My Math Forum Similar to Collatz Conjecture

 Number Theory Number Theory Math Forum

 September 6th, 2009, 09:44 AM #1 Newbie   Joined: Mar 2009 Posts: 4 Thanks: 0 Similar to Collatz Conjecture First considered the following (Call it "A"): If x is even, x=x/2 If x has a 1 in the units place, 1x+1=x If x has a 3 in the units place, 3x+1=x If x has a 5 in the units place, 5x+1=x If x has a 7 in the units place, 7x+1=x If x has a 9 in the units place, 9x+1=x Does every initial x go to 1? No, there are counterexamples. 5, 26, 13, 40, 20, 5. Now consider another (Call this "B"): If x is even, x=x/2 If x has a 1 in the units place, 3x+1=x If x has a 3 in the units place, 5x+1=x If x has a 5 in the units place, 7x+1=x If x has a 7 in the units place, 9x+1=x If x has a 9 in the units place, 1x+1=x Does every initial x go to 1 now? No, again a counterexample starting with 5: 5, 36, 18, 9, 10, 5. Next one: ("C") If x is even, x=x/2 If x has a 1 in the units place, 5x+1=x If x has a 3 in the units place, 7x+1=x If x has a 5 in the units place, 9x+1=x If x has a 7 in the units place, 1x+1=x If x has a 9 in the units place, 3x+1=x Upon initial examination, every initial x does seem to go to 1. It takes 139 steps from 5: 5, 46, 23, 162, 81, 406, 203, 1422, 711, 3556, 1778, 889, 2668, 1334, 667, 668, 334, 167, 168, 84, 42, 21, 106, 53, 372, 186, 93, 652, 326, 163, 1142, 571, 2856, 1428, 714, 357, 358, 179, 538, 269, 808, 404, 202, 101, 506, 253, 1772, 886, 443, 3102, 1551, 7756, 3878, 1939, 5818, 2909, 8728, 4364, 2182, 1091, 5456, 2728, 1364, 682, 341, 1706, 853, 5972, 2986, 1493, 10452, 5226, 2613, 18292, 9146, 4573, 32012, 16006, 8003, 56022, 28011, 140056, 70028, 35014, 17507, 17508, 8754, 4377, 4378, 2189, 6568, 3284, 1642, 821, 4106, 2053, 14372, 7186, 3593, 25152, 12576, 6288, 3144, 1572, 786, 393, 2752, 1376, 688, 344, 172, 86, 43, 302, 151, 756, 378, 189, 568, 284, 142, 71, 356, 178, 89, 268, 134, 67, 68, 34, 17, 18, 9, 28, 14, 7, 8, 4, 2, 1. Next one ("D"): If x is even, x=x/2 If x has a 1 in the units place, 7x+1=x If x has a 3 in the units place, 9x+1=x If x has a 5 in the units place, 1x+1=x If x has a 7 in the units place, 3x+1=x If x has a 9 in the units place, 5x+1=x Also has a loop starting at 5: 5, 6, 3, 28, 14, 7, 22, 11, 78, 39, 196, 98, 49, 246, 123, 1108, 554, 277, 832, 416, 208, 104, 52, 26, 13, 118, 59, 296, 148, 74, 37, 112, 56, 28 And the last one ("E"): If x is even, x=x/2 If x has a 1 in the units place, 9x+1=x If x has a 3 in the units place, 1x+1=x If x has a 5 in the units place, 3x+1=x If x has a 7 in the units place, 5x+1=x If x has a 9 in the units place, 7x+1=x I also can't find any counterexample, and this one seems to reach 1 much faster than C. So, can anyone find any counterexamples for "C" or "E"? Any interesting observations?
 September 6th, 2009, 10:53 AM #2 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Re: Similar to Collatz Conjecture No counterexamples for C up to 10 million. I think that this could be programmed very efficiently, though I haven't done so myself. Calculate the value mod 80 (or something like that) and check cases. For each case you can do several steps at a time. Better, you can calculate where the sequence will be at its lowest point out of those steps and use it to see if you can stop early. For example, suppose for C you know that if n is 17 mod 20, four steps will take it to (3n + 5)/4 -- try it! But you also know that the lowest point in those four steps will be (n + 1)/2. So if you know that C terminates for all values below L, then you can check if (n + 1)/2 < L. If so, it terminates; if not, replace it with (3n + 5)/4.
