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 27th, 2013, 06:13 PM   #21
Math Team
 
Joined: Apr 2012

Posts: 1,579
Thanks: 22

Re: Old King Collatz

In any event, simply taking any number of the form 8x+5 and reversing the 4n+1 rule to get (8x+5-1)/4 = (8x+4)/4 = 2x+1, dividing by 8 and reapplying the rule every time you get a new number of the form 8k+5 until you finally get a number of some other mod 8 residue class is conceptually as simple as it gets. You will definitely eventually get an odd number that equals 1, 3 or 7 mod 8, guaranteed! 3n+1 either is or isn't odd, depending on n.
johnr is offline  
 
March 28th, 2013, 02:05 AM   #22
Senior Member
 
Joined: Mar 2012

Posts: 572
Thanks: 26

Re: Old King Collatz

The difference is that in my formulation you don't have to keep changing the value of n (or k) and reapplying a rule. There is one rule for 8n+5 numbers (that aren't 16n+5 numbers), and then one rule for 16n+5, 64n+21 etc. So I'd say it is conceptually a bit simpler as it gives an algorithm for the equivalent 8n+1, 3, 7 number* without relying on reiterations. Phrasing it slightly differently as the even/odd thing was a bit confusing:

For 8k+5 numbers (that can't be expressed 16n+5) go to 2k+1 (with the same value of k and we know this isn't an 8n+5 number)
For 16k+5, 64k+21, 256k+85 etc go to k (if k is odd) or 4k+1 (if k is even)

8k+5
13 = 8*1+5 -> 2*1+1 = 3 (->5)
29 -> 8*3+5 -> 2*3+1 = 7 (->11)
45 = 8*5+5 -> 2*5+1 = 11
61 = 8*7+5 -> 2*7+1 = 15
77 = 8*9+5-> 2*9+1 = 19

