introduction

La séquence ECG commence par 1 et 2, puis la règle est que le terme suivant est le plus petit entier positif qui ne figure pas déjà dans la séquence et dont le facteur commun avec le dernier terme est supérieur à 1 (ils ne sont pas des nombres premiers).

Les premiers termes sont:

1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, ...

C'est ce qu'on appelle l'électrocardiogramme parce que le graphique de ses termes est assez similaire à un électrocardiogramme.

C'est la séquence A064413 dans l'OEIS .

Défi

Vous devez écrire une fonction qui prend un entier n en entrée et affiche combien de n premiers termes de la séquence sont supérieurs à n .

Comme la règle de la séquence commence par le troisième terme, l'entier d'entrée doit être supérieur ou égal à 3. Par exemple, pour une entrée donnée, 10la sortie est 1due au fait que le 7e terme est 12et qu'aucun des dix premiers termes ne dépasse 10.

Cas de test

3 -> 1

10 -> 1

100 -> 9

1000 -> 70

Règles

• Pour les entiers inférieurs à 3, la fonction peut sortir 0 ou un code d'erreur.
• Pas d'autres règles particulières sauf: c'est du golf de code, le plus court sera le mieux!

Gelée , 20 19 18 octets

S‘gṪ’ɗƇḟ¹Ṃṭ
1Ç¡>¹S

Ceci est un programme complet.

Essayez-le en ligne!

Comment ça fonctionne

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.

Notez que la séquence générée est $[1, \mathbf{0}, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, \dots]$ . Étant donné que l'appel de la liaison d'assistance $n$ fois génère une séquence de longueur $n + 1$ , le $0$ est pratiquement ignoré.

Perl 6 , 66 63 59 58 octets

-4 octets grâce à Jo King

{sum (1,2,{+(1...all *gcd@_[*-1]>1,*∉@_)}...*)[^$_]X>$_}

Essayez-le en ligne!

Trop lent sur TIO pour n = 1000.

JavaScript (ES6), 107 106 105 octets

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

Essayez-le en ligne!

Comment?

$C$

C = (a, b) => b ? C(b, a % b) : a > 1

$a$$[2,1]$$a[0]$

$k$$0$

a.indexOf(k) + C(k, a[0])

a.indexOf(k) est égal à:

• $-1$$k$$a$
• $0$$k$
• $i\ge 1$

a.indexOf(k) + C(k, a[0])$0$$k$$a$$k$$-1+true=0$).

Haskell, 89 82 octets

Edit: -7 octets grâce à @ 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]

Essayez-le en ligne!

Husk , 16 octets

#>¹↑¡§ḟȯ←⌋→`-Nḣ2

Essayez-le en ligne!

Explication

#>¹↑¡§ḟȯ←⌋→`-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 octets

qq:2:w"GE:yX-y0)yZdqg)1)h]G>z

Essayez-le en ligne!

Explication:

	#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

APL (Dyalog Unicode) , 39 octets ^SBCS

-2 octets grâce à ngn, -1 octet en utilisant une vérification conditionnelle appropriée.

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

Essayez-le en ligne!

JavaScript, 93 91 87 octets

Lance une erreur de débordement pour 0ou 1, produit 0pour 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)

Essayez-le en ligne

APL (NARS), caractères 121, octets 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
∇

tester en moins d'une minute ici en temps d'exécution:

  a¨3 10 100 1000 2000
1 1 9 70 128 

Naturellement, il n'y a pas de contrôle pour le type et la portée ...

Japt, 23 21 octets

@_jX ªAøZ}f}gA=ì)Aè>U

Essayez-le

@_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 octets

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

Essayez-le en ligne! (Avertissement: prend environ 30 secondes pour évaluer)