collatz-conjecture-iter.py -- simplest Collatz conjecture iterator in python

collatz-conjecture-iter.py

# collatz-conjecture-iter.py -- simplest Collatz conjecture iterator in python
# Author: Serg G. Brester aka sebres

import math

f = lambda x: 3*x+1 if x & 1 else x/2

def fcci(x):
  """single collatz conjecture iteration starting by given x
  """
  m = x
  i = 0
  while x & (x-1) != 0: # not power of two
    x = f(x); i+=1
    if x > m: m = x
  n = int(math.log(x, 2))
  return (n, i, m)

def fci(x):
  """single collatz conjecture iteration starting by given x,
  outputs a result in text form
  """
  r = fcci(x)
  print("reached 2**%s after %s iter(s), max: %s" % r)

def fct(x, maxn=10, maxstep=2, maxmfact=10):
  """tests collatz conjecture starting by given x, where n (power of two) up to maxn,
  outputs a result in text form
  """
  n = 0; m = x
  while n < maxn:
    r = fcci(x)
    if (not n or n < r[0] and n+maxstep >= r[0]) and x != 2**r[0]: # new known power of n
      n = r[0]
      print("x = %s\n\treached 2**%s after %s iter(s), max: %s" % ((x,)+r))
    if m*maxmfact < r[2]: # new known max (at least two times larger as last known).
      m = r[2]
      print("\tnew known interim max: %s" % m)
    x += 2
  
# Examples:

# >>> fci(7)
# reached 16 == 2**4 after 12 iter(s), max: 52
# >>> fci(27)
# reached 16 == 2**4 after 107 iter(s), max: 9232
# >>> fci(2**32-1)
# reached 16 == 2**4 after 447 iter(s), max: 3706040377703680
# >>> fci(2**64-1)
# reached 16 == 2**4 after 859 iter(s), max: 6867367640585024969315698178560
# >>> fci(2**64+1)
# reached 16 == 2**4 after 479 iter(s), max: 55340232221128654852

# >>> fci(2**(10**4)-1)
# reached 16 == 2**4 after 134400 iter(s), max: 3e4771 (number with 4.7K zeros)
# >>> fci(2**(10**5)-1)
# reached 16 == 2**4 after 1344922 iter(s), max: 2e47712 (number with 48K zeros)

# # some "large" prime:
# >>> fci(21195711*(2**143630)-1);
# reached 16 == 2**4 after 1933551 iter(s), max: 4e68536 (number with 68K zeros)

# # results reached other power of two:
# >>> fci((2**64-1)^(3**33))
# reached 1024 == 2**10 after 434 iter(s), max: 70018874346777313300
# >>> fci((2**64-1)^(3**67))
# reached 1024 == 2**10 after 714 iter(s), max: 92709463147887419037572212592868
# >>> fci((3**67)^(7**29))
# reached 1024 == 2**10 after 714 iter(s), max: 352006232164377918748736081217028
# >>> fci((3**67)^(7**48))
# reached 1024 == 2**10 after 771 iter(s), max: 55055052221586488638944101534385438606184

# # simple search of next power of two (fct results):
# >>> fct(7, 25)
# x = 7
#         reached 2**4 after 12 iter(s), max: 52
#         new known interim max: 160
# x = 21
#         reached 2**6 after 1 iter(s), max: 64
#         new known interim max: 9232
# x = 75
#         reached 2**8 after 6 iter(s), max: 340
# x = 151
#         reached 2**10 after 5 iter(s), max: 1024
#         new known interim max: 250504
# x = 1365
#         reached 2**12 after 1 iter(s), max: 4096
#         new known interim max: 6810136
# x = 5461
#         reached 2**14 after 1 iter(s), max: 16384
# x = 14563
#         reached 2**16 after 3 iter(s), max: 65536
#         new known interim max: 106358020
#         new known interim max: 1570824736
# x = 87381
#         reached 2**18 after 1 iter(s), max: 262144
#         new known interim max: 17202377752
# x = 184111
#         reached 2**20 after 13 iter(s), max: 1864132
# x = 932067
#         reached 2**22 after 3 iter(s), max: 4194304