37

I'm trying to create a challenge for PP&CG where the object will be to find the longest sequence in a given time, but I'm worried that there may be an infinite sequence that will ruin things.

The sequence is similar to the Look-and-say sequence, but using the prime factors (in increasing order) of the previous term for the current. When the current term is prime, the sequence stops. For example, if the first term is 15, you get:

15       = one 3, one 5  (1 3 1 5)
1315     = one 5, one 263 (1 5 1 263)
151263   = two 3s, five 7s (2 3 5 7)
2357     = prime, stop sequence

So, starting with 15 gives a four-term series. Starting with any prime gives a one-term series.

Additionally, if a sequence revisits a number, it stops (counting the revisited number only once). I don't know if there are any cyclic sequences, but that's there to prevent it.

Each number I've tried so far (manually) eventually terminates, but I'm not confident that it holds for any starting term. Is there any simple insight I'm missing that would show (or disprove) that for every (positive) starting number the sequence will be finite? I don't care if it's absurdly long, just not infinite.

Community
  • 1
Bog Site
  • 471

1 Answers1

17

Starting with $8$ I get $32, 52, 22113, 5317113, 131167110613, \ldots$ and the sequence shows no sign of ending. At some point the numbers get so big that factoring becomes very slow. My program gave up when trying to factor $$ 231331170111602782603539242084011491005276716148307683565573944963714969597915443$$

EDIT: Let $x_k$ be the sequence of numbers obtained in this process. If $x_k = p_1 \cdots p_m$ has $n$ digits, the factors $p_1, \ldots, p_m$ have between $n$ and $n+m-1$ digits together (i.e. if $10^{d_j-1} \le p_j < 10^{d_j}$ and $s = d_1 + \ldots + d_m$ we have $10^{s-m} \le x < 10^s$), and (if the $p_j$ are distinct) the next number $x_{k+1}$ has between $n+m$ and $n + 2m-1$ digits. Numbers that are not squarefree reduce this somewhat. Typically, a number with $n$ digits has roughly $\log n$ distinct prime factors. So we should expect the number of digits in $x_k$ not to grow much more than linearly, maybe at most something like $k \log(k)$. The probability of a random integer of this size being prime is something like $\dfrac{1}{k \log(k)}$. Since $\sum_k \dfrac{1}{k \log(k)}$ diverges, we should expect to eventually encounter a prime. However, this is only a heuristic argument, not a proof, and that sum diverges extremely slowly, so given that we have reached an $81$-digit number without finding a prime the number of steps needed might well be enormous.

Here is a plot of the number of digits in $x_k$ for $k = 0 \ldots 20$ with $x_0 = 8$.

enter image description here

EDIT: Actually there was the bug in my code (I forgot that Maple does not always list the factors in numerical order), so the number 231331... above was wrong. But the plot should be correct. The $90$-digit $x_{20}$ is $$ \small 143314611607153852459854993120121438819369187408718398556398062751481672397689379055730183$$

trichoplax is on Codidact now
  • 159
Robert Israel
  • 448,999
  • 4
    But all it takes is one prime.... – Gerry Myerson Dec 29 '14 at 19:45
  • This is the problem I ran into trying to brute-force a counterexample. While many starting terms give rapidly increasing sequences, hitting a single prime number stops it. Factoring is slow, though, and I don't know that a program would "prove" an infinite sequence, just one that "hasn't stopped yet". – Bog Site Dec 29 '14 at 19:53
  • 4
    Indeed, it seems that at each step the number of digits increases rather slowly (e.g. after the $81$-digit integer above, which Maple eventually did factor, the next one has $86$ digits), and since an $n$-digit integer has probability $\approx const/n$ of being prime, it seems like with probability $1$ the process should eventually stop. But it could take a long, long time. And this is only a heuristic argument, not a proof. – Robert Israel Dec 29 '14 at 19:54
  • 3
    @RobertIsrael I upvoted because of that comment - could you add the heuristic to your answer? –  Dec 29 '14 at 20:21
  • $143314611607153852459854993120121438819369187408718398556398062751481672397689379055730183=3\cdot13\cdot47\cdot103\cdot419\cdot392023456666297\cdot7932852672683567\cdot582552829413557626341426823298517746606521215829157$ due to http://www.alpertron.com.ar/ECM.HTM – Lehs Dec 30 '14 at 11:49
  • @RobertIsrael: Here's the rub... heuristically, if the number of digits increases by a fixed number every step, then the process should stop with probability $1$ (since the sum of $1/n$ diverges). But if the number of digits increases by a fixed factor every step (say, by 2%), then the process would diverge with nonzero probability (since the sum of $n^{-1.02}$ converges). Seems hard to tell the difference between these two cases... it'll have to do with the smoothness of the numbers in the sequence, right? – mjqxxxx Oct 19 '15 at 23:08
  • What I suggested is that the number of digits after $n$ steps should be something like $n \log n$, based on the average behaviour of $\omega(x)$, the number of distinct prime factors of $x$. – Robert Israel Oct 20 '15 at 00:31