
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
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:
The Pari code generator can handle all of AE, 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 <stdio.h> #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  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
an argument that the Collatz conjecture is false  dkcox  Number Theory  15  January 8th, 2014 05:20 AM 
Collatz conjecture & More (Please Help)  Aika  Number Theory  6  April 29th, 2012 06:34 AM 
Collatz conjecture, questions  xolruf  Number Theory  1  January 1st, 2012 08:11 AM 
Collatz Conjecture's solution  kaushiks.nitt  Number Theory  42  March 4th, 2011 04:20 PM 
Question relating to Collatz conjecture  steiner1745  Number Theory  1  February 28th, 2007 08:09 PM 