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!

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, mathbf0, 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, 66 bytes

+grep *>$_,(1,2,first *gcd@_[*-1]>1,grep *∉@_,1..*...*)[^$_]

Try it online!

Too slow on TIO for n = 1000.

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 $ige 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$).

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!

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

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