Symbolically searching for a counter-example to the Collatz Conjecture. A more efficient version of collatzc.py, written in vlang, evaluates 1e6 paths per second. Note you must edit vlang to make fractions expose their n and d, see https://github.com/vlang/v/pull/11018

collatz.v

// The Simplest Math Problem No One Can Solve
// https://www.youtube.com/watch?v=094y1Z2wpJg
// https://en.wikipedia.org/wiki/Collatz_conjecture
// I'm looking for loops by checking every positive integer (1, 2, 3...)
// and I'm using the binary representation (0b0, 0b10, 0b11, 0b100, ...)
// as an up and down path of a collatz loop where '1' means (3x+1)/2 and 
// '0' means x/2 . `frac_follow_path` calculates what should be the starting
// value based on that collatz loop path, and if that's an integer - 
// we found a loop.
// Problems so far:
// 1. At 2B, vlang int (i32) gets stuck
// 2. 357913941 => found_x is 1. But that was just a 1010... I hit because I resumed
//    right after I allowed found_x.n to be 1 as a solution for testing.
// 3. At 36,191,195,499 - I gave up. Wikipedia says the loop is at least 1.7e7 steps long.
//    I only got up to ~35 steps.

import math.fractions
import time


fn frac_follow_path(path i64) (fractions.Fraction) {
  // When closing a loop, x = Ax + B
  // We follow the path by updating the coefficients A and B.
  // In the end we calculate what should be the starting value: x = B / (1 - A)
  one := fractions.fraction(1, 1)
  two := fractions.fraction(2, 1)
  three := fractions.fraction(3, 1)
  // Start with just `x` => A = 1, B = 0
  mut ax := fractions.fraction(1, 1)
  mut b := fractions.fraction(0, 1)
  mut step := path
  for ;; {
    op_index := step % 2
    // println('${op_index} ax: ${ax} b: ${b}')
    step = step >> 1
    if step == 0 {
      // The leftmost bit is always `1`, to allow us
      // to use `>>` from the right digit to left.
      // Because apparently getting the leftmost digit is complicated.
      // Also - if we went right to left, how else would we know how many
      // trailing (left) zeroes are there?
      break
    }
    if op_index == 0 {
      ax = ax / two
      b = b / two
    } else {
      // Every 3x+1 must be followed by a x/2.
      // So just do that and then we don't need to verify the binary sequence
      // is legal (e.g. with no repeat 1s in it)
      ax = ax * three / two
      b = (b * three + one) / two
    }
  }
  
  found_x := b / (one - ax)
  return found_x
}

fn find_loops() {
  mut sw := time.new_stopwatch()
  // Start evaluating at path `2` to test this function.
  // Or continue wherever the execution left off.
  mut path := i64(357913941)
  for ;; {
    since := sw.elapsed().seconds()
    if since > 5 {
      // Report status every 5 seconds
      println('still looking, path: ${path}')
      sw.restart()
    }
    found_x := frac_follow_path(path)
    found_x.reduce()
    // found_x.n == 1, 2, or 4 for any sequence of 10, 1010, 101010, ...
    if found_x.n > 4 && found_x.d == 1 {
      println('Is this it? found_x: ${found_x.n}, path: ${path}')
      return
    }
    path++
  }
}

println('Starting collatz loop search')

// The path is from right to left, with a leftmost `1` terminator.
// path 5 = 0b101 => [0, 1] => ⬇️⬇️⬆️ => found_x = 1
// path 6 = 0b110 => [1, 0] => ⬇️⬆️⬇️ => found_x = 2
// found_x = 4 is invalid since I made "1" always do (3x+1)/2 instead of just 3x+1 => ⬇️⬆️⬆️
// In practice this is ok, because the left most 1 is a rotation of a previously evaluated case.
assert frac_follow_path(5) == fractions.fraction(1, 1)
assert frac_follow_path(6) == fractions.fraction(2, 1)
assert frac_follow_path(7) == fractions.fraction(-1, 1)
find_loops()