Trying to symbolically solve the Collatz Conjecture

collatzc.py

"""
The Simplest Math Problem No One Can Solve - YouTube - https://www.youtube.com/watch?v=094y1Z2wpJg
Collatz Conjecture

3x + 1
x / 2


(3x + 1) / 2 = 1.5x + 0.5
3(x/2) + 1 = 1.5x + 1

5 -> 16 -> 8
5 -> 2.5 -> 8.5
7 -> 22
9 -> 28
11 -> 34

- n0 - n1 - ... - n0


To find a loop - we could make guesses at "paths" and "start values".
Or we could use symbolic manipulation to avoid guessing "start values".
But we'd need to solve the equation every time.

x = 3x + 1
-1 = 2x

1 -> 4 -> 2 -> 1
x = 3x + 1
(3x + 1) / 2 = 1.5x + 0.5
(1.5x + 0.5) /  2 = 0.75x + 0.25

x = 0.75x + 0.25
0.25x = 0.25
x = 1

To close a loop - in the end if I know x = Ax + B, I can do
(1 - A)x = B
x = B / (1 - A)
iff x is an integer - I win

lol, after writing this I found a fractional answer:
11/7

"""
import fractions
import time
import collections


ops = [
  lambda x: x // 2,
  lambda x: 3 * x + 1,
]

def frac_follow_path(path):
  # start with `x` => A = 1, B = 0
  ax = fractions.Fraction(1, 1)
  b = fractions.Fraction(0, 1)
  for op_index in path:
    # print(f"{ax} {b}")
    if op_index == 0:
      ax = ax / 2
      b = b / 2
    else:
      ax = ax * 3
      b = b * 3 + 1
  
  maybex = b / (1 - ax)
  return ax, b, maybex


def follow_path(start_value, path):
  x = start_value
  index = 0
  for op_index in path:
    if op_index == 0 and x % 2 == 1:
      raise Exception(f"Odd number getting divided by two. index: {index} x: {x}")
    elif op_index == 1 and x % 2 == 0:
      raise Exception(f"Even number getting 3x+1ed. index: {index} x: {x}")
    x = ops[op_index](x)
  return x


def find_loops():
  options = collections.deque([
    [1, 0],
  ])

  last_update = time.time()
  while options:
    since = time.time() - last_update
    if since > 5:
      print(f"still looking, len(options): {len(options)}, options[0]: {options[0]}")
      last_update = time.time()
    next_up = options.popleft()
    # important to try the shrinker option first, so we don't just explode to infinity
    options.append(next_up + [0])
    options.append(next_up + [1, 0])
    ax, b, maybex = frac_follow_path(next_up)
    if maybex > 1 and maybex.denominator == 1:
      print(f"Is this it? ax: {ax}, b: {b}, maybex: {maybex}")
      return

assert follow_path(1, [1, 0, 0]) == 1

# print(fractions.Fraction(3, 1))
print(frac_follow_path([1, 0, 0]))
find_loops()

After 5 hours running, this was the final output before I killed the process:

still looking, len(options): 87149926, options[0]: [1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0]

A few ways to improve this:

• Port to a faster language
• Parallelize
• Make the options grow more slowly - e.g. just count up in binary. This will use less memory.
• If we find a loop - it should have a ratio of about three 0 to every two 1. E.g. 3^20 ≈ 2^31.7