My Math Forum  

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

Number Theory Number Theory Math Forum


Thanks Tree1Thanks
Reply
 
LinkBack Thread Tools Display Modes
March 26th, 2013, 05: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+5-1)/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?
johnr is offline  
 
March 26th, 2013, 05:58 PM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Old King Collatz

As I recall Olivera e Silva uses a greatly-expanded version of this in his large-scale verification. I don't know what modulus he uses but surely closer to 2^20 than 2^3.
CRGreathouse is offline  
March 27th, 2013, 03:24 AM   #3
Math Team
 
Joined: Apr 2012

Posts: 1,579
Thanks: 22

Re: Old King Collatz

Quote:
Originally Posted by CRGreathouse
As I recall Olivera e Silva uses a greatly-expanded version of this in his large-scale verification. I don't know what modulus he uses but surely closer to 2^20 than 2^3.
Is there anything online about this?
johnr is offline  
March 27th, 2013, 03: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.
johnr is offline  
March 27th, 2013, 05:02 AM   #5
Senior Member
 
Joined: Mar 2012

Posts: 572
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(x-1)/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...
Hedge is offline  
March 27th, 2013, 06:12 AM   #6
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Old King Collatz

Quote:
Originally Posted by johnr
Quote:
Originally Posted by CRGreathouse
As I recall Olivera e Silva uses a greatly-expanded version of this in his large-scale verification. I don't know what modulus he uses but surely closer to 2^20 than 2^3.
Is there anything online about this?
http://www.ieeta.pt/~tos/3x+1.html

(Sorry, I misspelled the name, it should be Oliveira).
CRGreathouse is offline  
March 27th, 2013, 06:32 AM   #7
Senior Member
 
Joined: Mar 2012

Posts: 572
Thanks: 26

Re: Old King Collatz

Quote:
Originally Posted by CRGreathouse

http://www.ieeta.pt/~tos/3x+1.html

(Sorry, I misspelled the name, it should be Oliveira).
Thanks, I'll see if I can get my head round that.
Hedge is offline  
March 27th, 2013, 06:41 AM   #8
Senior Member
 
Joined: Mar 2012

Posts: 572
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 n-2 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.
Hedge is offline  
March 27th, 2013, 06:55 AM   #9
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

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.
CRGreathouse is offline  
March 27th, 2013, 07:13 AM   #10
Senior Member
 
Joined: Mar 2012

Posts: 572
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.
Hedge is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
collatz, king



Search tags for this page
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 03:01 AM
Vote for the King mathmaniac Physics 16 March 20th, 2013 07:58 PM
Who is the king? Math Dreamer New Users 5 April 21st, 2012 12:23 PM
"The present king of France is bald"..False or Meaningless? Owen Applied Math 13 January 26th, 2011 02:05 PM





Copyright © 2017 My Math Forum. All rights reserved.