Problems & Puzzles: Puzzles

Puzzle 114. The Murad's generalization of the Collatz's sequences

The Collatz's original sequences {a0, a1, a2, ...} are such that, for any positive a0:

or an+1 = an/2, if an is even

or an+1 = 3.an+1, if an is odd.

Collatz conjectured that all these sequences form a "tree-structure" - except for one specific zone -, that is to say, all these sequences arrive to one and only one cycle of numbers - the cycle {...,4,2,1,4,2,1...} - no matter the starting number a0 of the particular sequence currently generated.

Murad AlDamen has sent to me a paper (20/10/2000) that shows that he has generalized the Collatz original sequences the following way:

For a predefined prime p:

or an+1 = an/P(qi), for all primes qi<p such that qi divides an

or an+1 = p.an+1, if  no one prime qi<p divides an

Example:

if p = 5 and a0 = 35, the Murad's sequence is: {35,176,88,44,22,11,56,28,14,7,36,6,1}

As you can easily recognize from the Murad's generalization formulas, the Murad's sequences for p = 3 are the same than the Collatz's sequences.

Murad has found the following conjectural empirical facts:

1.- The odd primes can be divided in two classes:

a) Class I:  the primes such that the sequences linked to them has a behavior similar to p=3, that is to say for any a0 starting value the sequence arrives to "1". This class of primes is composed for p = 3, 5, 7, 19,...

b) Class II: the primes such that the sequences linked to them for certain values a0  does not arrive to "1" but get 'hooked' to certain "cycles". This class of primes is composed for the primes p = 11, 13, 17,...

2.- For those sequences linked to the p primes of the Class II, their corresponding cycles:

a) are unique

b) always has at least one prime member, r such that r>p

Example:

The cycle for p = 11 is: {..., 17, 188, 94, 47, 518, 37, 408, 68, 34, 17,...}
(as usual the primes are in blue)

As a matter of fact Murad has verified the conjectural empirical facts associated to the Class II primes, for positive a0 values less than 106

Questions:

1. Can you extend the Classes of primes I & II? While extending the Class of primes II, can you submit the corresponding cycles?

2. Can you verify if the conjectural empirical facts 2 a) & 2 b) are absolutely true?

3. Is this generalization useful as an approach to solve the original Collatz's conjecture?

Jeff Heleen has sent (16/20/2000) an interesting and complete study of the Murad's sequences for all numbers below 1000 that are class 2.

"Here are some results for problem 114. Shown below are numbers less than 1000 that are Class 2 (there are 107 of them). The number in parenthesis is the first (lowest) instance where the given number departs from Class 1 behavior.  There is one instance where the given number and its departure point are the same (281).

 11 (17) 167 (1787) 373 (4519) 601 (1637) 797 (823) 13 (19) 173 (1697) 379 (857) 613 (6299) 809 (29383) 17 (43) 181 (991) 383 (461) 617 (306463) 821 (7699) 19 (46063) 193 (233) 401 (3527) 619 (22853) 829 (1103) 23 (179) 223 (503) 409 (967) 641 (14149) 839 (1327) 31 (67) 227 (50789) 421 (526649) 659 (2731) 857 (223063) 37 (2173) 233 (1181) 431 (743) 661 (691) 859 (1493) 43 (174569) 239 (431) 449 (65497) 673 (27337) 863 (753191) 47 (859) 241 (2713) 457 (521) 677 (11467) 877 (887) 53 (19559) 251 (1831) 461 (521) 683 (7207) 881 (1091) 59 (73) 257 (461) 467 (499) 691 (1489) 883 (8839) 61 (97) 263 (2579) 491 (15641) 701 (95483) 907 (937) 67 (181) 269 (523) 503 (532867) 709 (341461) 911 (44207) 71 (306511) 271 (337) 523 (3739) 719 (1579) 919 (2083) 73 (409) 277 (5851) 541 (356731) 727 (1423) 937 (12421) 83 (89) 281 (281) 547 (12473) 739 (27077) 947 (2351) 97 (631) 283 (311) 563 (587) 743 (5171) 971 (2027) 101 (661) 293 (22777) 571 (14533) 751 (881) 983 (1319) 103 (11131) 313 (17077) 577 (661) 757 (809) 991 (2671) 113 (857) 347 (892999) 587 (855923) 761 (4091) 151 (5501) 353 (48239) 593 (827) 769 (6043) 163 (383) 367 (619) 599 (4663) 787 (2521)

All other odd prime numbers less than 1000 (there are 60 of them left) are Class 1 for all starting numbers <10^6.

***

This interesting table shows that the Murad's claim that 19 was a prime of the class 1 was wrong...

***

Jeff continues his patient work (Dec/3/2000):

I have further checked the 60 class 1 numbers <1000 up to 10^7. The following primes have also gone class 2:

131 (1787497)
137 (1008793)
139 (1789589)
197 (3543521)
229 (7797743)
331 (3073813)
389 (5594623)
499 (2806543)
509 (2187221)

Again, the number in parenthesis is where the prime first departs class 1. I'll now be checking the remaining 51 primes to higher levels.

***

Naturally that after the good work of Jeff the following conjecture arises: maybe there are not other primes class 1 except the prime 3.

Any bet?

***

Jeff Heleen wrote  the 17/12/2000:

"I have now finished checking the remaining 51 class 1 primes. Up to 10^8 they are all still class 1."

***

Jeff Heleen wrote on Feb 2012

For puzzle 114 I have now checked the remaining 51 primes up to 10^10. The following primes have also switched from class 1 to class 2:

89 (335272373)
317 (255276859)
349 (112982641)
433 (999070381)
463 (736368469)
607 (102689623)
647 (437736413)
953 (111295097)
967 (102314733)
997 (1049747401)

Again, the number in parenthesis is where the prime first departs class 1.

***

Ralph Muschall wrote on Nov 14, 2017:

I am just running a few examples of the Murad-Collatz problem and found
smaller results than those given by Jeff Heleen:

For 607, I got a loop starting with 4171571 (peak value: 1135356711237899082)
and for for 967: 13118317 (peak 202940612036308874).

I use a simple c++ program linked with libgmpxx and libgmp.

The start values given by Jeff Heleen don't give non-trivial loops for me.
Both of these values are located closely below 2**30, maybe one of the
bignum libraries used either by me or by him are buggy in that region.
Are other independent people studying this problem?

***

Jeff wrote on Nov 19, 2017:

I see Ralph Muschall found smaller results for 607 and 967 in puzzle 114. I found my old programs
and checked and indeed his smaller results are correct. I decided to check the others and, assuming
I am using my own program correctly, found another smaller result as well.

For 953 I found 28279021. If someone could verify this.

***

 Records   |  Conjectures  |  Problems  |  Puzzles