1, 2, 4, 8, 16, ... 33?

24

Desafio

Escreva uma função / programa que emita o n'th elemento, ou o primeiro nelemento, na conhecida sequência numérica:

         1, 2, 4, 8, 16 ...

Ah, espere ... esqueci os primeiros números:

1, 1, 1, 1, 2, 4, 8, 16 ...

Heck, vou adicionar mais alguns para uma boa medida:

1, 1, 1, 1, 2, 4, 8, 16, 33, 69, 146, 312, 673, 1463, 3202, 7050, 15605, 34705 ...

Os números são números catalães generalizados dados pela fórmula (indexada a zero):

a(n+1)=a(n)+k=2n1a(k)a(n1k)

Onde

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

Este é o OEIS A004149 .

Você pode escolher se deseja que a sequência seja indexada em zero ou um. A sequência deve, é claro, ser a mesma, portanto, você deve reescrever a fórmula se a tiver um indexado.

Stewie Griffin
fonte
Corrija-me se estiver errado aqui, mas a modificação de uma fórmula de um índice é mudar a(n-1-k)para a(n-k), correto?
Sumner18 19/09
9
Isso me lembra a forte lei dos pequenos números
Luis Mendo

Respostas:

23

Python , 51 bytes

f=lambda n,k=2:n<3or k<n and f(k)*f(n-k-2)+f(n,k+1)

Experimente online!

Simplifica um pouco a fórmula:

uma(n)=k=2n-1uma(k)uma(n-2-k)

uma(-1)=uma(0 0)=uma(1)=uma(2)=1

xnor
fonte
8
Parabéns pelos 100k !!
Stewie Griffin
Desde que eu também cheguei a esta solução de forma independente, devo dizer que o caminho para ela é um pouco acidentado ...
Erik the Outgolfer
10

Perl 6 , 44 bytes

{1,1,1,1,{sum @_[2..*]Z*@_[@_-4...0,0]}...*}

Experimente online!

Bloco de código anônimo que retorna uma sequência infinita e lenta de valores. Isso praticamente implementa a sequência como descrita, com o atalho que ele zip multiplica todos os elementos até agora após o segundo elemento, com o reverso da lista começando no quarto elemento e adicionando um extra 1no final.

Explicação:

{                                          }  # Anonymous code block
                                       ...*   # Create an infinite sequence
 1,1,1,1,                                     # Starting with four 1s
         {                            }       # Where each new element is:
          sum                                   # The sum of
              @_[2..*]                          # The second element onwards
                      Z*                        # Zip multiplied with
                        @_[@_-4...0  ]          # The fourth last element backwards
                                   ,0           # And 1
Brincadeira
fonte
10

05AB1E , 14 13 11 bytes

$ƒˆ¯Âø¨¨¨PO

Experimente online!

Gera o enésimo elemento, indexado em 0.

$                # push 1 and the input
 ƒ               # repeat (input+1) times
  ˆ              #  add the top of the stack (initially 1) to the global array
   ¯             #  push the global array
    Â            #  and a reversed copy of it
     ø           #  zip the two together, giving a list of pairs
      ¨¨¨        #  drop the last 3 pairs
         P       #  take the product of each pair (or 1 if the list is empty)
          O      #  take the sum of those products
                 #  after the last iteration, this is implicitly output;
                 #  otherwise, it's added to the global array by the next iteration
Grimmy
fonte
7

JavaScript (ES6), 42 bytes

Uma porta da solução do xnor .

Indexado a 0.

f=(n,k=2)=>n<3||k<n&&f(k)*f(n+~++k)+f(n,k)

Experimente online!


JavaScript (ES6),  83  75 bytes

Uma solução mais rápida, menos recursiva, mas significativamente mais longa.

Indexado a 0.

f=(n,i,a=[p=1])=>a[n]||f(n,-~i,[...a,p+=(h=k=>k<i&&a[k]*a[i-++k]+h(k))(2)])

