Terms of the EKG sequence

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
9
down vote

favorite












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!









share|improve this question























  • 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?
    – Shaggy
    yesterday










  • @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.
    – david
    yesterday














up vote
9
down vote

favorite












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!









share|improve this question























  • 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?
    – Shaggy
    yesterday










  • @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.
    – david
    yesterday












up vote
9
down vote

favorite









up vote
9
down vote

favorite











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!









share|improve this 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!






code-golf sequence






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited yesterday









Solomon Ucko

264110




264110










asked yesterday









david

595




595











  • 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?
    – Shaggy
    yesterday










  • @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.
    – david
    yesterday
















  • 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?
    – Shaggy
    yesterday










  • @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.
    – david
    yesterday















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?
– Shaggy
yesterday




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?
– Shaggy
yesterday












@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.
– david
yesterday




@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.
– david
yesterday










8 Answers
8






active

oldest

votes

















up vote
6
down vote














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.






share|improve this answer





























    up vote
    5
    down vote














    Perl 6, 66 bytes





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


    Try it online!



    Too slow on TIO for n = 1000.






    share|improve this answer





























      up vote
      4
      down vote













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






      share|improve this answer





























        up vote
        4
        down vote













        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!






        share|improve this answer






















        • 82 bytes
          – H.PWiz
          yesterday










        • @H.PWiz: ah, that's clever. Thanks!
          – nimi
          yesterday

















        up vote
        3
        down vote














        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





        share|improve this answer



























          up vote
          2
          down vote













          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






          share|improve this answer





























            up vote
            1
            down vote














            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





            share|improve this answer




















            • please can you explain why do you double the input (with GE:)?
              – david
              yesterday






            • 1




              @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.
              – Giuseppe
              yesterday

















            up vote
            1
            down vote













            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





            share|improve this answer






















              Your Answer





              StackExchange.ifUsing("editor", function ()
              return StackExchange.using("mathjaxEditing", function ()
              StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
              StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
              );
              );
              , "mathjax-editing");

              StackExchange.ifUsing("editor", function ()
              StackExchange.using("externalEditor", function ()
              StackExchange.using("snippets", function ()
              StackExchange.snippets.init();
              );
              );
              , "code-snippets");

              StackExchange.ready(function()
              var channelOptions =
              tags: "".split(" "),
              id: "200"
              ;
              initTagRenderer("".split(" "), "".split(" "), channelOptions);

              StackExchange.using("externalEditor", function()
              // Have to fire editor after snippets, if snippets enabled
              if (StackExchange.settings.snippets.snippetsEnabled)
              StackExchange.using("snippets", function()
              createEditor();
              );

              else
              createEditor();

              );

              function createEditor()
              StackExchange.prepareEditor(
              heartbeatType: 'answer',
              convertImagesToLinks: false,
              noModals: true,
              showLowRepImageUploadWarning: true,
              reputationToPostImages: null,
              bindNavPrevention: true,
              postfix: "",
              imageUploader:
              brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
              contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
              allowUrls: true
              ,
              onDemand: true,
              discardSelector: ".discard-answer"
              ,immediatelyShowMarkdownHelp:true
              );



              );













               

              draft saved


              draft discarded


















              StackExchange.ready(
              function ()
              StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f175858%2fterms-of-the-ekg-sequence%23new-answer', 'question_page');

              );

              Post as a guest






























              8 Answers
              8






              active

              oldest

              votes








              8 Answers
              8






              active

              oldest

              votes









              active

              oldest

              votes






              active

              oldest

              votes








              up vote
              6
              down vote














              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.






              share|improve this answer


























                up vote
                6
                down vote














                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.






                share|improve this answer
























                  up vote
                  6
                  down vote










                  up vote
                  6
                  down vote










                  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.






                  share|improve this answer















                  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.







                  share|improve this answer














                  share|improve this answer



                  share|improve this answer








                  edited yesterday

























                  answered yesterday









                  Dennis

                  184k32293728




                  184k32293728




















                      up vote
                      5
                      down vote














                      Perl 6, 66 bytes





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


                      Try it online!



                      Too slow on TIO for n = 1000.






                      share|improve this answer


























                        up vote
                        5
                        down vote














                        Perl 6, 66 bytes





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


                        Try it online!



                        Too slow on TIO for n = 1000.






                        share|improve this answer
























                          up vote
                          5
                          down vote










                          up vote
                          5
                          down vote










                          Perl 6, 66 bytes





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


                          Try it online!



                          Too slow on TIO for n = 1000.






                          share|improve this answer















                          Perl 6, 66 bytes





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


                          Try it online!



                          Too slow on TIO for n = 1000.







                          share|improve this answer














                          share|improve this answer



                          share|improve this answer








                          edited yesterday

























                          answered yesterday









                          nwellnhof

                          5,7081021




                          5,7081021




















                              up vote
                              4
                              down vote













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






                              share|improve this answer


























                                up vote
                                4
                                down vote













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






                                share|improve this answer
























                                  up vote
                                  4
                                  down vote










                                  up vote
                                  4
                                  down vote









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






                                  share|improve this answer














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







                                  share|improve this answer














                                  share|improve this answer



                                  share|improve this answer








                                  edited yesterday

























                                  answered yesterday









                                  Arnauld

                                  68.5k584289




                                  68.5k584289




















                                      up vote
                                      4
                                      down vote













                                      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!






                                      share|improve this answer






















                                      • 82 bytes
                                        – H.PWiz
                                        yesterday










                                      • @H.PWiz: ah, that's clever. Thanks!
                                        – nimi
                                        yesterday














                                      up vote
                                      4
                                      down vote













                                      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!






                                      share|improve this answer






















                                      • 82 bytes
                                        – H.PWiz
                                        yesterday










                                      • @H.PWiz: ah, that's clever. Thanks!
                                        – nimi
                                        yesterday












                                      up vote
                                      4
                                      down vote










                                      up vote
                                      4
                                      down vote









                                      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!






                                      share|improve this answer














                                      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!







                                      share|improve this answer














                                      share|improve this answer



                                      share|improve this answer








                                      edited yesterday

























                                      answered yesterday









                                      nimi

                                      30.6k31985




                                      30.6k31985











                                      • 82 bytes
                                        – H.PWiz
                                        yesterday










                                      • @H.PWiz: ah, that's clever. Thanks!
                                        – nimi
                                        yesterday
















                                      • 82 bytes
                                        – H.PWiz
                                        yesterday










                                      • @H.PWiz: ah, that's clever. Thanks!
                                        – nimi
                                        yesterday















                                      82 bytes
                                      – H.PWiz
                                      yesterday




                                      82 bytes
                                      – H.PWiz
                                      yesterday












                                      @H.PWiz: ah, that's clever. Thanks!
                                      – nimi
                                      yesterday




                                      @H.PWiz: ah, that's clever. Thanks!
                                      – nimi
                                      yesterday










                                      up vote
                                      3
                                      down vote














                                      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





                                      share|improve this answer
























                                        up vote
                                        3
                                        down vote














                                        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





                                        share|improve this answer






















                                          up vote
                                          3
                                          down vote










                                          up vote
                                          3
                                          down vote










                                          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





                                          share|improve this answer













                                          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






                                          share|improve this answer












                                          share|improve this answer



                                          share|improve this answer










                                          answered 16 hours ago









                                          Zgarb

                                          26.3k460228




                                          26.3k460228




















                                              up vote
                                              2
                                              down vote













                                              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






                                              share|improve this answer


























                                                up vote
                                                2
                                                down vote













                                                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






                                                share|improve this answer
























                                                  up vote
                                                  2
                                                  down vote










                                                  up vote
                                                  2
                                                  down vote









                                                  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






                                                  share|improve this answer














                                                  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







                                                  share|improve this answer














                                                  share|improve this answer



                                                  share|improve this answer








                                                  edited 11 hours ago

























                                                  answered yesterday









                                                  Shaggy

                                                  17.9k21663




                                                  17.9k21663




















                                                      up vote
                                                      1
                                                      down vote














                                                      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





                                                      share|improve this answer




















                                                      • please can you explain why do you double the input (with GE:)?
                                                        – david
                                                        yesterday






                                                      • 1




                                                        @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.
                                                        – Giuseppe
                                                        yesterday














                                                      up vote
                                                      1
                                                      down vote














                                                      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





                                                      share|improve this answer




















                                                      • please can you explain why do you double the input (with GE:)?
                                                        – david
                                                        yesterday






                                                      • 1




                                                        @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.
                                                        – Giuseppe
                                                        yesterday












                                                      up vote
                                                      1
                                                      down vote










                                                      up vote
                                                      1
                                                      down vote










                                                      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





                                                      share|improve this answer













                                                      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






                                                      share|improve this answer












                                                      share|improve this answer



                                                      share|improve this answer










                                                      answered yesterday









                                                      Giuseppe

                                                      15.8k31051




                                                      15.8k31051











                                                      • please can you explain why do you double the input (with GE:)?
                                                        – david
                                                        yesterday






                                                      • 1




                                                        @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.
                                                        – Giuseppe
                                                        yesterday
















                                                      • please can you explain why do you double the input (with GE:)?
                                                        – david
                                                        yesterday






                                                      • 1




                                                        @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.
                                                        – Giuseppe
                                                        yesterday















                                                      please can you explain why do you double the input (with GE:)?
                                                      – david
                                                      yesterday




                                                      please can you explain why do you double the input (with GE:)?
                                                      – david
                                                      yesterday




                                                      1




                                                      1




                                                      @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.
                                                      – Giuseppe
                                                      yesterday




                                                      @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.
                                                      – Giuseppe
                                                      yesterday










                                                      up vote
                                                      1
                                                      down vote













                                                      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





                                                      share|improve this answer


























                                                        up vote
                                                        1
                                                        down vote













                                                        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





                                                        share|improve this answer
























                                                          up vote
                                                          1
                                                          down vote










                                                          up vote
                                                          1
                                                          down vote









                                                          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





                                                          share|improve this answer














                                                          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






                                                          share|improve this answer














                                                          share|improve this answer



                                                          share|improve this answer








                                                          edited yesterday

























                                                          answered yesterday









                                                          Shaggy

                                                          17.9k21663




                                                          17.9k21663



























                                                               

                                                              draft saved


                                                              draft discarded















































                                                               


                                                              draft saved


                                                              draft discarded














                                                              StackExchange.ready(
                                                              function ()
                                                              StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f175858%2fterms-of-the-ekg-sequence%23new-answer', 'question_page');

                                                              );

                                                              Post as a guest













































































                                                              Popular posts from this blog

                                                              How to check contact read email or not when send email to Individual?

                                                              Displaying single band from multi-band raster using QGIS

                                                              How many registers does an x86_64 CPU actually have?