4 ms·

Collatz's Ant

102 points by Fibra 1y ago

keepamovin 1y ago
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)
pvg 1y ago
The previous piece previous thread https://news.ycombinator.com/item?id=42479375 https://news.ycombinator.com/item?id=42479375
cdaringe 1y ago
I didnt know what i was getting into but i loved it
berlinbrowndev 1y ago
I love cellular automata projects like this.
- 1024core 1y ago
  Now if someone could figure out a link between this and Conway's Game of Life...
lapetitejort 1y ago
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.
- InfoSecErik 1y ago
  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.
  - lapetitejort 1y ago
    I ran some calculations looking to see if there were patterns to the next lowest number (call that number x) and could not quickly find any. So even if 7 + k*2^n follows a predicable path to its next lowest number, that number is not currently predictable. Of course, if you can identify which n satisfies the equation x = s + k*2^n for some value of n and some "base" value s (7 is the base value in the previous example), you can predict the path of that number. As an example, take 7 + 4*2*7 = 519. Its next lowest number is 329. 329 = 5 + 81*2^2. So for 329, s=5, k=81, n=2. So we know 329 will only take two steps to reach 247.
    - kr99x 1y ago
      In my phrasing, 128k + 7 -> 81k + 5 for all positive integers k. Pick a power of 3 n to be the coefficient for k on the right/reduced side, and then the left side will have at least one valid reducing form with coefficient power of 2 f(n) = ⌊n·log2(3)⌋+1. If there is more than one, they will have different constants. Each multiplication immediately has a division (you already got this part), and there must be a final division which is not immediately preceded by a multiplication because (3x + 1)/2 > x for all positive integers (that is, if you multiply once and then divide once, you will always be larger than just before those two things, so an "extra" division is needed to reduce). This means that there must always be at least one less multiplication than division, so the initial condition is one division and zero multiplications - the even case with n = 0. Then for n = 1 you need 2 divisions, which works because 2^2 > 3^1. Then for n = 2 you need 4 divisions, because 2^3 < 3^2 so 3 divisions is not enough. This is where f(n) comes in, to give you the next power of 2 to use/division count for a given n. When you do skip a power of 2, where f(n) jumps, you get an "extra" division, so at 16k + 3 -> 9k + 2 you are no longer "locked in" to only the one form, because there is now an "extra" division which could occur at any point in the sequence... Except it can't, because you can't begin a reducing sequence with the complete form of a prior reducing sequence, or else it would "already reduce" before you finish operating on it, and it so happens that there's only one non-repeating option at n=2. At n = 0, you just get D (division). At n = 1, you have an unsplittable M (multiply) D pair MD and an extra D. The extra D has to go at the end, so your only option is MDD. At n = 2, you appear to have three options for arranging your MD MD D and D: DMDMDD, MDDMDD, and MDMDDD. But DMDMDD starts with D so isn't valid, and MDDMDD starts with MDD so also isn't valid, leaving just MDMDDD. At n = 3 there are finally 2 valid forms, 32k + 11 -> 27k + 10 and 32k + 23 -> 27k + 20, and you can trace the MD patterns yourself if you like by following from the k = 0 case. The constants don't even actually matter to the approach. If there are enough 2^x k - > 3^y k forms when n goes off to infinity, which it sure looks like there are though I never proved my infinite sum converged, you have density 1 (which isn't enough to prove all numbers reduce) and this angle can't do any better.
standardly 1y ago
The conjecture holds up through 2^68. Can't we just call it there? Lol I'm obviously being obtuse, but really is there some reason to think there would be an exception at sufficiently large integers? It's hard to even imagine that one wouldn't. edit: I'm in way over my head. Disregard me :)
- WhitneyLand 1y ago
  It’s a fair question. Two things: 1. It does happen. These conjectures can fall apart after seeming like a lock: https://en.m.wikipedia.org/wiki/Mertens_conjecture https://en.m.wikipedia.org/wiki/Mertens_conjecture 2. Even if it is true, the process of proving can yield interesting insights.
  - standardly 1y ago
    That's pretty mind-blowing. Hey thanks for replying. Mathematics is a tough subject to take interest in as a layman, but I still enjoy it for some reason.

102 points by Fibra 1y ago

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)

