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.

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

JavaScript, 93 91 bytes

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

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

Try it online

n=>                                 :Anonymous function taking the input as an argument via parameter n

(g=x=>                              :Main function g which takes the number we want to test as an argument via parameter x

  n-i?                              :If n is greater than the iteration counter i then

    a[++x]                          :Increment x and check if the array a has an element at that index

                                    :(On the first iteration x will be the singleton array [2] which gets coerced to a number before being incremented)

    |                               :Or

    (h=(y,z)=>z?h(z,y%z):y)(x,c)    :Helper function which returns the GCD of x and c, the last number in he sequence so far

    <2                              :If that's less than 2 then c & x are co-prime

    ?                               :If either of those checks are truthy then

      g(x)                          :Call g again with the incremented value of x

    :(                              :Else

      a[c=x]=++i,                   :Assign x to c for the next iteration, increment the iteration counter and drop that value into the array at index x

      x>n                           :Test if x is greater than the original input

      )+g(2)                        :Add the result of running g again, with an initial value of 2

  :0                                :Else if n==i then return 0, add that to the final value and return the result

)(a=[i=c=2])                        :Immediately call g with an initial value of [2] which also gets assigned to a and initiate i & c with a value of 2

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

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