8
$\begingroup$

You may:
Reduce a number by dividing it by its number of prime factors, counting multiplicities.
Repeat this on the result as much as you want.

Is there an infinite number of squares that can be reduced to their roots?

examples:
4 and 16 reduce to their root in one step
1600 reduces to 40 in 2 steps

Bonus points if the question also gets answered for higher powers.
I did not brute force it, but would not be surprised if 16 reduces to 2 in 2 steps is the only one.

Improve this question
$\endgroup$
6
  • $\begingroup$ This is a good one, have you managed to solve it yourself? $\endgroup$
    – hexomino
    Commented Sep 11, 2020 at 10:06
  • $\begingroup$ What means 'number of primes'? Number of prime factors or number of distinct prime factors? $\endgroup$
    – daw
    Commented Sep 11, 2020 at 10:08
  • 1
    $\begingroup$ @daw I was confused by this too, but it means prime factors, counting multiplicities. So $16=2^4$ has four prime factors ($2,2,2,2$) and $1600 = 2^6 5^2$ has eight ($2,2,2,2,2,2,5,5$) $\endgroup$
    – hexomino
    Commented Sep 11, 2020 at 10:12
  • $\begingroup$ @hexomino No, I find it not too difficult to find several more with pen and paper, but I don't see a prove for infinite in the pattern, not a pure math-logic proof. Is number of prime factors indeed better (i.e. less confusing) English? $\endgroup$
    – Retudin
    Commented Sep 11, 2020 at 10:46
  • 1
    $\begingroup$ @Retudin My own personal preference would be to say "number of prime factors, counting multiplicities" but the clearest way to explain would be by means of an example, so it might be useful to include that in your question. $\endgroup$
    – hexomino
    Commented Sep 11, 2020 at 10:57

3 Answers 3

Reset to default
7
$\begingroup$

Partial result:

Any solution is fully determined by the number $n$ of its prime factors. Indeed, assuming $s$ is a solution with $n$ prime factors, start with its square $s^2$ which has $2n$ prime factors. By definition of a solution we can divide $s^2$ by $2n$. If $2n$ has $k$ prime factors then $\frac{s^2}{2n}$ has $n'=2n-k$ prime factors. Again, we may divide by $n'$ and the result will have $n''=2n-k-k'$ prime factors where $k'$ is the number of prime factors of $n'$ and so on. Note that we only used the number of prime factors, and that this via the decompositions of $k,k',...$ determines what these factors are. Therefore an equivalent task to the one given is: Find numbers $n$ such that starting at $2n$ and repeatedly subtracting the number of prime factors we eventually hit $n$. If nothing else this is much easier to explore with a computer and there appear to be many (~1500 for squares with up to 10000 prime factors) solutions.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I hit upon this also. It seems like an easier proposition to prove but currently, I don't see a clear way. $\endgroup$
    – hexomino
    Commented Sep 11, 2020 at 13:22
  • 2
    $\begingroup$ @hexomino Maddening, isn't it? There are apparently so many and still no easy proof to see. $\endgroup$
    – Paul Panzer
    Commented Sep 11, 2020 at 13:40
3
$\begingroup$

Partial answer:

For roots less than 1 million, I have found the following squares that work: $2^2, 4^2, 40^2, 80^2, 756^2, 1512^2, 42120^2, 130560^2$. It is not clear whether this sequence continues indefinitely. The following squares arrive at 2: $2^2, 4^2, 80^2, 1008^2$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes. I already new this to be the smallest ones using Paul's tactic (before I asked the question). (dis)proving infinite is were I am stuck. $\endgroup$
    – Retudin
    Commented Sep 11, 2020 at 13:17
1
$\begingroup$

Probabilistic argument:

Use Paul Panzer's reduction to the following problem:

For a positive integer $n$, define $f(n)$ to be $n$ minus the number of prime factors of $n$, when counted with multiplicity. Are there infinitely many $n$ so that $n$ is in the sequence $2n,f(2n),f(f(2n)),\dots$?

Define $\Omega(n)$ to be the number of prime factors of $n$ counted with multiplicity. It is known that the average order of $\Omega(n)$ is $\log \log n$ (see here), so a reasonable guess would be that the sequence starting at $2n$ should not have any bias as to which numbers around $n$ it includes, since it should take an average of $n/\log \log n$ iterations of $f$ to get near $n$. As a result, one should expect $n$ to be in the sequence with probability about $1/\log \log n$, and $$\sum \frac{1}{\log \log n}$$ diverges. So, there should be infinitely many $N$ for which $N$ can be reached from $N^2$.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ And next we prove that every other even number is odd ;-D Just kidding, solid effort. One more serious nitpick, though. The $N^k,k>2$ cases are not only constrained by the number of prime factors but also partially by those primes having to fall into groups of $k-1$ of the same which I suspect makes things much more tricky. $\endgroup$
    – Paul Panzer
    Commented Sep 11, 2020 at 19:53
  • 1
    $\begingroup$ @PaulPanzer Yeah, there are definitely issues with the applicability of such an argument. I guess I expect that, since $2n$ is a lot greater than $n$, these irregularities should even themselves out, but it's certainly nowhere near a proof. $\endgroup$
    – Carl Schildkraut
    Commented Sep 11, 2020 at 21:34
  • $\begingroup$ @PaulPanzer Actually you're right -- for $N^3$ you would need some $n$ for which $n$ is in the sequence $3n,f(3n),f(f(3n))$ and the product of the terms before $n$ is a perfect square. This should still occur with decently high probability (enough for there to be infinitely many), but the asymptotics are a lot less convincing. $\endgroup$
    – Carl Schildkraut
    Commented Sep 12, 2020 at 1:38
  • 1
    $\begingroup$ @CarlSchildkraut I did comment "and higher powers are not". I read your "should still occur with decently high probability" as k=3 would diverge. Now you spelled out the formula I see that is not true. Now I am confused what you meant with "should still occur with decently high probability". $\endgroup$
    – Retudin
    Commented Sep 12, 2020 at 7:49
  • 1
    $\begingroup$ That explains it, a quick check on your cube claim let me too the same mistake. $\endgroup$
    – Retudin
    Commented Sep 12, 2020 at 8:00

Not the answer you're looking for? Browse other questions tagged or ask your own question.