# 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.

# 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.

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!
• Can we use 0-indexing, with 1 being the 0th term of the sequence and therefor making, for example, 15 the 10th term, rather than 5? Commented Nov 13, 2018 at 16:48
• @Shaggy I think it's fair to use this as a mathematical way, but actually it will change the result of test cases and indeed the asked function in itself. Thus I think you should'nt be allowed to do so. Sorry. Commented Nov 13, 2018 at 16:59
• oeis.org/A064413/graph - OEIS can write graphs? Neat. Commented Mar 21, 2019 at 13:44

# Jelly, 2019 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.
ɗƇ      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.

# Perl 6, 666359 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.

• @JoKing After I realised that first &f,1..* can be rewritten as +(1...&f), your junction trick helped after all. Commented Mar 11, 2019 at 14:29

# 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


# JavaScript (ES6), 107106 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\$$).

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!

• 82 bytes Commented Nov 13, 2018 at 17:41
• @H.PWiz: ah, that's clever. Thanks!
– nimi
Commented Nov 13, 2018 at 17:50

# APL (Dyalog Unicode), 39 bytesSBCS

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

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


Try it online!

• ⍣ passes its own left argument to the operand function, so there's no need for ∘. also, ⍵ won't bind with the thing on the right as it starts with a function (⍳), so there's no need for ⊢.
– ngn
Commented Mar 22, 2019 at 15:14

# 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

• please can you explain why do you double the input (with GE:)? Commented Nov 13, 2018 at 20:56
• @david I think empirically I noticed that $a(n)\leq 2n$ but I don't have a proof, so I originally used $a(n)\leq n^2$, which timed out on the $n=1000$ test case, so I switched it back to test that, and left it in. I'm still not sure about either bound, but it seems to work, so I may try to come up with a proof. A while loop would be much messier in MATL so I was trying to avoid it. Commented Nov 13, 2018 at 21:08

# JavaScript, 9391 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

# 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...

# 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


# 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)