Paciência, jovem "Padovan"

44

Todo mundo conhece a sequência de Fibonacci:
você pega um quadrado, anexa um quadrado igual a ele e, em seguida, anexa repetidamente um quadrado cujo comprimento lateral é igual ao maior comprimento lateral do retângulo resultante.
O resultado é uma bela espiral de quadrados cuja sequência de números é a sequência de Fibonacci :

Mas, e se não quiséssemos usar quadrados?

Se usarmos triângulos equilaterais - em vez de quadrados - de maneira semelhante, obteremos uma espiral igualmente bonita de triângulos e uma nova sequência: a sequência Padovan , também conhecida como A000931 :

Tarefa:

Dado um número inteiro positivo, , saída , o ° prazo na sequência Padovan ou as primeiras termos.NaNNN

Suponha que os três primeiros termos da sequência sejam todos . Assim, a sequência começará da seguinte forma: 1

1,1,1,2,2,3,...

Entrada:

  • Qualquer número inteiro positivoN0

  • Entrada inválida não precisa ser levada em consideração

Resultado:

  • O ° prazo na sequência Padovan OU os primeiros termos da sequência Padovan.NNN

  • Se os primeiros termos forem impressos, a saída poderá ser o que for mais conveniente (lista / matriz, sequência de linhas múltiplas, etc.)N

  • Pode ser indexado ou indexado01

Casos de Teste:
(0-indexados, th prazo)N

Input | Output
--------------
0     | 1
1     | 1
2     | 1
4     | 2
6     | 4
14    | 37
20    | 200
33    | 7739

(Indexados em 1, primeiros termos)N

Input | Output
--------------
1     | 1
3     | 1,1,1
4     | 1,1,1,2
7     | 1,1,1,2,2,3,4
10    | 1,1,1,2,2,3,4,5,7,9
12    | 1,1,1,2,2,3,4,5,7,9,12,16

Regras:

Tau
fonte
2
14(0-indexado) é mostrado como saída 28enquanto eu acredito que deveria render37
Jonathan Allan
@ JonathanAllan sim, você está correto. Eu fixo os dois últimos casos de teste para º prazo, mas não essa. A postagem foi editada. N
Tau
@LuisMendo Eu acredito que sim. Eu vou editar a postagem.
Tau
1
@sharur esta definição para a sequência de Fibonacci é a definição visual . Cada quadrado sucessivo adicionado possui um comprimento desse termo na sequência. A sequência que você descreve é ​​o raciocínio numérico por trás dela. Ambas as seqüências funcionam tão bem quanto a outra.
Tau
1
Observe que a sequência OEIS que você vinculou é um pouco diferente, pois é usada a_0=1, a_1=0, a_2=0. Ele acaba sendo deslocado um pouco, porque entãoa_5=a_6=a_7=1
Carmeister

Respostas:

59

Gelatina , 10 bytes

9s3’Ẓæ*³FṀ

Experimente online!

1 indexado. Calcula o maior elemento de:

[001101010]n
onde a matriz binária é convenientemente calculada como:
[isprime(0)isprime(1)isprime(2)isprime(3)isprime(4)isprime(5)isprime(6)isprime(7)isprime(8)]

(isso é uma total coincidência.)

9s3         [[1,2,3],[4,5,6],[7,8,9]]    9 split 3
   ’        [[0,1,2],[3,4,5],[6,7,8]]    decrease
    Ẓ       [[0,0,1],[1,0,1],[0,1,0]]    isprime
     æ*³    [[0,0,1],[1,0,1],[0,1,0]]^n  matrix power by input
        FṀ                               flatten, maximum
Lynn
fonte
33
isso é claramente algum tipo de vodu
Pureferret
7
Isso deve ser publicado.
YSC
6
@YSC Já foi publicado em A000931 . Eu nunca teria adivinhar o truque primos :)
flawr 08/04
1
... faça isso ", a menos que alguém consiga tirar dois bytes desse" (agora que eu tenho 9 byter )
Jonathan Allan
1
Estou tão acostumado a ver respostas absurdamente pequenas aqui, que pensei que a vírgula após 'Jelly' era de fato o código para esse problema
Tasos Papastylianou
28

