EKG sequence convergence

From Rosetta Code
Revision as of 17:29, 5 August 2018 by PureFox (talk | contribs) (Added Go)
EKG sequence convergence is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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 with a(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, ... the EKG(2) sequence;
  • the sequence starting 1, 3, ... the EKG(3) sequence;
  • ... the sequence starting 1, N, ... the EKG(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
  1. Calculate and show here the first ten members of EKG(2).
  2. Calculate and show here the first ten members of EKG(5).
  3. Calculate and show here the first ten members of EKG(7).
  4. Stretch goal: Calculate and show here at which term EKG(5) and EKG(7) converge.
Reference

Go

<lang go>package main

import "fmt"

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 {

   for _, j := range a {
       if j == b {
           return true
       }
   }
   return false

}

func getState(used [nPrimes]bool) string {

   var tf [15]byte
   for i := 0; i < nPrimes; i++ {
       if used[i] {
           tf[i] = 't'
       } else {
           tf[i] = 'f'
       }
   }
   return string(tf[:])

}

func main() {

   const limit = 100
   starts := [3]int{2, 5, 7}
   var ekg [3][limit]int
   var state [3][limit]string
   for s, start := range starts {
       ekg[s][0] = 1
       ekg[s][1] = start
       var used [nPrimes]bool
   nextMember:
       for n := 2; n < limit; n++ {
           for i := 2; ; i++ {
               // a potential sequence member cannot already have been used
               if !contains(ekg[s][:n], i) {
                   for j, prime := range primes {
                       // must have a factor in common with previous member
                       if i%prime == 0 && ekg[s][n-1]%prime == 0 {
                           ekg[s][n] = i
                           used[j] = true
                           state[s][n] = getState(used)
                           continue nextMember
                       }
                   }
               }
           }
       }
       fmt.Printf("EKG(%d): %v\n", start, ekg[s][:10])
   }
   // now compare EKG(5) and EKG(7) for convergence
   for i := 1; i < limit; i++ {
       if ekg[1][i] == ekg[2][i] && state[1][i] == state[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
  1. %%

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
  1. %%

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!