13
\$\begingroup\$

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!
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Shaggy Nov 13 '18 at 16:48
  • \$\begingroup\$ @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. \$\endgroup\$ – david Nov 13 '18 at 16:59
  • \$\begingroup\$ oeis.org/A064413/graph - OEIS can write graphs? Neat. \$\endgroup\$ – Magic Octopus Urn Mar 21 at 13:44

11 Answers 11

7
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ @JoKing After I realised that first &f,1..* can be rewritten as +(1...&f), your junction trick helped after all. \$\endgroup\$ – nwellnhof Mar 11 at 14:29
4
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ 82 bytes \$\endgroup\$ – H.PWiz Nov 13 '18 at 17:41
  • \$\begingroup\$ @H.PWiz: ah, that's clever. Thanks! \$\endgroup\$ – nimi Nov 13 '18 at 17:50
4
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ please can you explain why do you double the input (with GE:)? \$\endgroup\$ – david Nov 13 '18 at 20:56
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ – Giuseppe Nov 13 '18 at 21:08
3
\$\begingroup\$

APL (Dyalog Unicode), 39 bytesSBCS

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

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 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 . \$\endgroup\$ – ngn Mar 22 at 15:14
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.