Hacker News Reader

Comment by anonymous2024 | Hacker News Reader

anonymous2024

Someone has also noticed another curiosity: The number of bits of the biggest number (in binary notation) in a path is less than the number of bits of the initial number (in binary notation) * 3 + 1

View on HN

If that were true, then every number would lead to a cycle (possibly a different one from 1-4-2). It would make the decision problem (whether a given initial number leads to 1) decidable, and the Collatz conjecture finitely refutable.

This isn't true. Take 9_A = 1001_2. 28_A = 11100_2, which is 5 bits long (3 set). The biggest number in this path is 52_A = 110100_2, which is 6 bits long (3 set). 5 ≯ 6, and 3 ≯ 3: neither of my interpretations of your statement holds.

Not to say their statement is true but I don't see any reason to count the initial zeroes.

11100 == 111 == 11100000000, in terms of the next odd iteration

Even numbers don't really count in the process surely? All collatz does is essentially ignore those zeroes

Valid point: it depends what invariants you're trying to construct. Considering only the odd elements of the sequence does yield a slightly different set of insights compared to other approaches. (9 / 28 / 52 still describe a counterexample to the proposed invariant, even in this scheme.)

There is another interpretation, reading "bits" as "set bits" and assuming that textual description (especially the operator "of the") has a higher precedence than multiplication, then your initial number is 9 with 2 bits set, and the largest number is 52 with 3 bits set, and 3 < 2 * 3 + 1 = 7.

What I understood was: 9_A = 1001_2 needs 4 bits, set or not set as the minimum length of the binary representation. 52_A = 110100_2 needs 6 bits 6 bits is less than 4*3+1=13 bits

At that point, the conjecture's just numerology: 27 takes 5 bits, and 9232 takes 14 bits (two shy of 3×5+1 = 16). 27 is the peak of the average ratio between start and maximum, because the +1s are so significant when the numbers are small: past that point, we're relying on extreme outlier behaviour to get each new high-score. Those only start showing up often enough to matter once we get into the thousands.

Plugging in values from OEIS A006884, it looks like the maximum ratio between the maximum and starting values goes down until around 4255, then picks up again, gradually increasing from there. Eyeballing the growth rate, I suspect there's a counterexample to this interpretation somewhere before 10^1000. (Does anyone have an element of A006884 greater than 2358909599867980429759? That's 140 bits maximum to 71 bits starting.)

Do you have a source for that?

Reply on news.ycombinator.com