Problems & Puzzles: Puzzles

Puzzle 949. Another Collatz-like sequence Dmitry Kamenetsky sent the following nice puzzle: I came up with a very interesting problem: Start with a number k=2. If the current number k is prime then replace it with k*k+9. Otherwise replace it with k/2 (integer division). The sequence starts as 2 (prime), 13 (prime), 178, 89 (prime), 7930, 3965, 1982, 991 (prime), ... Q. Does this sequence ever reach a cycle or does it continue forever?

---

Contributions came from Adam Stinchcombe, Pierandrea Formusa, Jeff Heleen and Simon Cavegn

***

Adam wrote:

I did find a cycle starting with 3251:

 

[3251, 10569010, 5284505, 2642252, 1321126, 660563, 436343476978, 218171738489, 109085869244, 54542934622, 27271467311, 13635733655, 6817866827, 3408933413, 1704466706, 852233353, 426116676, 213058338, 106529169, 53264584, 26632292, 13316146, 6658073, 3329036, 1664518, 832259, 416129, 208064, 104032, 52016, 26008, 13004, 6502, 3251]

 

Using Maple, I limited my isprime test to a number with fewer than 90 digits, so most sequences went over the limit w/o cycling back.  I went out to a starting value of 104052 and the only cycle (that also stayed below 10^90) contained 3251.

***

Pierandrea wrote:

This sequence reaches a cycle for an infinite number of starting terms; the minimum length of cycle is 33. Below 1M we have ten starting terms that cycles in the lowest step number (i.e. 33): 
 

3251

6502 

13004 

26008 

52016 

104032 

208064
...

416129

660563

832259

 

Lowest starting term with minimum cycle is 3251, all the other ones are substantially multiple of 3251 (perfect multiples, apart 416129 that is 3251*128+1 and 832259 that is 3251*256+3, corrections absorbed by integer division in the chain rule) with the exception of 660563.

***

Jeff wrote:

I have taken this (starting k=2) to the 7089th step which produced a 1013 digit
prime 13347...41611 (proven by YAFU aprcl). No cycles.

***

Simon wrote:

Because primes become very rare for large k, it tends to divide by 2 almost always for large k. Therefore I think it is possible to proof that any

k = k*k + n (starting with k=2, n positive or 0) will always end in a loop. No loop would require k to grow towards infinity.

 

I wrote some code to check k*k+9, did not yet find a loop after this many steps:

step:1000 kdigits=54
step:3000 kdigits=12
step:10000 kdigits=2381
step:100000 kdigits=14402

step:200000 kdigits=2289
step:300000 kdigits=12813
step:309000 kdigits=42701

For those interested, here some hopefully efficient c# code, where "Integer" is using an old version 4.2 of https://gmplib.org/ compiled to a 64bit dll:

 

HashSet<Integer> hashSet = new HashSet<Integer>();
long count = 0;
Integer k = 2;
while (true)
{
    count++;
    if (k.IsProbablyPrime(20)) // This function performs some trial divisions, then 20 Miller-Rabin probabilistic primality tests. Error chance: 4^-20 per check
    {
        Integer.Mul(k, k, k);
        Integer.Add(k, k, n);
    } else {
        Integer.Div(k, k, 2u);
    }
    if (hashSet.Contains(k))
    {
        Log("Found loop for k*k+{0} at stepCount: {1}", n, count);
        break;
    }

    if (count % 1000 == 0)

    {

        hashSet.Add(new Integer(k));

    }

}

***

 

 

---