Experimente online!

Arnauld
fonte
7

Haskell, 49 43 39 bytes

a n=max(sum[a k*a(n-2-k)|k<-[2..n-1]])1              

Experimente online!

Para n<3o sumé 0, então max ... 1aumenta para 1.

Edit: -6 bytes graças a @Jo King.

nimi
fonte
6

Wolfram Language (Mathematica) , 36 bytes

Sum[#0@i#0[#-i-1],{i,3,#-1}]/. 0->1&

Experimente online!

1 indexado.

A sequência 2-indexada é 4 bytes mais curto: Sum[#0@i#0[#-i],{i,#-4}]/. 0->1&. Experimente online!

attinat
fonte
2
Impressionante que isso seja mais curto que o embutido CatalanNumber!
erfink 20/09
6

05AB1E , 17 13 bytes

4Å1λ£₁λ¨Â¦¦s¦¦*O+

Não menor que a resposta 05AB1E existente , mas eu queria experimentar a funcionalidade recursiva da nova versão 05AB1E como prática para mim. Talvez pudesse ser jogado por alguns bytes. EDIT: E de fato pode, consulte a versão recursiva de @Grimy resposta 05AB1E 's abaixo, que é 13 bytes .

n

n£è
£

Explicação:


uma(n)=uma(n-1)+k=2n-1(uma(k)uma(n-1-k))

uma(0 0)=uma(1)=uma(2)=uma(3)=1

   λ               # Create a recursive environment,
    £              # to output the first (implicit) input amount of results after we're done
4Å1                # Start this recursive list with [1,1,1,1], thus a(0)=a(1)=a(2)=a(3)=1
                   # Within the recursive environment, do the following:
      λ            #  Push the list of values in the range [a(0),a(n)]
       ¨           #  Remove the last one to make the range [a(0),a(n-1)]
        Â          #  Bifurcate this list (short for Duplicate & Reverse copy)
         ¦¦        #  Remove the first two items of the reversed list,
                   #  so we'll have a list with the values in the range [a(n-3),a(0)]
           s       #  Swap to get the [a(0),a(n-1)] list again
            ¦¦     #  Remove the first two items of this list as well,
                   #  so we'll have a list with the values in the range [a(2),a(n-1)]
              *    #  Multiply the values at the same indices in both lists,
                   #  so we'll have a list with the values [a(n-3)*a(2),...,a(0)*a(n-1)]
               O   #  Take the sum of this list
               +  #  And add it to the a(n-1)'th value
                   # (afterwards the resulting list is output implicitly)

Versão de 13 bytes do @Grimy (certifique-se de votar sua resposta se ainda não o fez!):

1λ£λ1šÂ¨¨¨øPO

n


1λèλ1šÂ¨¨¨øPO
λλ1šÂ¨¨¨øPOuma(0 0)=1

Explicação:


uma(n)=k=2n-1(uma(k)uma(n-2-k))

uma(-1)=uma(0 0)=uma(1)=uma(2)=1

 λ             # Create a recursive environment,
  £            # to output the first (implicit) input amount of results after we're done
1              # Start this recursive list with 1, thus a(0)=1
               # Within the recursive environment, do the following:
   λ           #  Push the list of values in the range [a(0),a(n)]
    1š         #  Prepend 1 in front of this list
      Â        #  Bifurcate the list (short for Duplicate & Reverse copy)
       ¨¨¨     #  Remove (up to) the last three value in this reversed list
          ø    #  Create pairs with the list we bifurcated earlier
               #  (which will automatically remove any trailing items of the longer list)
           P   #  Get the product of each pair (which will result in 1 for an empty list)
            O  #  And sum the entire list
               # (afterwards the resulting list is output implicitly)
Kevin Cruijssen
fonte
1
Interessante que isso possa resolver um (1200) em 40 segundos em tio, enquanto outras abordagens recursivas atingem o tempo limite para números n além de 100 ...
Stewie Griffin
1
Também fiz (mas não publiquei) uma versão recursiva. São 13 bytes para os primeiros n termos ou 11 bytes para uma lista infinita . A caixa especial a (n-1) custa muitos bytes e não é necessária (veja, por exemplo, a fórmula do xnor ).
Grimmy 20/09
@ Grimy Você se importa se eu adicionar suas soluções recursivas à minha resposta (creditando você, é claro)? Vou deixar minha resposta original também. Mas é bom ver as diferenças entre a fórmula original e a fórmula de economia de bytes do xnor. :)
Kevin Cruijssen 20/09
1
Claro, tudo bem!
Grimmy 20/09
@ StewieGriffin Sim, também fiquei impressionado com a velocidade dessas funções infinitas recursivas. Talvez um dos pontos fortes de Elixir, e definitivamente devido ao carregamento preguiçoso embutido. Ele calcula n=100em 0,65 segundos , mas quando desativo o carregamento lento, o tempo limite é excedido após 60 segundos, mesmo paran=25 .
Kevin Cruijssen 20/09
5

Python 3 , 59 bytes

realmente ineficiente, a(13)não termina no TIO.

a=lambda n,k=2:n<4or(n-k<2)*a(n-1)or a(k)*a(n-k-2)+a(n,k+1)

Experimente online!

ovs
fonte
2

Haskell , 76 bytes

1:1:1:f[1,1,1]
f(x:z)|y<-x+sum(zipWith(*)(init$init z)$reverse z)=y:f(y:x:z)

Experimente online!

flawr
fonte
2

Japt , 19 17 16 bytes

Gera o ntermo th, indexado em 1.

@Zí*Zz2)Ťx}g4Æ1

