[HN Gopher] Collatz's Ant
___________________________________________________________________
Collatz's Ant
Author : Fibra
Score : 86 points
Date : 2025-04-23 10:52 UTC (12 hours ago)
(HTM) web link (gbragafibra.github.io)
(TXT) w3m dump (gbragafibra.github.io)
| keepamovin wrote:
| 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 wrote:
| The previous piece previous thread
| https://news.ycombinator.com/item?id=42479375
| cdaringe wrote:
| I didnt know what i was getting into but i loved it
| berlinbrowndev wrote:
| I love cellular automata projects like this.
| 1024core wrote:
| Now if someone could figure out a link between this and
| Conway's Game of Life...
| lapetitejort wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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.
| gregschlom wrote:
| 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?
| skulk wrote:
| 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.
| lapetitejort wrote:
| 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.
| kr99x wrote:
| 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.
| prezjordan wrote:
| Potentially useful to you:
| https://en.wikipedia.org/wiki/Collatz_conjecture#As_a_parity...
| standardly wrote:
| 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 wrote:
| 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
|
| 2. Even if it is true, the process of proving can yield
| interesting insights.
___________________________________________________________________
(page generated 2025-04-23 23:01 UTC)