EKG sequence convergence: Difference between revisions
(→{{header|Go}}: Replaced 15 with nPrimes in getState function.) |
(→{{header|Go}}: Replaced existing solution with improved version - doesn't require primes or state to be stored.) |
||
Line 29: | Line 29: | ||
<lang go>package main |
<lang go>package main |
||
import |
import ( |
||
"fmt" |
|||
"sort" |
|||
const nPrimes = 15 |
|||
) |
|||
var primes = [nPrimes]int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47} |
|||
func contains(a []int, b int) bool { |
func contains(a []int, b int) bool { |
||
Line 44: | Line 43: | ||
} |
} |
||
func |
func gcd(a, b int) int { |
||
for a != b { |
|||
if a > b { |
|||
a -= b |
|||
⚫ | |||
} else { |
} else { |
||
b -= a |
|||
} |
} |
||
} |
} |
||
return |
return a |
||
} |
|||
func areSame(s, t []int) bool { |
|||
le := len(s) |
|||
if le != len(t) { |
|||
return false |
|||
} |
|||
sort.Ints(s) |
|||
sort.Ints(t) |
|||
for i := 0; i < le; i++ { |
|||
if s[i] != t[i] { |
|||
⚫ | |||
⚫ | |||
} |
|||
return true |
|||
} |
} |
||
Line 60: | Line 73: | ||
starts := [3]int{2, 5, 7} |
starts := [3]int{2, 5, 7} |
||
var ekg [3][limit]int |
var ekg [3][limit]int |
||
var state [3][limit]string |
|||
for s, start := range starts { |
for s, start := range starts { |
||
ekg[s][0] = 1 |
ekg[s][0] = 1 |
||
ekg[s][1] = start |
ekg[s][1] = start |
||
var used [nPrimes]bool |
|||
nextMember: |
nextMember: |
||
for n := 2; n < limit; n++ { |
for n := 2; n < limit; n++ { |
||
for i := 2; ; i++ { |
for i := 2; ; i++ { |
||
// a potential sequence member cannot already have been used |
// a potential sequence member cannot already have been used |
||
// and must have a factor in common with previous member |
|||
if !contains(ekg[s][:n], i) && gcd(ekg[s][n-1], i) > 1 { |
|||
ekg[s][n] = i |
|||
continue nextMember |
|||
ekg[s][n] = i |
|||
used[j] = true |
|||
state[s][n] = getState(used) |
|||
continue nextMember |
|||
} |
|||
⚫ | |||
} |
} |
||
} |
} |
||
} |
} |
||
fmt.Printf("EKG(%d): %v\n", start, ekg[s][:10]) |
fmt.Printf("EKG(%d): %v\n", start, ekg[s][:10]) |
||
} |
} |
||
// now compare |
// now compare EKG5 and EKG7 for convergence |
||
for i := 1; i < limit; i++ { |
for i := 1; i < limit; i++ { |
||
if ekg[1][i] == ekg[2][i] && |
if ekg[1][i] == ekg[2][i] && areSame(ekg[1][:i], ekg[2][:i]) { |
||
fmt.Println("\nEKG(5) and EKG(7) converge at term", i+1) |
fmt.Println("\nEKG(5) and EKG(7) converge at term", i+1) |
||
return |
return |
Revision as of 19:04, 5 August 2018
The sequence is of natural numbers defined by:
a(1) = 1
;a(2) = Start = 2
;- for n > 2,
a(n)
shares at least one prime factor witha(n-1)
and is the smallest such natural number not already used.
The sequence is called the EKG sequence (after its visual similarity to an electrocardiogram when graphed).
Variants of the sequence can be generated starting 1, N where N is any natural number larger than one. For the purposes of this task let us call:
- The sequence described above , starting
1, 2, ...
theEKG(2)
sequence; - the sequence starting
1, 3, ...
theEKG(3)
sequence; - ... the sequence starting
1, N, ...
theEKG(N)
sequence.
Convergence
If an algorithm that keeps track of the minimum amount of numbers and their corresponding prime factors used to generate the next term is used, then this may be known as the generators essential state. Two EKG generators with differing starts can converge to produce the same sequence after initial differences.
EKG(N1)
and EKG(N2)
are said to to have converged at and after generation a(c)
if state_of(EKG(N1).a(c)) == state_of(EKG(N2).a(c))
.
- Task
- Calculate and show here the first ten members of
EKG(2)
. - Calculate and show here the first ten members of
EKG(5)
. - Calculate and show here the first ten members of
EKG(7)
. - Stretch goal: Calculate and show here at which term EKG(5) and EKG(7) converge.
- Reference
- The EKG Sequence and the Tree of Numbers. (Video).
Go
<lang go>package main
import (
"fmt" "sort"
)
func contains(a []int, b int) bool {
for _, j := range a { if j == b { return true } } return false
}
func gcd(a, b int) int {
for a != b { if a > b { a -= b } else { b -= a } } return a
}
func areSame(s, t []int) bool {
le := len(s) if le != len(t) { return false } sort.Ints(s) sort.Ints(t) for i := 0; i < le; i++ { if s[i] != t[i] { return false } } return true
}
func main() {
const limit = 100 starts := [3]int{2, 5, 7} var ekg [3][limit]int
for s, start := range starts { ekg[s][0] = 1 ekg[s][1] = start nextMember: for n := 2; n < limit; n++ { for i := 2; ; i++ { // a potential sequence member cannot already have been used // and must have a factor in common with previous member if !contains(ekg[s][:n], i) && gcd(ekg[s][n-1], i) > 1 { ekg[s][n] = i continue nextMember } } } fmt.Printf("EKG(%d): %v\n", start, ekg[s][:10]) }
// now compare EKG5 and EKG7 for convergence for i := 1; i < limit; i++ { if ekg[1][i] == ekg[2][i] && areSame(ekg[1][:i], ekg[2][:i]) { fmt.Println("\nEKG(5) and EKG(7) converge at term", i+1) return } } fmt.Println("\nEKG5(5) and EKG(7) do not converge within", limit, "terms")
}</lang>
- Output:
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
Python
<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(pf_gen.__next__()) 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: e.__next__() # 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>
- Output:
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!