Oásis , 5 bytes

nono termo indexado a 0

cd+1V

Experimente online!

Explicação

   1V   # a(0) = 1
        # a(1) = 1
        # a(2) = 1
        # a(n) =
c       #        a(n-2)
  +     #              +
 d      #               a(n-3)
Emigna
fonte
26

Geléia ,  10 9  8 bytes

ŻṚm2Jc$S

Um link monádico que aceita n(indexado 0) que produz P(n).

Experimente online!

Quão?

ImplementaçõesP(n)=i=0n2(i+1n2i)

ŻṚm2Jc$S - Link: integer, n       e.g. 20
Ż        - zero range                  [0, 1, 2, 3, 4, ..., 19, 20]
 Ṛ       - reverse                     [20, 19, ..., 4, 3, 2, 1, 0]
  m2     - modulo-slice with 2         [20, 18, 16, 14, 12, 10,  8,  6,  4,  2,  0]  <- n-2i
      $  - last two links as a monad:
    J    -   range of length           [ 1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11]  <- i+1
     c   -   left-choose-right         [ 0,  0,  0,  0,  0,  0,  0, 28,126, 45,  1]
       S - sum                         200

E aqui está um "duplo"
... um método totalmente diferente também para 8 bytes (este é 1 indexado, mas muito mais lento):

3ḊṗRẎ§ċ‘ - Link: n
3Ḋ       - 3 dequeued = [2,3]
   R     - range = [1,2,3,...,n]
  ṗ      -   Cartesian power         [[[2],[3]],[[2,2],[2,3],[3,2],[3,3]],[[2,2,2],...],...]
    Ẏ    - tighten                   [[2],[3],[2,2],[2,3],[3,2],[3,3],[2,2,2],...]
     §   - sums                      [ 2,  3,   4,    5,    5,    6,     6,...]
       ‘ - increment                 n+1
      ċ  - count occurrences         P(n)
Jonathan Allan
fonte
18

Haskell , 26 bytes

(l!!)
l=1:1:1:2:scanl(+)2l

Experimente online! Gera o nono termo indexado a zero.

Eu pensei que a solução recursiva "óbvia" abaixo seria imbatível, mas então eu achei isso. É semelhante à expressão clássica de golfe l=1:scanl(+)1lpara a lista infinita de Fibonacci, mas aqui a diferença entre elementos adjacentes é o termo 4 posições de volta. Podemos escrever mais diretamente l=1:1:zipWith(+)l(0:l), mas isso é mais longo.

Se esse desafio permitisse a saída infinita da lista, poderíamos cortar a primeira linha e ter 20 bytes.

27 bytes

f n|n<3=1|1>0=f(n-2)+f(n-3)

Experimente online!

xnor
fonte
6

Oitava / MATLAB, 35 33 bytes

@(n)[1 filter(1,'cbaa'-98,2:n<5)]

Produz os primeiros n termos.

Experimente online!

Como funciona

Função anônima que implementa um filtro recursivo .

'cbaa'-98é uma forma mais curta de produzir [1 0 -1 -1].

2:n<5é uma forma mais curta de produzir [1 1 1 0 0 ··· 0]( n- 1 termos).

filter(1,[1 0 -1 -1],[1 1 1 0 0 ··· 0])passa a entrada [1 1 1 0 0 ··· 0]por um filtro de tempo discreto definido por uma função de transferência com coeficiente numerador 1e coeficiente denominador [1 0 -1 -1].

Luis Mendo
fonte
6

J , 22 bytes

-2 bytes graças a ngn e Galen

formulário fechado, 26 bytes

0.5<.@+1.04535%~1.32472^<:

Experimente online!

iterativo, 22 bytes