September 6th, 2009, 12:17 PM   #3
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Similar to Collatz Conjecture

Ugh, no good. I wrote the program:
Quote:
 OK, I wrote a better program. I made a code generator in Pari (see my .sig) which wrote the key part of the code in C. I wrote the rest of the code and compiled with the highest optimization settings in gcc. It's blazingly fast compared to my earlier version, maybe 100 times faster. It could still be improved, if I really wanted more speed. I've verified C up to several billion. My program said [quote:1z5eqcqt]137289583 does not halt after about 2700 steps.
but when I had it try more iterations it was able to show that it does go to 1.

The Pari code generator can handle all of A-E, so I can try others if you'd like.[/quote:1z5eqcqt]
but when I went back to test that all the numbers stayed within range, they didn't. 64 bits just doesn't cut it.

Oh well, I'm going to have to stick with Pari for now. At least it doesn't overflow.

 September 6th, 2009, 12:30 PM #4 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Re: Similar to Collatz Conjecture If you're interested, my C code looks something like this: Code: #include #define u64 unsigned long long void test(u64 num); u64 steps(u64 n); u64 L; int main () { u64 start = 10; u64 end = 1000; printf("Testing conjecture up to %llu, assuming it holds below %llu.\n", end, start); for(L = start | 1; L <= end; L += 2) test(L); return 0; } // Requires that n is odd. void test(u64 num) { const int bigsteps = 1000; u64 n = num; int i = 0; for (; i < bigsteps; ++i) { n = steps(n); if (n == 0) return; } printf("%llu does not halt after about %d steps.\n", num, 9 * bigsteps); } // Requires that n is odd; returns 0 if n halts and an odd number otherwise. u64 steps(u64 n) { switch (n%40) { case 1: n = (n * 175 + 49) >> 3; break; case 3: n = (n * 35 + 7) >> 3; break; case 5: n = (n * 315 + 49) >> 3; break; case 7: n = (n + 1) >> 3; break; case 9: n = (n * 3 + 5) >> 3; break; case 11: n = (n * 5 + 1) >> 3; break; case 13: n = (n * 49 + 11) >> 3; break; case 15: n = (n * 9 + 1) >> 3; break; case 17: n = (n * 3 + 5) >> 3; break; case 19: n = (n * 9 + 5) >> 3; break; case 21: n = (n * 35 + 9) >> 3; break; case 23: n = (n * 245 + 53) >> 3; break; case 25: n = (n * 63 + 9) >> 3; break; case 27: n = (n + 5) >> 3; break; case 29: n = (n * 3 + 1) >> 3; break; case 31: n = (n * 15 + 7) >> 3; break; case 33: n = (n * 7 + 1) >> 3; break; case 35: n = (n * 27 + 7) >> 3; break; case 37: if (((n + 1) >> 1) < L) return 0; n = (n * 9 + 19) >> 3; break; case 39: n = (n * 27 + 19) >> 3; break; } while (!(n&1)) n >>= 1; if (n < L) return 0; if (n > 58561092297490640ULL) printf(" Warning: value %llu potentially out of range\n", n); return n; }
 September 6th, 2009, 07:13 PM #5 Newbie   Joined: Mar 2009 Posts: 4 Thanks: 0 Re: Similar to Collatz Conjecture I am interested; thank you very much. If you consider [abcde] to refer to If x is even, x=x/2 If x has a 1 in the units place, ax+1=x If x has a 3 in the units place, bx+1=x If x has a 5 in the units place, cx+1=x If x has a 7 in the units place, dx+1=x If x has a 9 in the units place, ex+1=x Then there are 120 different sets where a, b, c, d, e = 1, 3, 5, 7, and 9. (eg [13579] which was "A" above, [57913] which was "C", and [17539] which wasn't listed). I'm going to look at all of them and see how many I can't find counterexamples (sequences not including 1) for and if anything else interesting emerges. I'll post again soon.
 September 6th, 2009, 09:30 PM #6 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Re: Similar to Collatz Conjecture In that case I'll post my Pari code generator. To write code for what you refer to as [abcde] mod M (say, 10 or 20), type "setupCases(M, [a,b,c,d,e])". I used "setupCases(40, [5,7,9,1,3])" to generate my C code above. Increasing the modulus doesn't change the outcome unless you would overflow. Code: \\ See http://mymathforum.com/viewtopic.php?f=40&t=9377 setupCases(modulus, table)={ \\ Modulus should be a power of two times five. print("long long steps(n) {"); print("\tswitch (n%"modulus") {"); forstep(n=1,modulus,2, print("\tcase "n":"); setup(n, modulus, table); print("\t\tbreak;"); ); print("\t}"); print("\twhile (!(n&1))"); print("\t\tn >>= 1;"); print("\tif (n < L)"); print("\t\treturn 0;"); print("\treturn n"); print("}"); }; \\ See http://mymathforum.com/viewtopic.php?f=40&t=9377 \\ Replace 2n with n, and odd n with n * table[(n%10) >> 1 + 1] + 1. \\ C: [5, 7, 9, 1, 3] setup(a, b, table,verbose)={ my(best=1,c=1,d=0,bestPlus,bestShft=0,mult,shft=0,bestValueIsFinal=0,bestValueIsMedial=0); if(b%10 > 0, error("Modulus not divisible by 10")); while (b%2 == 0, if (verbose, print(c"n + "d" = "a" (mod "b")") ); if (a%2, mult = table[(a%10) >> 1 + 1]; if (verbose, print(" Ends in "a%10"; multiplying by "mult" and adding one."); ); b *= mult; c *= mult; a = a * mult + 1; d = d * mult + 1; , a /= 2; b /= 2; c /= 2; d /= 2; if (c <= best && (c < best || d < bestPlus), best = c; bestPlus = d; ) ) ); if (best < 1, if (best == c && bestPlus == d, bestValueIsFinal = 1; , bestValueIsMedial = 1; ) ); while(denominator(c * d) > 1, c *= 2; d *= 2; shft++ ); while(denominator(best * bestPlus) > 1, best *= 2; bestPlus *= 2; bestShft++ ); if (bestValueIsMedial, if (best == 1, print("\t\tif (((n + "bestPlus") >> "bestShft") < L)") , print("\t\tif (((n * "best" + "bestPlus") >> "bestShft") < L)") ); print("\t\t\treturn 0;"); ); if (c == 1, print("\t\tn = (n + "d") >> "shft";") , print("\t\tn = (n * "c" + "d") >> "shft";") ); \\if (bestValueIsFinal, \\ print("\t\tif (n < L)"); \\ print("\t\t\treturn 0;"); \\) \\ Currently handled elsewhere };
 September 7th, 2009, 07:26 PM #7 Newbie   Joined: Mar 2009 Posts: 4 Thanks: 0 Re: Similar to Collatz Conjecture Some initial observations: -Other than [57913] discussed above, only one of the 120 series takes longer to converge to 1from an initial value 5: [97513], which takes an unexpectedly impressive 663 steps. Wow. -4 of the series appear to go to infinity with an initial value of 5: [37195], [53719], [73915], [97135]. This was unexpected. It is possible they form very large loops or converge to 1 after more than 5000 steps. I find the latter unlikely, but the former is possible. [93715] eventually settles into a 1214 member loop with an initial value of 5.

 Tags collatz, conjecture, similar

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post dkcox Number Theory 15 January 8th, 2014 05:20 AM Aika Number Theory 6 April 29th, 2012 06:34 AM xolruf Number Theory 1 January 1st, 2012 08:11 AM kaushiks.nitt Number Theory 42 March 4th, 2011 04:20 PM steiner1745 Number Theory 1 February 28th, 2007 08:09 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top