pvg 1y ago

The previous piece previous thread https://news.ycombinator.com/item?id=42479375 https://news.ycombinator.com/item?id=42479375

cdaringe 1y ago

I didnt know what i was getting into but i loved it

berlinbrowndev 1y ago

I love cellular automata projects like this.

1024core 1y ago
Now if someone could figure out a link between this and Conway's Game of Life...

lapetitejort 1y ago

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.

InfoSecErik 1y ago
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.
- lapetitejort 1y ago
  I ran some calculations looking to see if there were patterns to the next lowest number (call that number x) and could not quickly find any. So even if 7 + k*2^n follows a predicable path to its next lowest number, that number is not currently predictable. Of course, if you can identify which n satisfies the equation x = s + k*2^n for some value of n and some "base" value s (7 is the base value in the previous example), you can predict the path of that number. As an example, take 7 + 4*2*7 = 519. Its next lowest number is 329. 329 = 5 + 81*2^2. So for 329, s=5, k=81, n=2. So we know 329 will only take two steps to reach 247.
  - kr99x 1y ago
    In my phrasing, 128k + 7 -> 81k + 5 for all positive integers k. Pick a power of 3 n to be the coefficient for k on the right/reduced side, and then the left side will have at least one valid reducing form with coefficient power of 2 f(n) = ⌊n·log2(3)⌋+1. If there is more than one, they will have different constants. Each multiplication immediately has a division (you already got this part), and there must be a final division which is not immediately preceded by a multiplication because (3x + 1)/2 > x for all positive integers (that is, if you multiply once and then divide once, you will always be larger than just before those two things, so an "extra" division is needed to reduce). This means that there must always be at least one less multiplication than division, so the initial condition is one division and zero multiplications - the even case with n = 0. Then for n = 1 you need 2 divisions, which works because 2^2 > 3^1. Then for n = 2 you need 4 divisions, because 2^3 < 3^2 so 3 divisions is not enough. This is where f(n) comes in, to give you the next power of 2 to use/division count for a given n. When you do skip a power of 2, where f(n) jumps, you get an "extra" division, so at 16k + 3 -> 9k + 2 you are no longer "locked in" to only the one form, because there is now an "extra" division which could occur at any point in the sequence... Except it can't, because you can't begin a reducing sequence with the complete form of a prior reducing sequence, or else it would "already reduce" before you finish operating on it, and it so happens that there's only one non-repeating option at n=2. At n = 0, you just get D (division). At n = 1, you have an unsplittable M (multiply) D pair MD and an extra D. The extra D has to go at the end, so your only option is MDD. At n = 2, you appear to have three options for arranging your MD MD D and D: DMDMDD, MDDMDD, and MDMDDD. But DMDMDD starts with D so isn't valid, and MDDMDD starts with MDD so also isn't valid, leaving just MDMDDD. At n = 3 there are finally 2 valid forms, 32k + 11 -> 27k + 10 and 32k + 23 -> 27k + 20, and you can trace the MD patterns yourself if you like by following from the k = 0 case. The constants don't even actually matter to the approach. If there are enough 2^x k - > 3^y k forms when n goes off to infinity, which it sure looks like there are though I never proved my infinite sum converged, you have density 1 (which isn't enough to prove all numbers reduce) and this angle can't do any better.

standardly 1y ago

The conjecture holds up through 2^68. Can't we just call it there? Lol I'm obviously being obtuse, but really is there some reason to think there would be an exception at sufficiently large integers? It's hard to even imagine that one wouldn't. edit: I'm in way over my head. Disregard me :)

WhitneyLand 1y ago
It’s a fair question. Two things: 1. It does happen. These conjectures can fall apart after seeming like a lock: https://en.m.wikipedia.org/wiki/Mertens_conjecture https://en.m.wikipedia.org/wiki/Mertens_conjecture 2. Even if it is true, the process of proving can yield interesting insights.
- standardly 1y ago
  That's pretty mind-blowing. Hey thanks for replying. Mathematics is a tough subject to take interest in as a layman, but I still enjoy it for some reason.