3 ms·

Common sense suggests that the length of the cycle can be greater than any chosen N. The algorithm alternates between 2 steps: multiplication by 3 +1 followed

Common sense suggests that the length of the cycle can be greater than any chosen N. 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).

kccqzy 4y ago
That's neither common sense nor mathematically correct.
- feoren 4y ago
  Take a random[1] odd[2] number and represent it in binary. Its lowest bit is 1. Multiply by 3. The first bit is 1, but the rest have a 50% chance of being 0 and a 50% chance of being 1[3]. Adding 1 (the rest of the 3n+1 step) will flip a sequence like [0111] to [1000]. The number will then be divided by 2^k, where k is the number of trailing zeroes. How many trailing zeroes do we expect? We always start with one. There's a 50% chance the next one will be 0, and if it is, another 50% chance the next one will be, etc. So the average is 1 + 1/2 + 1/4 + 1/8 + 1/16 + ... = 2 trailing zeroes. Dividing off two zeroes in binary is the same as dividing the number by 4. 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.
  - Kranar 4y ago
    Your claim depends on the idea that the set of numbers {3, 9, 15, 21, 27, ...} = {3 * N | for all odd N} have an even distribution of 0s and 1s in their binary representation (ignoring the last digit, which is always a 1). But this claim does not seem like common sense, in fact it's not clear to me that it's true. The algebra suggests to me that the bias in favor of 1 bits scales logarithmically in favor of 1 bits (multiplying by 3 is the same as shifting the number to the left by 1 and adding the original number to it, since the original number had a bias in favor of 1 bits, then that bias carries over when shifted to the left), and a simple Python script I wrote to test this hypothesis on the first billion integers shows just such a bias in favor of the 1 digits. 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("")
    - feoren 4y ago
      It's pointless to argue about what is or is not "common sense", which is why I didn't mention it. I'm only concerned about whether it's correct. 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 Consider a bit somewhere in the middle of a number. It's 0 (p = 0.5) or 1 (p = 0.5). To multiply it by 3, we need to know the bit to its immediate right (to add, same distribution) and the carry bit (distribution not known yet). The 8 possibilities for (carry + bit + neighbor) = (nextCarry, result) are: (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) Out of the top group of 4, there's a 50/50 chance the resulting bit is 0/1. Out of the bottom group of 4, there's a 50/50 chance the resulting bit is 0/1. So the distribution of the carry bit doesn't actually matter: the resulting bit has a 50% chance of being 1, and a 50% chance of being 0. 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.

kccqzy 4y ago

That's neither common sense nor mathematically correct.

feoren 4y ago
Take a random[1] odd[2] number and represent it in binary. Its lowest bit is 1. Multiply by 3. The first bit is 1, but the rest have a 50% chance of being 0 and a 50% chance of being 1[3]. Adding 1 (the rest of the 3n+1 step) will flip a sequence like [0111] to [1000]. The number will then be divided by 2^k, where k is the number of trailing zeroes. How many trailing zeroes do we expect? We always start with one. There's a 50% chance the next one will be 0, and if it is, another 50% chance the next one will be, etc. So the average is 1 + 1/2 + 1/4 + 1/8 + 1/16 + ... = 2 trailing zeroes. Dividing off two zeroes in binary is the same as dividing the number by 4. 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.
- Kranar 4y ago
  Your claim depends on the idea that the set of numbers {3, 9, 15, 21, 27, ...} = {3 * N | for all odd N} have an even distribution of 0s and 1s in their binary representation (ignoring the last digit, which is always a 1). But this claim does not seem like common sense, in fact it's not clear to me that it's true. The algebra suggests to me that the bias in favor of 1 bits scales logarithmically in favor of 1 bits (multiplying by 3 is the same as shifting the number to the left by 1 and adding the original number to it, since the original number had a bias in favor of 1 bits, then that bias carries over when shifted to the left), and a simple Python script I wrote to test this hypothesis on the first billion integers shows just such a bias in favor of the 1 digits. 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("")
  - feoren 4y ago
    It's pointless to argue about what is or is not "common sense", which is why I didn't mention it. I'm only concerned about whether it's correct. 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 Consider a bit somewhere in the middle of a number. It's 0 (p = 0.5) or 1 (p = 0.5). To multiply it by 3, we need to know the bit to its immediate right (to add, same distribution) and the carry bit (distribution not known yet). The 8 possibilities for (carry + bit + neighbor) = (nextCarry, result) are: (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) Out of the top group of 4, there's a 50/50 chance the resulting bit is 0/1. Out of the bottom group of 4, there's a 50/50 chance the resulting bit is 0/1. So the distribution of the carry bit doesn't actually matter: the resulting bit has a 50% chance of being 1, and a 50% chance of being 0. 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.