37
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ Have you tried with large numbers? $\endgroup$ – HereToRelax Dec 29 '14 at 18:50
  • 4
    $\begingroup$ @FooBarrigno It's four 2s and nine 3s, so the next term is 4293. $\endgroup$ – Bog Site Dec 29 '14 at 19:44
  • 4
    $\begingroup$ It seems odd to me that you declare primes to be stopping points as opposed to just prepending a $1$ (i.e., $3$ = "one three" -> $13$). $\endgroup$ – Micah Dec 29 '14 at 19:48
  • 5
    $\begingroup$ $25 = 5^2$ is a fixed point. $\endgroup$ – Robert Israel Dec 29 '14 at 20:01
  • 3
    $\begingroup$ ... and there are no other fixed points or two-cycles up to $10^6$. $\endgroup$ – Robert Israel Dec 29 '14 at 20:12
17
+50
$\begingroup$

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$$

$\endgroup$
7
  • 4
    $\begingroup$ But all it takes is one prime.... $\endgroup$ – Gerry Myerson Dec 29 '14 at 19:45
  • $\begingroup$ 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". $\endgroup$ – Bog Site Dec 29 '14 at 19:53
  • 4
    $\begingroup$ 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. $\endgroup$ – Robert Israel Dec 29 '14 at 19:54
  • 3
    $\begingroup$ @RobertIsrael I upvoted because of that comment - could you add the heuristic to your answer? $\endgroup$ – user98602 Dec 29 '14 at 20:21
  • $\begingroup$ $143314611607153852459854993120121438819369187408718398556398062751481672397689379055730183=3\cdot13\cdot47\cdot103\cdot419\cdot392023456666297\cdot7932852672683567\cdot582552829413557626341426823298517746606521215829157$ due to alpertron.com.ar/ECM.HTM $\endgroup$ – Lehs Dec 30 '14 at 11:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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