I've been fiddling with the Collatz Conjecture off and on for years now. I'm convinced I found a pattern that I haven't been able to find mentioned anywhere. Granted, that could be because I lack the mathematical language needed to search for it.
First, I'm going to use an implicit even step after the odd step, as 3*odd + 1 always equals even. If you look at the path a number takes to its next lowest number, for example 5->8->4, visualize it by just looking at the even and odd steps like so: 5->10, you will see that other numbers follow a similar pattern:
9->10
13->10
17->10
What do these number have in common? They follow the pattern 5 + k(2^n) where n is the number of even steps (with the implicit even step, two in this case).
For another example, look at 7:
7->1110100
Seven even steps, so the next number will be 7 + 2^7 = 135:
135->1110100
I'd love to hear if this has been found and documented somewhere. If not, I have additional ramblings to share.
I've been down that road, and it's unfortunately a dead end. You can generate an infinite number of reducing forms, each of which itself covers an infinite number of integers, like 4k + 5 → 3k + 4. Each one covers a fraction of the integers 1/(2^x) where x is the number of division steps in its reducing sequence (and the right hand side is always 3^y where y is the number of multiplying steps). You can't just make 1/2 + 1/4 + 1/8 and so on though (the easy path to full coverage) because sometimes the power of 3 overwhelms the power of 2. There is no 8k → 9k form, because that's not a reduction for all k, so you instead have to go with 16k → 9k. This leaves a "gap" in the coverage, 1/2 + 1/4 + 1/16th. Fortunately, when this happens, you start to be able to make multiple classes for the same x and y pair and "catch up" some, though slower. As an amateur I wrote a whole bunch about this only to eventually discover it doesn't matter - even if you reach 1/1th of the integers by generating these classes out to infinity, it doesn't work. An infinite set of density 1 implies a complementary set of density 0, but a set of density 0 doesn't have to be empty! There can still be finitely many non-reducing numbers which are not in any class, allowing for alternate cycles - you would only eliminate infinite growth as a disproof option.
Mind you, it's almost certain Collatz is true (generating these classes out to 3^20 nets you just over 99% coverage, and by 3^255 you get 99.9999999%) but this approach doesn't work to PROVE it.
I too have been playing with the conjecture for fun. Your insight is interesting because of the appearance of 2^n, given that that always resolves to 1 for all n.
That is correct. I use pseudo-binary to represent the steps the number takes. Simply counting the number of steps is enough to get n, as all steps will have an implicit or explicit even step.
I love that people are working on this. It's inspiring. Thank you for posting. It's interesting if you post a comment about your process, purpose or idea - and maybe a link to code, etc (even tho it's all linked in the post, HN likes comments & discussion)
I've been fiddling with the Collatz Conjecture off and on for years now. I'm convinced I found a pattern that I haven't been able to find mentioned anywhere. Granted, that could be because I lack the mathematical language needed to search for it.
First, I'm going to use an implicit even step after the odd step, as 3*odd + 1 always equals even. If you look at the path a number takes to its next lowest number, for example 5->8->4, visualize it by just looking at the even and odd steps like so: 5->10, you will see that other numbers follow a similar pattern:
9->10
13->10
17->10
What do these number have in common? They follow the pattern 5 + k(2^n) where n is the number of even steps (with the implicit even step, two in this case).
For another example, look at 7:
7->1110100
Seven even steps, so the next number will be 7 + 2^7 = 135:
135->1110100
I'd love to hear if this has been found and documented somewhere. If not, I have additional ramblings to share.
I've been down that road, and it's unfortunately a dead end. You can generate an infinite number of reducing forms, each of which itself covers an infinite number of integers, like 4k + 5 → 3k + 4. Each one covers a fraction of the integers 1/(2^x) where x is the number of division steps in its reducing sequence (and the right hand side is always 3^y where y is the number of multiplying steps). You can't just make 1/2 + 1/4 + 1/8 and so on though (the easy path to full coverage) because sometimes the power of 3 overwhelms the power of 2. There is no 8k → 9k form, because that's not a reduction for all k, so you instead have to go with 16k → 9k. This leaves a "gap" in the coverage, 1/2 + 1/4 + 1/16th. Fortunately, when this happens, you start to be able to make multiple classes for the same x and y pair and "catch up" some, though slower. As an amateur I wrote a whole bunch about this only to eventually discover it doesn't matter - even if you reach 1/1th of the integers by generating these classes out to infinity, it doesn't work. An infinite set of density 1 implies a complementary set of density 0, but a set of density 0 doesn't have to be empty! There can still be finitely many non-reducing numbers which are not in any class, allowing for alternate cycles - you would only eliminate infinite growth as a disproof option.
Mind you, it's almost certain Collatz is true (generating these classes out to 3^20 nets you just over 99% coverage, and by 3^255 you get 99.9999999%) but this approach doesn't work to PROVE it.
I too have been playing with the conjecture for fun. Your insight is interesting because of the appearance of 2^n, given that that always resolves to 1 for all n.
You lost me here: "visualize it by just looking at the even and odd steps like so: 5->10"
Where does the 10 come from?
5 is odd, so that's where the 1 comes from
8 ((5*3+1)/2) is even, so that's where the 0 comes from
4 (8/2) is the end.
That is correct. I use pseudo-binary to represent the steps the number takes. Simply counting the number of steps is enough to get n, as all steps will have an implicit or explicit even step.
The previous piece previous thread https://news.ycombinator.com/item?id=42479375
I love that people are working on this. It's inspiring. Thank you for posting. It's interesting if you post a comment about your process, purpose or idea - and maybe a link to code, etc (even tho it's all linked in the post, HN likes comments & discussion)
I love cellular automata projects like this.
Now if someone could figure out a link between this and Conway's Game of Life...
I didnt know what i was getting into but i loved it