16k+5
5 = 16*0+5 -> 4*0+1 = 1
21 = 16*1+5 -> 1
37 = 16*2+5 -> 4*2+1 = 9 (previously I was jumping to the next step here, with 3*2+1 = 7, but it's clearer like this)
53 = 16*3+5 -> 3
69 = 16*4+5 -> 4*4+1 = 17
85 = 64*1+21 -> 1
101 = 16*6+5 -> 6*4+1 = 25
117 = 16*7+5 -> 7
133 = 16*8+1 -> 8*4+1 = 33
149 = 64*2+21 = 2*4+1 = 9
165 = 16*10 = 10*4+1 = 41
181 = 16*11+5 = 11

and so on - using this method, you always reach a number that isn't 8n+5 so don't need to reiterate the operation and can work out the equivalent 8n+1, 3, 7 number for the next step directly.

You can also see how it is the 8n+5 numbers that are equivalent to 8n+3 or 8n+7, while the 16n+5 numbers alternate between series of 8n+1 numbers, and another iteration of the 8n+3 and 8n+7 series.

*equivalent in terms of the onward path, not the path that went before, obviously.
Hedge is offline  
March 28th, 2013, 02:16 AM   #23
Senior Member
 
Joined: Mar 2012

Posts: 572
Thanks: 26

Re: Old King Collatz

The other reason for looking at it this way is that in order to study the pattern it might be useful to break out different series - first for the 8n+5 numbers (3, 7, 11, 15..., then the 16n+5 etc ones (and for 64n+5, 64n+21, 256n+85 etc you get a reiteration of the same series, so above we have started two series of 1, 9, 17 etc, one for the 16n+5 numbers, interlocking with one for the 64n+21 numbers).
Hedge is offline  
March 28th, 2013, 04:42 AM   #24
Math Team
 
Joined: Apr 2012

Posts: 1,579
Thanks: 22

Re: Old King Collatz

But you have to do essentially the same amount of calculation to determine which rule to apply out of what is actually an infinity of rules. So even what the next rule is would at times need to be calculated. But the approaches are mathematically equivalent. So in the end, there is no truly meaningful debate here.
johnr is offline  
March 28th, 2013, 05:10 AM   #25
Senior Member
 
Joined: Mar 2012

Posts: 572
Thanks: 26

Re: Old King Collatz

Quote:
Originally Posted by johnr
But you have to do essentially the same amount of calculation to determine which rule to apply out of what is actually an infinity of rules. So even what the next rule is would at times need to be calculated. But the approaches are mathematically equivalent. So in the end, there is no truly meaningful debate here.
I agree, in terms of computation of calculation there is no gain, but I'm trying to understand structure, not create a computer program.

There may be an infinity of rules, but we have already stated the form they all take (because we can define the series 16n+5, 64n+21, 256n+85 etc). On that basis I still think it is helpful to start picking out the different ways that the numbers resolve into series for this reason:

1, 3, 1, 7, 9, 11, 3, 15, 17, 19 looks like quite a messy, chaotic series.

but once you start breaking it down it becomes apparent that what you have is several iterations of 3, 7, 11, 15... and several interlocking iterations of 1, 9, 17 (though I need to go a bit further looking at how some of the latter ones work). And we need to understand how the 8n+5 numbers "output" into 8n+1, 3 or 7 numbers if there is to be any chance of dismissing loops. (See following note also). So it's no good just knowing that an 8n+5 number will map to some 8n+1, 3 or 7 number, we need to know more about the mechanics of this mapping.
Hedge is offline  
March 28th, 2013, 05:12 AM   #26
Senior Member
 
Joined: Mar 2012

Posts: 572
Thanks: 26

Re: Old King Collatz

Quote:
Originally Posted by johnr
So we don't have to ask any questions per se about numbers of the form 8x, 8x+2, 8x+4, 8x+5 or 8x+6, even though they will be implicated in other mappings and of course are all part of the conjecture in their own right. So IF someone can come up with some abstract inductive or whatever proof that all numbers of the forms 8x+1, 8x+3 and 8x+7 eventually map to 1, the others come for free and we are done.
I think the problem is that it would be impossible* to prove that if we couldn't first dismiss the possibility of 8n+5 numbers looping back onto themselves - so it's a circular argument of the form "If we could prove all 8x + 1, 3, 7 numbers map to 1 (which would involve showing that no loops are possible) we could dismiss the possibility of loops."

*Because any possible algorithm mapping 8n+1, 3 and 7 numbers to 1 would have to include analysis of how 8n+5 numbers map back to 8n+1, 3, 7 numbers.
Hedge is offline  
March 28th, 2013, 05:35 AM   #27
Math Team
 
Joined: Apr 2012

Posts: 1,579
Thanks: 22

Re: Old King Collatz

Quote:
Originally Posted by Hedge
Quote:
Originally Posted by johnr
So we don't have to ask any questions per se about numbers of the form 8x, 8x+2, 8x+4, 8x+5 or 8x+6, even though they will be implicated in other mappings and of course are all part of the conjecture in their own right. So IF someone can come up with some abstract inductive or whatever proof that all numbers of the forms 8x+1, 8x+3 and 8x+7 eventually map to 1, the others come for free and we are done.
I think the problem is that it would be impossible* to prove that if we couldn't first dismiss the possibility of 8n+5 numbers looping back onto themselves - so it's a circular argument of the form "If we could prove all 8x + 1, 3, 7 numbers map to 1 (which would involve showing that no loops are possible) we could dismiss the possibility of loops."

*Because any possible algorithm mapping 8n+1, 3 and 7 numbers to 1 would have to include analysis of how 8n+5 numbers map back to 8n+1, 3, 7 numbers.
Of course any loop that does occur would likely include numbers of the form 8x+5 just as they would DEFINITELY include evens. But we know that all evens will eventually boil down to odds. So if all the odds go to 1, so will all the evens. Odds of the form 8x+5, meanwhile, will go to another odd that some odd of the form 8x+1, 8x+3 or 8x+7 go to. Consider the "column" 3, 13, 53, 213, ... Then next odd that 3 will reach is 5. And that is the next odd that ALL of the numbers in this column will reach. So if 3 eventually reaches 1, so will all these 8x+5 odds, as they simply get to the same next odd that 3 does by first mapping into numbers that equal 5 times ever higher powers of 2, and those powers of 2 "burn off" eventually leaving 5 by the 2n->n rule. Conversely, if any of these numbers loop in a way that prevents them from going to 1, they all do, including 3. Same with any path that leads to an infinitely increasing series. If one is on such a path, they all are, since after they each take their slightly differing paths to 5, they are all at that point ON THE SAME PATH.

Exactly the same argument can be made for any number of the form 8x+5.
johnr is offline  
March 28th, 2013, 05:57 AM   #28
Senior Member
 
Joined: Mar 2012

Posts: 572
Thanks: 26

Re: Old King Collatz

Firstly let's say that either approach might have merits depending on the overall approach.

However secondly, I basically agree with this

Quote:
Originally Posted by johnr
Consider the "column" 3, 13, 53, 213, ... Then next odd that 3 will reach is 5. And that is the next odd that ALL of the numbers in this column will reach. So if 3 eventually reaches 1, so will all these 8x+5 odds, as they simply get to the same next odd that 3 does by first mapping into numbers that equal 5 times ever higher powers of 2, and those powers of 2 "burn off" eventually leaving 5 by the 2n->n rule. Conversely, if any of these numbers loop in a way that prevents them from going to 1, they all do, including 3.
But this only considers the onward path, not the path by which we reach 3, 13, 53, 213 in the first place. I just can't see how you could show that all numbers will go on to reach 1 without showing that if you start from the base number in a 4n+1 series (3 in this case), you can't loop back to a higher point in that series. So we know that the output is the same for any number in a series of that kind, but we need to know what rules apply that would prevent us subsequently reaching a different number in that same series. And for that you need more than "all 8n+5 numbers are equivalent to an 8n+1,3,7 number" - you need the rules of all these transforms:

from 8n+7 to 8n+3 numbers (via other 8n+7 numbers)
from 8n+3 numbers to 8n+5 and 8n+1 numbers
from 8n+1 numbers back to 8n +3, 5, 7 numbers (via other 8n+1 numbers)
From 8n+5 numbers to 8n+1, 3, 7 numbers

If you don't have clear rules for the last of these, you can't eliminate loops, and if you can't eliminate loops you can't prove you will get to 1. I think it is feasible to codify all of these transforms, but am not sure there whether or not there is a way of approaching that proof from there, as the rules don't mesh in a way that I can clearly see taking us forwards.
Hedge is offline  
March 28th, 2013, 06:09 AM   #29
Senior Member
 
Joined: Mar 2012

Posts: 572
Thanks: 26

Re: Old King Collatz

Another way of putting this - it's easy to codify most of the transforms I mentioned without reference to even numbers, and that's why we can 'ignore them'.

But I don't think it is as easy to 'ignore' the 8n+5 numbers, because any transform that goes via them will need to follow two distinct sets of rules - one to get you to a 8n+5 number, then one to get you to the 8n+1, 3 or 7 number that that can be boiled down to.

I do see what you're saying, I just think there is a danger of ignoring an important part of the overall picture if you just treat 8n+5 numbers as being 'eliminated from enquiries'. The two easiest transforms to codify are the ones from 8n+1 and 8n+ 7*. The two hardest are from 8n+3 and 8n+5.
Hedge is offline  
March 28th, 2013, 07:22 AM   #30
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 Hedge
I do see what you're saying, I just think there is a danger of ignoring an important part of the overall picture if you just treat 8n+5 numbers as being 'eliminated from enquiries'. The two easiest transforms to codify are the ones from 8n+1 and 8n+ 7*. The two hardest are from 8n+3 and 8n+5.
4n+1 -> 3n+1, so 8n+1 and 8n+5 can't be the smallest Collatz failure. 8n+7 goes to 27n+26. I'm not sure why you say 8n+1 and 8n+7 are easy while the other two are hard.
CRGreathouse 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.