fundo
Muitos de vocês sabem o que é um número de Fibonacci . Alguns de vocês devem saber que todos os números inteiros positivos podem ser representados como uma soma de um ou mais números distintos de Fibonacci, de acordo com o Teorema de Zeckendorf . Se o número de termos na representação ideal de Zeckendorf de um número inteiro n
for ele próprio um número de Fibonacci, chamaremos n
Fibonacci "secretamente".
Por exemplo:
139 = 89 + 34 + 13 + 3
This is a total of 4 integers. Since 4 is not a Fibonacci number, 139 is not secretly Fibonacci
140 = 89 + 34 + 13 + 3 + 1
This is a total of 5 integers. Since 5 is a Fibonacci number, 140 is secretly Fibonacci
Notas
- A representação ideal de Zeckendorf pode ser encontrada usando um algoritmo guloso. Basta pegar o maior número de Fibonacci <= n e subtraí-lo de n até chegar a 0
- Todos os números de Fibonacci podem ser representados como uma soma de 1 número de Fibonacci (ele mesmo). Como 1 é um número de Fibonacci, todos os números de Fibonacci também são secretamente Fibonacci.
Desafio
Seu desafio é escrever um programa ou função que use um número inteiro e retorne se esse número inteiro é secretamente Fibonacci.
Entrada
Você pode receber informações em qualquer formato razoável. Você pode assumir que a entrada será um único número inteiro positivo.
Saída
Saída de um dos dois resultados distintos para saber se a entrada é secretamente Fibonacci. Exemplos incluem True
/ False
, 1
/ 0
, etc.
Pontuação
Isso é código-golfe , então a resposta mais curta em bytes vence! As brechas padrão são proibidas.
Casos de teste
Truthy (secretly Fibonacci)
1
2
4
50
140
300099
Falsey (NOT secretly Fibonacci)
33
53
54
139
118808
fonte
Respostas:
JavaScript (Node.js) , 54 bytes
Experimente online!
fonte
Python 2 , 77 bytes
Experimente online!
Isso faz uso do teorema de que as duas descrições do OEIS A003714 são equivalentes:
z
Resta verificar se
z[n]
é um número de Fibonacci, ou sejaz[z[n]] == 1
.fonte
bin(x)
. Você também pode remover um alterandorange(n*n+1)
pararange(n<<n)
. (Supondo que 0 é inválido)bin(x)
, haha. E, hm,1<<n
já é muito, muito mais do que suficiente, mas eu gostaria de manter o tempo de execução não-astronômicoGelatina , 15 bytes
Um link monádico que aceita um número inteiro não negativo que produz
1
se "secretamente Fibonacci" e0
outros.Experimente online! (muito ineficiente para os casos de teste maiores)
Quão?
fonte
R , 83 bytes
Experimente online!
fonte
C # (.NET Core) ,
12411598 bytesExperimente online!
-3 bytes: mudou o loop while para for (graças a Olivier Grégoire )
-6 bytes: retornos comutados para usar a variável inicializada bec fora dos loops (graças a Kevin Cruijssen )
-17 bytes: condição alterada no segundo loop para mover se fora do loop e combine com retorno, variáveis reutilizadas bec no último loop (graças ao raznagul )
Ungolfed:
fonte
for(;c<=a;b=c-b)c+=b;
você economizará 3 bytes.{}
Tirei todos os suportes de seus loops e coloquei tudo emfor
-loops. Além disso, adicionei uma variávelr
que definimos1
no seuif(e==n)
e retornamos no final, para que você tenha apenas umreturn
.e<n
que você pode mover aif
para após o loop e consequentlly combiná-lo com oreturn
de 101 bytes .b
ec
no último loop e removendod
ee
.Perl 6 , 58 bytes
Experimente online!
1, &[+] ... * > $_
é apenas a sequência de Fibonacci, parada em um local não-infinito conveniente (o número de entrada).$_, { $^n - (1, &[+] ...^ * > $n).tail } ... 0
é uma sequência de números, começando com o número de entrada, e cada elemento sucessivo obtido subtraindo o maior número de Fibonacci menor ou igual ao elemento anterior do elemento anterior. A sequência termina quando0
é alcançada. Por exemplo, se$_
estiver140
, então esta sequência é140, 51, 17, 4, 1, 0
.Subtrair um desta sequência o trata como um número, seu comprimento e a diferença é o número de números de Fibonacci que, somados, fornecem o número de entrada. Em seguida, esse número é verificado para associação na primeira sequência de Fibonacci.
fonte
&[+]
antes! Bom economizar em não ter que definir dois termos iniciaisPerl 6 , 48 bytes
Experimente online!
Transforma a entrada em uma lista de Representações Zeckendorf repetidamente até atingir um único número e depois verifica se o comprimento da sequência foi menor que 4.
A função Zenckendorf no meio é principalmente da resposta de Sean com algumas melhorias.
Explicação:
Por exemplo, a sequência para
2
é que2 1
já2
é um número de Fibonacci. A sequência para140
é140 5 1
e, como 5 é um número de Fibonacci, isso retorna verdadeiro. A sequência para33
é33 4 2 1
e, como4
não é um número de Fibonacci, a sequência tem comprimento 4.fonte
05AB1E , 14 bytes
Experimente online . Não há suíte de testes para todos os casos de teste, porque o
counter_variable
não pode ser redefinido para 0. No entanto, verifiquei tudo manualmente e eles estão corretos.Explicação:
NOTA:
counter_variable
Seria5
para entrada139
e6
para entrada140
, porque, para que oΔ
loop-verifique a pilha permaneceu a mesma, é claro que faz uma iteração adicional.fonte
Haskell , 64 bytes
Experimente online!
fonte
Retina 0.8.2 , 61 bytes
Experimente online! O link inclui casos de teste. Explicação:
Converta para unário.
Conte o número de números de Fibonacci necessários.
A primeira alternância lida com números de Fibonacci que são pelo menos 2. Na primeira passagem,
\2
ainda não existe, mas felizmente é opcional, portanto, não precisamos correspondê-la.\1
também não existe, mas, felizmente, temos a alternativa\G.
que corresponde a um único caractere no início da partida. Ambos\2
e,\1
portanto, assumem o valor 1.Nos passes subsequentes,
\2
existe, então tentamos combiná-lo. Desta vez, se falhar,\1
também falhará (já que é maior que\2
), mas se for bem-sucedido, o(?>)
impedirá de voltar atrás; portanto, se\2
corresponder, mas\1
não, não tentamos apenas\1
. (\G1
sempre falha desde que avançamos após o início do patch.) Finalmente\2
assume o valor anterior de\1
while\1
assume a soma dos dois valores.Portanto, combinamos o maior número possível de Fibonacci, adicionando à medida que avançamos. Como as somas parciais da sequência
1, 2, 3, 5...
são,0, 1, 3, 6, 11...
ou seja, 2 menores que os números de Fibonacci, terminamos combinando 2 no final.Obviamente, isso não corresponde a 1, então uma alternância lida com esse caso.
Converta para unário.
Teste se este é um número de Fibonacci. Isso usa a mesma idéia do primeiro teste, mas usa em
^
vez de\G
e também precisamos corresponder exatamente, portanto, usa uma captura opcional em vez de uma alternância, pois é mais golfista (mas aumenta os números de captura em 1).Retina , 35 bytes
Experimente online! O link inclui casos de teste. Explicação:
Converta para unário.
Conte o número de números de Fibonacci necessários. (Fazer um loop na conversão e na contagem economiza um byte inteiro, deixando a contagem unária em primeiro lugar.)
Execute as etapas anteriores duas vezes no total. Isso leva a contagem de números de Fibonacci necessária para somar à contagem de números de Fibonacci.
Se o número era secretamente Fibonacci, o resultado é 1.
fonte
Python 2 ,
146137 bytesExperimente online!
f () é uma função recursiva que retorna o valor do enésimo número de Fibonacci. Retirado desta resposta .
g () é uma função recursiva que retorna a representação Zeckendorf do número fornecido como uma lista de números inteiros.
Como todos os números de Fibonacci terão um comprimento de retorno de um item de g (), h () verifica se o comprimento de g () de g (n) == 1.
EDIT: Salvo 9 bytes graças a nedla2004 . Fico esquecendo que as lambdas nem sempre são a melhor solução ...
fonte
g
uma função para que eu pudesse definirf(n-1)
uma variável. Algumas outras mudanças a partir==
de<
onde eles são os mesmos.