Last active
January 8, 2020 01:47
-
-
Save sebres/2639de7400d00a4e797894b4e1688d81 to your computer and use it in GitHub Desktop.
collatz-conjecture-iter.py -- simplest Collatz conjecture iterator in python
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment