Termos da sequência de eletrocardiograma

13

Introdução

A sequência do ECG começa com 1 e 2, então a regra é que o próximo termo seja o menor número inteiro positivo que ainda não esteja na sequência e cujo fator comum com o último termo seja maior que 1 (eles não são coprimes).

Os primeiros termos são:

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

É chamado de eletrocardiograma porque o gráfico de seus termos é bastante semelhante a um eletrocardiograma.

É a sequência A064413 no OEIS .

Desafio

Você tem que escrever uma função que leva um inteiro n como entrada e saídas quantos dos n primeiros termos da sequência são maiores do que n .

Como a regra da sequência começa com o terceiro termo, o número inteiro de entrada deve ser maior ou igual a 3. Por exemplo, dada a entrada, 10a saída ocorre 1porque o sétimo termo é 12e nenhum dos outros dez primeiros excede 10.

Casos de teste

3 -> 1

10 -> 1

100 -> 9

1000 -> 70

Regras

  • Para números inteiros menores que 3, a função pode gerar 0 ou um código de erro.
  • Nenhuma outra regra específica, exceto: é código de golfe, quanto menor, melhor!
david
fonte
Podemos usar a indexação 0, 1sendo o 0º termo da sequência e, portanto, criando, por exemplo, 15o 10º termo, em vez de 5?
Shaggy
@ Shagy Acho que é justo usar isso como uma maneira matemática, mas, na verdade, isso mudará o resultado dos casos de teste e, de fato, a função solicitada em si. Portanto, acho que você não deveria poder fazê-lo. Desculpe.
david
oeis.org/A064413/graph - OEIS pode escrever gráficos? Arrumado.
Magic Octopus Urn

Respostas:

7

Geléia , 20 19 18 bytes

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

Este é um programa completo.

Experimente online!

Como funciona

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.

Observe que a sequência gerada é [1,0,2,4,6,3,9,12,8,10,5,15,] . Como chamar o link auxiliar n vezes gera uma sequência de comprimento n+1 , o 0 é praticamente ignorado.

Dennis
fonte
6

Perl 6 , 66 63 59 58 bytes

-4 bytes graças a Jo King

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

Experimente online!

Muito lento no TIO para n = 1000.

Nwellnhof
fonte
@JoKing Depois que percebi que isso first &f,1..*pode ser reescrito como +(1...&f), seu truque de junção ajudou, afinal.
Nwellnhof 11/03/19
4

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

Experimente online!

Quão?

C

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

a[2,1]a[0]

k0

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

a.indexOf(k) é igual a:

  • 1ka
  • 0 0k
  • Eu1

a.indexOf(k) + C(k, a[0])0 0kumak-1+trvocêe=0 0

Arnauld
fonte
4

Haskell, 89 82 bytes

Edit: -7 bytes graças a @ 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]

Experimente online!

nimi
fonte
82 bytes
H.PWiz
@ H.PWiz: ah, isso é inteligente. Obrigado!
nimi
4

Casca , 16 bytes

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

Experimente online!

Explicação

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

MATL , 29 bytes

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

Experimente online!

Explicação:

	#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
Giuseppe
fonte
por favor, você pode explicar por que você dobra a entrada (com GE:)?
David #
2
@ David Eu acho que empiricamente notei que uma(n)2n mas não tenho uma prova, então usei originalmente uma(n)n2, que atingiu o tempo limite no n=1000caso de teste, então eu mudei de volta para testar isso e o deixei. Ainda não tenho certeza sobre nenhum dos limites, mas parece funcionar, então posso tentar apresentar uma prova. Um whileloop seria muito mais confuso no MATL, então eu estava tentando evitá-lo.
21418 Giuseppe #:
3

APL (Dyalog Unicode) , SBCS de 39 bytes

-2 bytes graças a ngn, -1 byte usando a verificação condicional adequada.

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

Experimente online!

voidhawk
fonte
passa seu próprio argumento esquerdo para a função operando, portanto não há necessidade . Além disso, não se vincula à coisa à direita, pois começa com uma função ( ), portanto não há necessidade .
ngn 22/03/19
2

JavaScript, 93 91 87 bytes

Lança um erro de estouro para 0ou 1, gera 0para 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)

Experimente online

Shaggy
fonte
2

APL (NARS), caracteres 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
∇

teste em menos de um minuto aqui em tempo de execução:

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

Natural, não há verificação de tipo e alcance ...

RosLuP
fonte
1

Japonês, 23 21 bytes

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

Tente

@_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
Shaggy
fonte
1

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

Experimente online! (Aviso: leva cerca de 30 segundos para avaliar)

Black Owl Kai
fonte