If they reach a value below 200 then they surely will reach 1 (since all sub 200 sequences have been brute forced). What am I missing?
Looking at the paper, it basically says: the orbit starting with N dips to f(N) for "most" N, where f is a function that goes to infinity.
So, you can't pick f(N) = 200, but you can at least pick an f(N) that goes to infinity really slowly--a lot more slowly than previous results (f(N) = ~N^0.7924 is mentioned as a previous result).
* This allowed him to draw conclusions along the lines of 99% of starting values greater than 1 quadrillion eventually reach a value below 200.
* This allowed him to draw conclusions along the lines of 99% of starting values greater than 1 quadrillion eventually reach 1.
yet the author used the first which seems weird
> The length of a non-trivial cycle is known to be at least 186265759595.
This probably makes it very hard to find a cycle unless we know of some properties of the numbers involved in the cycle.
The algorithm alternates between 2 steps: multiplication by 3 +1 followed by division by a power of 2 (equal to the number of trailing 0 bits; on average it divides by 4), etc. (So on average you multiply by 3, but divide by 4.)
This argument simultanesouly 1) motivates the claim of the conjecture 2) predicts that the cycle length is unlimited (but always finite).
So on average, we multiply a "random" odd number by 3, but divide it by 4.
So yes, it is "mathematically correct" in a very real sense. It's a bit weird that you felt the need to claim it's incorrect, without explaining why.
[1] Think of grouping the integers based on how many bits they take up. We're looking at patterns like [1----1] where each "-" has a 50/50 chance of being 0 or 1. For any given window size, this analysis holds, except for a small number of very pathological edge cases that become vanishingly unlikely for even modest window sizes.
[2] It's common to consider each step only applying to odd numbers, and always dividing until the result is odd again. It's clear that any analysis on this "simplified" version trivially extends to the evens as well.
[3] This shouldn't actually be taken as a given, since we've modified our original bit distribution by multiplying by 3, but it is true, which you'd probably agree with if you played around for a bit with multiplying random bits by 3. You can figure out the distributions of the resulting bits (include the carry bit as well). The highest bit can be wonky, but the probability that the run of zeroes reaches the highest bit vanishes as the window size grows.
Sorry for being terse in my original comment. I should have elaborated.
Neither of these are rigorous demonstrations but without some kind of evidence to indicate the contrary, or a proof, I think OP was right to state that this claim is neither common sense or mathematically correct.
Below is a script you can use to empirically test the bias for yourself (or identify a mistake that I've made):
def count_bits(n):
count = 0
while n:
count += n & 1
n >>= 1
return count
def experiment(count):
count_0_bits = 0
count_1_bits = 0
for i in range(1, count, 2):
num = 3 * i
num >>= 1 # Remove the least significant bit
count_1_bits += count_bits(num)
count_0_bits += num.bit_length() - count_bits(num)
print(f"count: {count}")
print(f"0 bits: {count_0_bits} {count_0_bits / (count_0_bits + count_1_bits)}")
print(f"1 bits: {count_1_bits} {count_1_bits / (count_0_bits + count_1_bits)}")
print("")The obvious flaw I see in your code is that you're starting from 1 and not ignoring the topmost bit, which is also always 1. We know the Collatz conjecture is true up to something like 10^20, which is over 2^66. We've always only been talking about "sufficiently large" numbers. The probability of the top bit affecting the outcome of one step (3n+1, then divide until odd) is (1/2)^66; completely negligible. So starting at 1 will give you a clearly biased answer.
But you're right it needs to be proven. Here's a brief sketch:
To multiply a number N by 3, we can bit-shift once to get 2N, and add it back to the original.
N = 1001101
2N = 10011010
+ ________
3N = 11100111
carry = 0011000
(0 + 0 + 0) = (0, 0) with p = 1/2 * 1/2 * p(carry = 0)
(0 + 0 + 1) = (0, 1) etc.
(0 + 1 + 0) = (0, 1)
(0 + 1 + 1) = (1, 0)
(1 + 0 + 0) = (0, 1) with p = 1/2 * 1/2 * p(carry = 1)
(1 + 0 + 1) = (1, 0) etc.
(1 + 1 + 0) = (1, 0)
(1 + 1 + 1) = (1, 1)
This makes some intuitive sense to me: writing a number in base B, then multiplying by any number M that is relatively prime to B, should "scramble" the digits: M is a generator of the integers modulo B. Write out the digits up to B-1 and multiply by M, you get { 0, 1M, 2M, 3M, ... } which will not repeat digits. The carry digit might complicate things for higher bases, but binary is simple enough that it doesn't matter. Keep in mind, the bias would have to be huge (something like 1.58:1) to overcome the difference between the x3 and /4.
> since the original number had a bias in favor of 1 bits, then that bias carries over when shifted to the left
After adding 1, the lowest 1-bit becomes a 0 (with a carry of 1, which we saw doesn't matter), so the result of 3n+1 is biased in favor of 0 on the low-end, which is why we end up dividing by 4 on average, and not 2.
The highest 1-bit does not matter. You seem to be thinking that a 10-bit number has a bias like "one extra '1' out of 10 bits", but it's much more like "a (1/2)^10 chance of an extra '1'". That bias very quickly becomes negligible for any of the numbers we're talking about.
Edit: The cycle length seems to have gotten longer since I last checked.
Given a number N with prime factors (p1, p2, …pn) And N+1 with prime factors (q1, q2, …qm)
What is the relation between (p1, p2, …pn) and (q1, q2, …qm)