EKG sequence convergence: Difference between revisions
Content deleted Content added
→{{header|Python}}: Moved to example it applies to. |
→Python: Using prime factor generation: Removed. Even if fixed it wouldn't be best. |
||
Line 304: | Line 304: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
===Python: Using prime factor generation=== |
|||
{{incorrect|Python|EKG(10) produces: EKG(10): 1, 2, 4, 6, 3, 9, 12, 8, 10, 5}} |
|||
<lang python>from itertools import count, islice, takewhile |
|||
from functools import lru_cache |
|||
primes = [2, 3, 5, 7, 11, 13, 17] # Will be extended |
|||
@lru_cache(maxsize=2000) |
|||
def pfactor(n): |
|||
# From; http://rosettacode.org/wiki/Count_in_factors |
|||
if n == 1: |
|||
return [1] |
|||
n2 = n // 2 + 1 |
|||
for p in primes: |
|||
if p <= n2: |
|||
d, m = divmod(n, p) |
|||
if m == 0: |
|||
if d > 1: |
|||
return [p] + pfactor(d) |
|||
else: |
|||
return [p] |
|||
else: |
|||
if n > primes[-1]: |
|||
primes.append(n) |
|||
return [n] |
|||
def next_pfactor_gen(): |
|||
"Generate (n, set(pfactor(n))) pairs for n == 2, ..." |
|||
for n in count(2): |
|||
yield n, set(pfactor(n)) |
|||
def EKG_gen(start=2): |
|||
"""\ |
|||
Generate the next term of the EKG together with the minimum cache of |
|||
numbers left in its production; (the "state" of the generator). |
|||
""" |
|||
def min_share_pf_so_far(pf, so_far): |
|||
"searches the unused smaller number prime factors" |
|||
nonlocal found |
|||
for index, (num, pfs) in enumerate(so_far): |
|||
if pf & pfs: |
|||
found = so_far.pop(index) |
|||
break |
|||
else: |
|||
found = () |
|||
return found |
|||
yield 1, [] |
|||
last, last_pf = start, set(pfactor(start)) |
|||
pf_gen = next_pfactor_gen() |
|||
# minimum list of prime factors needed so far |
|||
so_far = list(islice(pf_gen, start)) |
|||
found = () |
|||
while True: |
|||
while not min_share_pf_so_far(last_pf, so_far): |
|||
so_far.append(next(pf_gen)) |
|||
yield found[0], [n for n, _ in so_far] |
|||
last, last_pf = found |
|||
#%% |
|||
def find_convergence(ekgs=(5,7), limit=1_000): |
|||
"Returns the convergence point or zero if not found within the limit" |
|||
ekg = [EKG_gen(n) for n in ekgs] |
|||
for e in ekg: |
|||
next(e) # skip initial 1 in each sequence |
|||
differ = list(takewhile(lambda state: not all(state[0] == s for s in state[1:]), |
|||
islice(zip(*ekg), limit-1))) |
|||
ldiff = len(differ) |
|||
return ldiff + 2 if ldiff < limit-1 else 0 |
|||
#%% |
|||
if __name__ == '__main__': |
|||
for start in 2, 5, 7: |
|||
print(f"EKG({start}):", str([n[0] for n in islice(EKG_gen(start), 10)])[1: -1]) |
|||
print(f"\nEKG(5) and EKG(7) converge at term {find_convergence(ekgs=(5,7))}!")</lang> |
|||
{{out}} |
|||
<pre>EKG(2): 1, 2, 4, 6, 3, 9, 12, 8, 10, 5 |
|||
EKG(5): 1, 5, 10, 2, 4, 6, 3, 9, 12, 8 |
|||
EKG(7): 1, 7, 14, 2, 4, 6, 3, 9, 12, 8 |
|||
EKG(5) and EKG(7) converge at term 21!</pre> |
|||
===Python: Using math.gcd=== |
===Python: Using math.gcd=== |
||
If this alternate definition of function EKG_gen is used then the output would be the same as above. |
If this alternate definition of function EKG_gen is used then the output would be the same as above. |