5 ms·

At some point I considered doing a computational search for cycles (perhaps using a SAT solver or something similar), but then I found this on Wikipedia: > The

At some point I considered doing a computational search for cycles (perhaps using a SAT solver or something similar), but then I found this on Wikipedia: > 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.

pclmulqdq 4y ago
I went down the same line of thought as you when this problem nerd sniped me 5 years ago (and periodically over the last 5 years). I actually now think you may be able to do a computer proof that there are no trivial cycles other than 1 with a clever construction of large integers that lets you consider them in chunks, but I don't think there's any chance of finding a cycle with computation absent some weird number theory. Edit: The cycle length seems to have gotten longer since I last checked.
- jiggawatts 4y ago
  The last time I wasted some time on this I had a similar notion: "start big" with numbers on the order of 1 million bits and try and demonstrate that different sections of those bits (prefix,middle,suffix) change according to some pattern that can then be generalised "down" to just 64 bits, which has been manually tested.
resource0x 4y ago
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("")
vimax 4y ago
I think the cycles are something of a distraction. Ultimately the problem comes down to this. 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)

pclmulqdq 4y ago

I went down the same line of thought as you when this problem nerd sniped me 5 years ago (and periodically over the last 5 years). I actually now think you may be able to do a computer proof that there are no trivial cycles other than 1 with a clever construction of large integers that lets you consider them in chunks, but I don't think there's any chance of finding a cycle with computation absent some weird number theory. Edit: The cycle length seems to have gotten longer since I last checked.

jiggawatts 4y ago
The last time I wasted some time on this I had a similar notion: "start big" with numbers on the order of 1 million bits and try and demonstrate that different sections of those bits (prefix,middle,suffix) change according to some pattern that can then be generalised "down" to just 64 bits, which has been manually tested.

resource0x 4y ago

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("")

vimax 4y ago

I think the cycles are something of a distraction. Ultimately the problem comes down to this. 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)