Terms of the EKG sequence

Question

Introduction

The EKG sequence begins with 1 and 2, then the rule is that the next term is the smallest positive integer not already in the sequence and whose common factor with the last term is greater than 1 (they are not coprimes).

The first terms are:

1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, ...

It's called EKG because the graph of its terms is quite similar to an EKG.

It's sequence A064413 in the OEIS.

Challenge

You have to write a function which takes an integer n as input and outputs how many of the n first terms of the sequence are greater than n.

As the sequence's rule begins with the third term, the input integer has to be greater or equal to 3. For example, given input 10 the output is 1 because the 7th term is 12 and none of the other first ten terms exceed 10.

Test cases

3 -> 1

10 -> 1

100 -> 9

1000 -> 70

Rules

• For integers lower than 3, the function may output 0 or an error code.
• No other particular rules except: it's code golf, the shorter the better!

Answer 1

Jelly, 20 19 18 bytes

S‘gṪ’ɗƇḟ¹Ṃṭ
1Ç¡>¹S

This is a full program.

Try it online!

How it works

1Ç¡>¹S       Main link. Argument: n (integer)

1            Set the return value to 1.
 Ç¡          Call the helper link n times.
   >¹        Compare the elements of the result with n.
     S       Take the sum, counting elements larger than n.


S‘gṪ’ɗƇḟ¹Ṃṭ  Helper link. Argument: A (array or 1)

S            Take the sum of A.
 ‘           Increment; add 1.
     ɗƇ      Drei comb; keep only elements k of [1, ..., sum(A)+1] for which the
             three links to the left return a truthy value.
  g              Take the GCD of k and all elements of A.
   Ṫ             Tail; extract the last GCD.
    ’            Decrement the result, mapping 1 to 0.
       ḟ¹    Filterfalse; remove the elements that occur in A.
         Ṃ   Take the minimum.
          ṭ  Tack; append the minimum to A.

Note that the generated sequence is \$[1, \mathbf{0}, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, \dots]\$. Since calling the helper link \$n\$ times generates a sequence of length \$n + 1\$, the \$0\$ is practically ignored.

Answer 2

Perl 6, 66 63 59 58 bytes

-4 bytes thanks to Jo King

{sum (1,2,{+(1...all *gcd@_[*-1]>1,*∉@_)}...*)[^$_]X>$_}

Try it online!

Too slow on TIO for n = 1000.

Answer 3

Husk, 16 bytes

#>¹↑¡§ḟȯ←⌋→`-Nḣ2

Try it online!

Explanation

