March 26th, 2013, 04:02 PM  #1 
Math Team Joined: Apr 2012 Posts: 1,579 Thanks: 22  Old King Collatz
Yeah, just a little more musing ... Just as we know that if all the odds map to 1 through repeat application of the Collatz function(s), then all the evens do, too, I'd like to show now that if all odds of the form 8k+1, 8k+3 and 8k+7 eventually map to 1, so do all odds of the form 8k+5. This is indeed just a minor algebraic refinement of Hedge's "layers" program. The Collatz functions are if n is even, divide by 2 and if n is odd, multiply by 3 and add 1. The conjecture is that no matter what positive integer you start with, you will eventually reach 1. This has been confirmed for billions if not trillions of numbers. Anyway, it is obvious that all the powers of 2 boil straight down to 1 and the game is, so to speak, to get to the powers of 2. Note that different odds will get you to different powers of 2, but once there, they all race to 1. So in a sense, ALL odds that map to a power of 2 are what I called "gateway" odds. The smallest is 1 itself. 3*1+1 = 4 and 4 divides twice by 2 to reach 1 again. This loop is actually important for Collatz to be true. For if 1 did not map back to 1, then neither would any numbers it maps to! The other "gateway" odds can be calculated from the first one by repeat application of the function n > 4n+1. So the next ones are 5, 21, 85, 341, ... You can see why 4n+1 works by considering the following. 3(1)+1 = 4 or 2^2. Let the nth gateway odd equal 2k+1. 3(2k+1)+1 = 6k+4 is then some power of 2. But then 4(2x+1)+1 = 8x+5 and 3(8x+5)+1 = 24x+ 14, which equals 4(6k+4). Since we stipulated that 6k+4 is a power of 2, obviously 4 time 6k+4 will be as well. And indeed, the powers of 2 reachable from the odds are the powers of 4: 1>4, 5>16, 21>64, etc. But this phenomenon is general. So, if it is obvious that all powers of 2 boil down to their largest odd fact, ie 1, it is equally obvious that all evens that have a common largest odd factor greater than 1 will all boil down to that odd factor. 10, 20, 40, 80, 160 all are powers of 2 times their largest common odd fact, ie 5. So that in turn means that any odds that map ONTO this sequence will all map to 5! The smallest is 3, as 3*3+1=10. But by the exact same algebraic argument shown about, we can get a whole slew of numbers that map onto this sequence. As with the powers of 2, there will be odds mapping onto only every other even in the sequence. So the next one is 4*3+1=13. Then 4*13+1=53. These numbers are of course, like 5 and 21, of the form 8x+5. The point is that for ALL numbers of the form 8x+5, there is a smaller odd that you can calculate by subtracting 1 and dividing by 4, ie (8x+51)/4 = 2x+1 for any x. Conversely, multiply 8x+5 by 3 and adding 1 will get you an even that is 4 times the size of the number you get by multiplying 2x+1 by 3 and adding 1. So the two numbers will simply be higher and lower powers of 2 times the same greatest common odd factor, and those evens will boil down to the same odd. Therefore, by Collatz, 3>10>5 and 13>40> and 53>160>5. So if 3 maps eventually to 1 (as it does by 5>>16>1), so do all the other forms derived from 3 by the 4n+1 function. And this is true of all these "layers", as Hedge calls them. If the smallest form, which will be of one of the forms 8x+1 or 8x+3 or 8x+7, maps to one, so do all the number of the form 8x+5 derived from that lowest number, Conversely, every number of the form 8x+5 is derived from some number of the form 2x+1 by the 4n+1 rule. Therefore, Collatz is REALLY about whether all odds that equal 1, 3 or 7 mod 8 will eventually map to 1. Showing that is STILL a tall order, but let's keep chipping away at this thing logically, eh? 
March 26th, 2013, 04:58 PM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 932 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Old King Collatz
As I recall Olivera e Silva uses a greatlyexpanded version of this in his largescale verification. I don't know what modulus he uses but surely closer to 2^20 than 2^3.

March 27th, 2013, 02:24 AM  #3  
Math Team Joined: Apr 2012 Posts: 1,579 Thanks: 22  Re: Old King Collatz Quote:
 
March 27th, 2013, 02:45 AM  #4 
Math Team Joined: Apr 2012 Posts: 1,579 Thanks: 22  Re: Old King Collatz
But do note that I didn't choose to examine Collatz from the point of view of mod 8. After having noted that the evens all boil down to their largest odd factor, I wanted to look at the odds that map to the same largest odd factor of the various evens they map directly into and noticed that the odds that map into higher even multiples of a given odd factor are always of the form 8x+5 and that indeed all numbers of the form 8x+5 will map into a higher even that shares a largest odd factor with a smaller odd of a different form. The 8x+5's just kinda take themselves out of the game as things to worry about. If odds that equal 1, 3 or 7 mod 8 all map eventually to 1, the ones that equal 5 mod 8 come alongs with them for free.