(],1#._2 _3{ ::1])^:[#

Experimente online!

Jonah
fonte
1
Outra solução de 24 bytes (chata): (1 # .2 3 $: @ - ~]) `1: @. (3 e>) Experimente online!
Galen Ivanov
23 bytes graças a ngn 1:-> #: Experimente online!
Galen Ivanov
@ GalenIvanov tyvm, esse é um grande truque.
Jonah
2
1:-> 1. "adverso" funciona com um substantivo à direita, aparentemente
ngn 10/04
@ngn TIL ... ty de novo!
Jonah
5

Retina , 47 42 bytes

K`0¶1¶0
"$+"+`.+¶(.+)¶.+$
$&¶$.(*_$1*
6,G`

Experimente online! Produz os primeiros ntermos em linhas separadas. Explicação:

K`0¶1¶0

Substitua a entrada pelos termos para -2, -1e 0.

"$+"+`.+¶(.+)¶.+$
$&¶$.(*_$1*

Gere os próximos ntermos usando a relação de recorrência. *_aqui é curto para o $&*_qual converte o (primeiro) número da correspondência em unário, enquanto $1*é curto para o $1*_qual converte o número do meio em unário. O $.(retorna a soma decimal de seus argumentos unários, ou seja, a soma do primeiro e do meio números.

6,G`

Descarte os seis primeiros caracteres, ou seja, as três primeiras linhas.

Neil
fonte
5

Cubix , 20 bytes

Este é indexado 0 e emite o N ° termo

;@UOI010+p?/sqq;W.\(

Experimente online!

Envolve em um cubo com comprimento lateral 2

    ; @
    U O
I 0 1 0 + p ? /
s q q ; W . \ (
    . .
    . .

Assista correr

  • I010 - Inicia a pilha
  • +p? - Adiciona o topo da pilha, puxa o contador da parte inferior da pilha e testa
  • /;UO@ - Se o contador for 0, reflita na face superior, remova os TOS, inversão de marcha, saída e pare
  • \(sqq;W - Se o contador for positivo, reflita, diminua o contador, troque o TOS, empurre de cima para baixo duas vezes, remova o TOS e mude a faixa de volta para o loop principal.
MickyT
fonte
4

Perl 6 , 24 bytes

{(1,1,1,*+*+!*...*)[$_]}

Experimente online!

Uma sequência gerada bastante padrão, com cada novo elemento gerado pela expressão * + * + !*. Isso adiciona o terceiro elemento anterior, o segundo elemento anterior e a negação lógica do elemento anterior, que é sempre False, que é numericamente zero.

Sean
fonte
Por que este wiki da comunidade?
Jo King
@JoKing Beats me. Se eu fiz de alguma forma, não foi de propósito.
Sean
4

05AB1E , 8 bytes

1Ð)λ£₂₃+

Experimente online!

1Ð)1D)3Å1n£

Quão?

1Ð)λ£₂₃+ | Full program.
1Ð)      | Initialize the stack with [1, 1, 1].
   λ     | Begin the recursive generation of a list: Starting from some base case,
         | this command generates an infinite list with the pattern function given.
    £    | Flag for λ. Instead of outputting an infinite stream, only print the first n.
     ₂₃+ | Add a(n-2) and a(n-3).
Mr. Xcoder
fonte
Eu não acho que 1Ð)pode ter 2 bytes tbh. Eu posso pensar em seis alternativas diferentes de 3 bytes , mas não em 2 bytes.
Kevin Cruijssen 8/04
4

APL (Dyalog Unicode) , 20 18 17 bytes SBCS

Este código é indexado em 1. É o mesmo número de bytes para obter nitens da sequência Padovan, pois você precisa eliminar os últimos membros extras. Também é o mesmo número de bytes para obter a indexação 0.

Edit: -2 bytes graças a ngn. -1 byte graças a ngn

4⌷2(⊢,⍨2⌷+/)⍣⎕×⍳3

Experimente online!

Explicação