#>¹↑¡§ḟȯ←⌋→`-Nḣ2  Implicit input, say n=10
              ḣ2  Range to 2: [1,2]
    ¡             Construct an infinite list, adding new elements using this function:
                   Argument is list of numbers found so far, say L=[1,2,4]
             N     Natural numbers: [1,2,3,4,5,6,7...
           `-      Remove elements of L: K=[3,5,6,7...
      ḟ            Find first element of K that satisfies this:
                    Argument is a number in K, say 6
     §    →         Last element of L: 4
         ⌋          GCD: 2
       ȯ←           Decrement: 1
                    Implicitly: is it nonzero? Yes, so 6 is good.
                  Result is the EKG sequence: [1,2,4,6,3,9,12...
   ↑              Take the first n elements: [1,2,4,6,3,9,12,8,10,5]
#                 Count the number of those
 >¹               that are larger than n: 1

Answer 4

JavaScript (ES6), 107 106 105 bytes

f=(n,a=[2,1],k=3)=>a[n-1]?0:a.indexOf(k)+(C=(a,b)=>b?C(b,a%b):a>1)(k,a[0])?f(n,a,k+1):(k>n)+f(n,[k,...a])

Try it online!

How?

The helper function \$C\$ returns true if two given integers are not coprime:

C = (a, b) => b ? C(b, a % b) : a > 1

The array \$a\$ is initialized to \$[2,1]\$ and holds all values that were encountered so far in reverse order. Therefore, the last value is always \$a[0]\$.

To know if \$k\$ qualifies as the next term of the sequence, we test whether the following expression is equal to \$0\$:

a.indexOf(k) + C(k, a[0])

a.indexOf(k) is equal to either:

• \$-1\$ if \$k\$ is not found in \$a\$
• \$0\$ if \$k\$ is equal to the last value (in which case it's necessarily not coprime with it)
• some \$i\ge 1\$ otherwise

Therefore, a.indexOf(k) + C(k, a[0]) is equal to \$0\$ if and only if \$k\$ is not found in \$a\$ and \$k\$ is not coprime with the last value (\$-1+true=0\$).

Answer 5

Haskell, 89 82 bytes

Edit: -7 bytes thanks to @H.PWiz

f l=[n|n<-[3..],all(/=n)l,gcd(l!!0)n>1]!!0:l
g n=sum[1|x<-iterate f[2]!!(n-2),x>n]

Try it online!

Answer 6

APL (Dyalog Unicode), 39 bytes^SBCS

-2 bytes thanks to ngn, -1 byte by using proper conditional checking.

{+/⍵<⍵⍴3{(1=⍺∨⊃⌽⍵)∨⍺∊⍵:⍵∇⍨⍺+1⋄⍵,⍺}⍣⍵⍳2}

Try it online!

Answer 7

MATL, 29 bytes

qq:2:w"GE:yX-y0)yZdqg)1)h]G>z

Try it online!

Explanation:

	#implicit input, n, say 10
qq:	#push 1:8
2:	#push [1 2]. Stack: {[1 .. 8], [1 2]}
w	#swap top two elements on stack
"	#begin for loop (do the following n-2 times):
 GE:	#push 1...20. Stack: {[1 2], [1..20]}
 y	#copy from below. Stack:{[1 2], [1..20], [1 2]}
 X-	#set difference. Stack: {[1 2], [3..20]}
 y0)	#copy last element from below. Stack:{[1 2], [3..20], 2}
 yZd	#copy from below and elementwise GCD. Stack:{[1 2], [3..20],[1,2,etc.]}
 qg)	#select those with gcd greater than 1. Stack:{[1 2], [4,6,etc.]}
 1)	#take first. Stack:{[1 2], 4}
 h	#horizontally concatenate. Stack:{[1 2 4]}
 ]	#end of for loop
G>z	#count those greater than input
	#implicit output of result

Answer 8

JavaScript, 93 91 87 bytes

Throws an overflow error for 0 or 1, outputs 0 for 2.

n=>(g=x=>n-i?g[++x]|(h=(y,z)=>z?h(z,y%z):y)(x,c)<2?g(x):(g[c=x]=++i,x>n)+g(2):0)(i=c=2)

Try it online

Answer 9

APL(NARS), chars 121, bytes 242

∇r←a w;i;j;v
r←w⋄→0×⍳w≤2⋄i←2⋄r←⍳2⋄v←1,1,(2×w)⍴0
j←¯1+v⍳0
j+←1⋄→3×⍳1=j⊃v⋄→3×⍳∼1<j∨i⊃r⋄r←r,j⋄i+←1⋄v[j]←1⋄→2×⍳w>i
r←+/w<r
∇

test in less one minute here in running time:

  a¨3 10 100 1000 2000
1 1 9 70 128 

Natural there is no check for type and for range...

Answer 10

Japt, 23 21 bytes

@_jX ªAøZ}f}gA=ì)Aè>U

Try it

@_jX ªAøZ}f}gA=ì)Aè>U
                          :Implicit input of integer U
             A            :10
               ì          :Digit array
              =           :Reassign to A
@          }g             :While the length of A < U+1, take the last element as X,
                          :pass it through the following function & push the result to A
 _       }f               :  Find the first integer Z >= 0 that returns falsey
  jX                      :    Is Z co-prime with X?
     ª                    :    OR
      AøZ                 :    Does A contain Z?
                )         :End loop
                 Aè>U     :Count the elements in A that are greater than U

Answer 11

Python 3, 153 bytes

import math
def f(n):
 l=[1];c=0
 for _ in range(n-1):l+=[min(*range(2,n*4),key=lambda x:n*8if x in l or math.gcd(x,l[-1])<2else x)];c+=l[-1]>n
 return c

Try it online! (Warning: Takes ~30 seconds to evaluate)