3 ms·

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

by 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.

by Kranar 4y ago

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.