4⌷2(⊢,⍨2⌷+/)⍣⎕×⍳3

  ⍺(. . . .)⍣⎕⍵   This format simply takes the input ⎕ and applies the function
                   inside the brackets (...) to its operands (here marked ⍵ and ⍺).
  2(. . .+/)⍣⎕×⍳3  In this case, our ⍵, the left argument, is the array 1 1 1,
                   where we save our results as the function is repeatedly applied
                   and our ⍺, 2, is our right argument and is immediately applied to +/,
                   so that we have 2+/ which will return the pairwise sums of our array.
       2⌷          We take the second pairwise sum, f(n-2) + f(n-3)
    ⊢,⍨            And add it to the head of our array.
4⌷                 When we've finished adding Padovan numbers to the end of our list,
                   the n-th Padovan number (1-indexed) is the 4th member of that list,
                   and so, we implicitly return that.
Sherlock9
fonte
4

K (ngn / k) , 24 20 bytes

-4 bytes graças a ngn!

{$[x<3;1;+/o'x-2 3]}

Experimente online!

Indexado em 0, primeiros termos N

Galen Ivanov
fonte
1
f[x-2]+f[x-3]-> +/o'x-2 3( oé "recorrente")
ngn 8/04
@ngn Obrigado! Eu tentei (sem sucesso) em J; aqui é elegante.
Galen Ivanov
@ngn De fato, aqui está uma possibilidade de como ele fica em J: (1 # .2 3 $: @ - ~]) `1: @. (3 &>)
Galen Ivanov
ah, certo, decodificação base-1 é uma maneira fácil de treinar para somar :)
ngn 8/04
2
1:-> #na solução j
ngn 8/04
4

código de máquina x86 de 32 bits, 17 bytes

53 33 db f7 e3 43 83 c1 04 03 d8 93 92 e2 fa 5b c3

Desmontagem:

00CE1250 53                   push        ebx  
00CE1251 33 DB                xor         ebx,ebx  
00CE1253 F7 E3                mul         eax,ebx  
00CE1255 43                   inc         ebx  
00CE1256 83 C1 04             add         ecx,4  
00CE1259 03 D8                add         ebx,eax  
00CE125B 93                   xchg        eax,ebx  
00CE125C 92                   xchg        eax,edx  
00CE125D E2 FA                loop        myloop (0CE1259h)  
00CE125F 5B                   pop         ebx  
00CE1260 C3                   ret

É 0 indexado. A inicialização é convenientemente alcançada calculando-se eax * 0. O resultado de 128 bits é 0 e entra em edx: eax.

No início de cada iteração, a ordem dos registros é ebx, eax, edx. Eu tive que escolher a ordem certa para tirar proveito da codificação da xchg eaxinstrução - 1 byte.

Eu tive que adicionar 4 ao contador de loop para permitir que a saída chegasse eax, o que mantém o valor de retorno da função na fastcallconvenção.

Eu poderia usar outra convenção de chamadas, que não requer salvamento e restauração ebx, mas fastcallé divertido mesmo assim :)

anatolyg
fonte
2
Adoro ver as respostas do código da máquina no PP&CG! +1
Tau
3

Lua 5.3,49. 48 bytes

function f(n)return n<4 and 1or f(n-2)+f(n-3)end

Experimente online!

Vanilla Lua não possui coerção de booleanos em strings ( tonumber(true)retornos pares nil), então você deve usar um operador pseudo-ternário. Esta versão é indexada em 1, como toda Lua. A 1orpeça deve ser alterada para 1 orLua 5.1, que possui uma maneira diferente de lexar números.

ciclaminista
fonte
3

JavaScript (ES6), 23 bytes

a(0)=a(1)=a(2)=1

N

f=n=>n<3||f(n-2)+f(n-3)

Experimente online!

Arnauld
fonte
Não acho razoável dizer que retornar trueé o mesmo que retornar 1se o restante da saída for números.
Nit
2
@Nit Meta post relevante .
Arnauld
Acho que estão faltando alguns requisitos: Dê uma olhada na minha modificação (versão em Java) aqui .
Shaq
@ Shaq O desafio especifica claramente que os três primeiros termos da sequência são todos 1 . Assim, é não a sequência definida na A000931 (mas a fórmula é a mesma).
Arnauld
@ Arnauld sim, eu posso vê-lo agora. Desculpa!
Shaq
2

Japonês -N , 12 bytes

<3ªßUµ2 +ß´U

Tente

Modalidade de ignorância
fonte
Parece que 12 é o melhor que podemos fazer: \
Shaggy
Eu estou corrigido!
Shaggy
2

TI-BASIC (TI-84), 34 bytes

[[0,1,0][0,0,1][1,1,0]]^(Ans+5:Ans(1,1

N

A entrada é no Ans.
A saída está dentro Anse é impressa automaticamente.

Imaginei que havia passado tempo suficiente, além de várias respostas terem sido postadas, das quais muitas foram superadas por essa resposta.

Exemplo:

0
               0
prgmCDGFD
               1
9
               9
prgmCDGFD
               9
16
              16
prgmCDGFD
              65

Explicação:

[[0,1,0][0,0,1][1,1,0]]^(Ans+5:Ans(1,1      ;full program (example input: 6)

[[0,1,0][0,0,1][1,1,0]]                     ;generate the following matrix:
                                            ; [0 1 0]
                                            ; [0 0 1]
                                            ; [1 1 0]
                       ^(Ans+5              ;then raise it to the power of: input + 5
                                            ; [4  7 5]
                                            ; [5  9 7]
                                            ; [7 12 9]
                               Ans(1,1      ;get the top-left index and leave it in "Ans"
                                            ;implicitly print Ans
Tau
fonte
2

Pitão, 16 bytes

L?<b3!b+y-b2y-b3

Isso define a função y. Experimente aqui!

Aqui está uma solução mais divertida, apesar de ter 9 bytes a mais; bytes podem ser raspados.

+l{sa.pMf.Am&>d2%d2T./QY!

Isso usa a definição dada por David Callan na página da OEIS: "a (n) = número de composições de n em partes ímpares e> = 3." Experimente aqui! Ele recebe entrada diretamente em vez de definir uma função.

RK.
fonte
y-b2y-b3talvez pudesse ser refatorado com bifurcado ou L? Embora declarar uma matriz de 2 elementos seja caro. yL-Lb2,3é mais :(
Ven
@ Ven fui capaz de substituir +y-b2y-b3com o smy-bdhB2que é a mesma quantidade de bytes; hB2resulta na matriz[2, 3]
RK.
Bem feito hB2. Pena que é a mesma contagem de bytes.
Ven
Sim, embora eu queira saber se há alguma maneira de se livrar do dno mapa.
RK.
2

Java, 41 bytes

Não é possível usar um lambda (erro de tempo de execução). Porta desta resposta Javascript

int f(int n){return n<3?1:f(n-2)+f(n-3);}

TIO

Benjamin Urquhart
fonte
Acho que faltam alguns requisitos: Dê uma olhada na minha modificação aqui .
Shaq
Desconsidere o comentário de Shaq: sua resposta está correta e é a resposta Java mais curta possível (a partir do Java 12).
Olivier Grégoire
OK então. Não tenho certeza do que "perdi", mas tudo bem. Edit: nvm Eu li a resposta JS.
Benjamin Urquhart
2

R + pryr , 38 36 bytes

Função recursiva indexada a zero.

f=pryr::f(`if`(n<3,1,f(n-2)+f(n-3)))

Experimente online!

Obrigado a @ Giuseppe por apontar dois bytes obviamente desnecessários.

rturnbull
fonte
2
Se você estiver usando pryr, o idioma deve ser R + pryre pode ser de 36 bytes
Giuseppe
@Giuseppe thanks! Atualizado agora.
rturnbull 8/04