EKG sequence convergence: Difference between revisions

← Older edit Newer edit →

Content deleted Content added

Inline

@@ Line 304: / Line 304: @@
 =={{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===
 If this alternate definition of function EKG_gen is used then the output would be the same as above.