Tente

@Zí*Zz2)Ťx}g4Æ1     :Implicit input of integer U
@                    :Function taking an array as an argument via parameter Z
 Zí                  :  Interleave Z with
    Zz2              :  Z rotated clockwise by 180 degrees (simply reversing would be a bye shorter but would modify the original array)
   *                 :  Reduce each pair by multiplcation
       )             :  End interleave
        Å            :  Slice off the first element
         ¤           :  Slice off the first 2 elements
          x          :  Reduce by addition
           }         :End function
            g        :Pass the following as Z, push the result back to it and repeat until it has length U
             4Æ1     :Map the range [0,4) to 1s
                     :Implicit output of the last element
Shaggy
fonte
1

Haskell , 65 bytes

f a|a<4=1|z<-g[2..a]=sum$zipWith(*)z$reverse(1:g[0..a-4])
g=map f

Experimente online!

Você pode usar fpara obter um único elemento de uma sequência ou passar uma lista de valores para ge obter todos os índices dessa lista.

Brincadeira
fonte
1

Quarto (gforth) , 99 81 bytes

: f recursive dup 4 > if 0 over 3 do over 1- i - f i f * + loop else 1 then nip ;

Experimente online!

A saída é o enésimo termo e a entrada é indexada 1

Editar: salvou 17 bytes mudando para a fórmula do xnor. Salvou outro byte usando 1 indexado por 1

Código Explicação

: f                     \ start a new word definition
  recursive             \ mark that this word will be recursive
  dup 4 >               \ duplicate the input and check if it is greater than 4
  if                    \ if it is:
    0 over              \ create an accumulator and copy n to top of stack
    3 do                \ start counted loop from 3 to n-1
      over 1- i - f     \ recursively calculate f(n-1-i)
      i f               \ recursively calculate f(i)
      * +               \ multiply results and add to accumulator
    loop                \ end the counted loop        
  else                  \ otherwise, if n < 5
    1                   \ put 1 on the stack
  then                  \ end the if block
  nip                   \ drop n from the stack
;                       \ end the word definition
reffu
fonte
1

Carvão , 26 bytes

F⁵⊞υ¹FN⊞υΣ✂E⮌υ×κ§υλ³→I§υ±⁴