March 27th, 2013, 04:02 AM  #5 
Senior Member Joined: Mar 2012 Posts: 569 Thanks: 26  Re: Old King Collatz
Going back to this chart, http://barkerhugh.blogspot.co.uk/2013/0 ... chart.html  a couple of observations: The columns of the chart are labelled according to the highest value of n for which the numbers are 1 mod 2^n. The 2n+1 column contains all numbers that are 3 or 7 mod 8. Column 2 has all numbers that are 5 mod 8. The other columns have all numbers that are 1 mod 8 (divided according to whether they can also be expressed as 1 mod 16, 1 mod 32 etc). I'd be interested in the verification work C.R. mentioned as that is another way of classifying numbers according to their 2^n modular value, will have a poke around. Anyhow, all the 1 mod 8 numbers follow a similar pattern whereby the numbers move two columns back towards the left hand side (I've marked a couple of these paths  the number of rows down you move can also be defined, but a bit lengthy to describe right now). If a number is 1 mod 2^n and n is odd, the path will lead to the first column (3 or 7 mod 8 ) while if n is even, the path will lead to the 5 mod 8 column (and as you've noted this will in turn lead to an odd number that can also be reached from a number that is 1, 3 or 7 mod 8 ). Within the 8n+1 region, from a starting (odd) number x, the next number in the path = 3(x1)/4 + 1 and this reiterates until you reach a number that can't be further reduced this way to an odd number. (Incidentally, 129 should have been coloured in brown in that image also). So there is a sense in which you could also say that 8n+1 numbers can be taken out of the game  as they follow an easily defined path back to column 1 or 2. That's a bit circular though, as it kind of brings the 8n+5 numbers back into play  it would be more use if we could also rule out the possibility of a constant loop between the 8n+1 region and 8n+5 column. Uninterrupted upwards paths are restricted to the first column. 8n + 5 numbers always resolve (via 24n + 16) to a lower number, 3n+ 2 (which can be odd or can be an even which will in turn resolve to a lower odd by halving). There are a few more patterns there, might come back to this later... 
March 27th, 2013, 05:12 AM  #6  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 932 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Old King Collatz Quote:
(Sorry, I misspelled the name, it should be Oliveira).  
March 27th, 2013, 05:32 AM  #7  
Senior Member Joined: Mar 2012 Posts: 569 Thanks: 26  Re: Old King Collatz Quote:
 
March 27th, 2013, 05:41 AM  #8 
Senior Member Joined: Mar 2012 Posts: 569 Thanks: 26  Re: Old King Collatz
While I think of it, you can pretty much also take the 8n+7 numbers 'out of the game'. If you start from a number in the 2n+1 column on my chart (3, 7, 11, ...) all 8n+7 numbers are the start of a sequence that climbs up that column until you reach a 8n+ 3 number, at which point you go to one of the columns to the right (this also has a definite structure, but quite a complicated one). For instance you get 7>11 15>23>35 31>47>71>107 39>59 The number of upward steps within this column depends on the value of n if you describe the starting number as 1 mod 2^n (if you take the highest possible value of n). You will get n2 upward steps within the 2n+1 column, then one more to another column. So 7 = 1 mod 2^3 and you get 2 upward steps, with the last one taking you to 17 in the 16n+1 column. There may be better ways to describe these patterns, just noting what I observe. 
March 27th, 2013, 05:55 AM  #9 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 932 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Old King Collatz
I guess there are two kinds of eliminations here: numbers that go to a smaller number and numbers that merely go to some other residue class. I'm less comfortable excluding the latter because the first number that loops (other than 4, 2, 1) might be of this type, and so if you use that elimination rule you're limited in your ability to use the other.

March 27th, 2013, 06:13 AM  #10 
Senior Member Joined: Mar 2012 Posts: 569 Thanks: 26  Re: Old King Collatz
Yes, I'm putting "out of the game" in scare quotes, because I know it is a bit of an overstatement  it's not so much an elimination as classifying numbers in a way that helps to clarify possible paths and areas to concentrate on in trying to understand them. But I find it interesting/fun to look at the patterns in the paths various residue classes take  even if this approach tells us more about the logic of those paths than it does about the possibility of a loop  The fact that 8n+5 numbers can all be effectively reduced a different residue class mod 8 doesn't mean you couldn't get a loop back to one of the same 8n+5 numbers. And the fact that all 2^n + 1 numbers (for n>2) follow a 1 step up 2 steps down path to a 2^n + 1 number (n=1 or 2) similarly doesn't rule out a loop back to the same path. I find it much harder to imagine an approach that would rule that out, unless you could show that any path must eventually hit a power of 2 in which case that would automatically exclude the possibility of a loop other than 4, 2, 1. 

Tags 
collatz, king 
Search tags for this page 
dream weaver collatz conjecture,how to get the rule for mapping,mathematics rule of mapping,how to find the rule of a mapping,if 3/2p1=1/3/1/4p 1
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Collatz with fractions  Hedge  Number Theory  0  January 5th, 2014 07:01 AM 
Collatz thoughts  Hedge  Number Theory  20  July 8th, 2013 02:01 AM 
Vote for the King  mathmaniac  Physics  16  March 20th, 2013 06:58 PM 
Who is the king?  Math Dreamer  New Users  5  April 21st, 2012 11:23 AM 
"The present king of France is bald"..False or Meaningless?  Owen  Applied Math  13  January 26th, 2011 02:05 PM 