My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
September 6th, 2009, 10: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?
8Pickle is offline  
 
September 6th, 2009, 11:53 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
September 6th, 2009, 01:17 PM   #3
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
September 6th, 2009, 01:30 PM   #4
Global Moderator
 
CRGreathouse's Avatar
 
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;
}
CRGreathouse is offline  
September 6th, 2009, 08: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.
8Pickle is offline  
September 6th, 2009, 10:30 PM   #6
Global Moderator
 
CRGreathouse's Avatar
 
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
};
CRGreathouse is offline  
September 7th, 2009, 08: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.
8Pickle is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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 06:20 AM
Collatz conjecture & More (Please Help) Aika Number Theory 6 April 29th, 2012 07:34 AM
Collatz conjecture, questions xolruf Number Theory 1 January 1st, 2012 09:11 AM
Collatz Conjecture's solution kaushiks.nitt Number Theory 42 March 4th, 2011 05:20 PM
Question relating to Collatz conjecture steiner1745 Number Theory 1 February 28th, 2007 09:09 PM





Copyright © 2018 My Math Forum. All rights reserved.