Experimente online! Link é a versão detalhada do código. Imprime o número n-ésimo indexado, embora calcule usando a indexação 1 internamente. Explicação:

F⁵⊞υ¹

Comece com a[0] = a[1] = a[2] = a[3] = a[4] = 1. Sim, isso é indexado em 1, mas com um valor extra de zero. Isso é código de golfe para você.

FN

Calcular ntermos adicionais . Isso é um exagero, mas torna mais fácil encontrar o termo desejado n<5.

⊞υΣ✂E⮌υ×κ§υλ³

Para cada termo, calcule o próximo termo como a soma dos termos até agora multiplicados pelo reverso dos termos até o momento, excluindo três termos.

Este é um no-op usado para enganar o carvão vegetal na análise da forma de 2 argumentos Slice, caso contrário, eu teria que usar uma maneira menos eficiente de remover três termos.

I§υ±⁴

Saída do quarto último termo.

Neil
fonte
1

Pitão , 30 bytes

J*4]1VQ=+J+eJsPP*M.t,PJ_PJ0;<J

Experimente online!

n

J*4]1VQ=+J+eJsPP*M.t,PJ_PJ0;<JQ # Full program, last Q = input (implicitly added)
J*4]1                  # J = 4 * [1] (=[1,1,1,1])
VQ                     # for N in range(Q):
  =+J                  #  J +=
     +eJ               #   J[-1] + 
        s              #    sum(                           )
           *M          #     map(__operator_mul,          )
             .t      0 #      transpose(          , pad=0)
               ,       #       [       ,         ]
                PJ     #         J[:-1] 
                  _PJ  #                 J[1::-1]
<JQ                    # J[::Q]

<@n

ar4093
fonte
1

Oitava , 73 bytes

g=(1:4).^0;for(i=3:(n=input('')))g(i+2)=g(4:i+1)*g(i-(2:i-1))';end;g(end)

Experimente online!

-2 bytes graças a Stewie Griffin. Mais uma vez, a abordagem imperativa vence a abordagem recursiva funcional. Esse é mostrado abaixo.

Oitava , 75 bytes

f(f=@(a)@(n){@()sum(arrayfun(@(k)a(a)(k)*a(a)(n-2-k),2:n-1)),1}{2-(n>3)}())

Experimente online!

Captcha queria verificar se eu era humano ao postar isso. Para ser sincero, não tenho tanta certeza .

Sanchises
fonte
Não vejo maneiras óbvias de encurtar a abordagem de loop ... Parece muito bem jogado! Além disso, muitas vezes não vejo a indexação baseada em zero no Octave :)
Stewie Griffin
@StewieGriffin Desde a recursão tem algumas compensações ele não realmente importa se você escolher zero ou uma indexação. Acho que talvez eu pudesse raspar alguns bytes se fizesse a indexação em 2, mas isso parecia trapaça. De qualquer forma, sua intuição estava certa - de alguma forma, essa foi realmente mais curta de uma maneira recursiva anônima. Eu acho que a principal vantagem é que ele lida com a criação dos quatro valores iniciais muito bem, porque apenas retorna 1 para n<4.
Sanchises
1
@ StewieGriffin Claro, boa e velha multiplicação de matrizes. Bem feito!
Sanchises
0

C / C ++ , 70 69 67 bytes

-1 bytes graças a Jonathan.

int a(int n){int k=2,s=0;while(++k<n)s+=a(k)*a(n+~k);return s?s:1;}

Experimente online!

polfosol ఠ_ఠ
fonte
Pode a(n-1-k)ser a(n+~k)?
Jonathan Frech 21/09
a(++k)*a(n-k)É provável que @JonathanFrech funcione, e ele solta mais 2 bytes de for. Mas sinto cheiro de comportamento indefinido.
polfosol ఠ_ఠ 21/09
Isso parece ser um problema de seqüenciamento; definitivamente UB.
Jonathan Frech 21/09