Question 1

O que é a sequência de Fibonacci?

Accepted Answer

É a sequência de inteiros em que cada termo é a soma dos dois anteriores: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34... Define-se por F(n) = F(n−1) + F(n−2), com F(0) = 0 e F(1) = 1. Leonardo de Pisa, o Fibonacci, a apresentou na Europa em 1202 no Liber Abaci, num problema sobre a reprodução de coelhos. A sequência já era conhecida na matemática indiana, em estudos de métrica poética.

Question 2

A sequência começa em F(0) = 0 ou em F(1) = 1?

Accepted Answer

Depende da convenção, e as duas descrevem os mesmos valores. A definição moderna e a dos programas usa F(0) = 0 e F(1) = 1, o que deixa identidades como F(m+n) mais limpas e combina com índices de vetor começando em 0. Textos antigos começam em 1, 1, 2, 3, 5, deslocando o índice. No modo Sequência, a chave Começar em permite escolher; basta conferir qual convenção o seu livro ou exercício usa.

Question 3

O que é a fórmula de Binet e por que ela falha para n grande?

Accepted Answer

A fórmula de Binet é F(n) = (φⁿ − ψⁿ) / √5, com φ = (1 + √5)/2 e ψ = (1 − √5)/2. Ela é exata em matemática. Em ponto flutuante de 64 bits (double), porém, φⁿ ganha mais dígitos do que a mantissa guarda, e o arredondamento dá o inteiro errado a partir de F(71). Perto de n = 1475, φⁿ estoura e vira infinito. Com BigInt, por soma ou duplicação, o resultado é exato. O modo N-ésimo termo mostra as duas versões lado a lado.

Question 4

Qual a relação entre Fibonacci e a razão áurea?

Accepted Answer

A razão F(n+1)/F(n) converge para a razão áurea φ = (1 + √5)/2 ≈ 1,6180339887. O erro cai por um fator de cerca de 0,382 (1/φ²) a cada passo, e a razão fica alternadamente acima e abaixo de φ. Já 55/34 ≈ 1,6176 se aproxima, e com n = 30 são cerca de 12 casas decimais iguais. A convergência vale para qualquer par de sementes inteiras não nulas com a regra de soma, não só para 0 e 1.

Question 5

Fibonacci aparece mesmo na natureza?

Accepted Answer

Em alguns casos, sim, mas com ressalvas. Em girassóis, pinhas e abacaxis, o número de espirais em cada sentido costuma ser dois números de Fibonacci consecutivos, e o ângulo entre folhas sucessivas em muitas plantas fica perto de 137,5°, o ângulo áureo. Modelos de empacotamento explicam por que esse ângulo é eficiente. Mas há exceções, e não é verdade que tudo na natureza segue Fibonacci: a concha do nautilo, por exemplo, é uma espiral logarítmica cuja razão de crescimento não é a áurea.

Question 6

Fibonacci tem aplicações em computação?

Accepted Answer

Sim, em vários pontos. O heap de Fibonacci, de Fredman e Tarjan, é uma fila de prioridade com inserção e diminuição de chave em tempo amortizado constante; o nome vem da análise, em que o tamanho das árvores é limitado por números de Fibonacci. A busca de Fibonacci divide um vetor ordenado em partes de tamanhos de Fibonacci e também é logarítmica. Em árvores AVL, o menor número de nós para uma altura dada cresce como Fibonacci. E a recursão ingênua fib(n) é o exemplo clássico de complexidade exponencial: fib(30) faz 2.692.537 chamadas.

Question 7

Como calcular F(n) rápido, sem somar n vezes?

Accepted Answer

Pela duplicação rápida, que usa F(2k) = F(k)·(2·F(k+1) − F(k)) e F(2k+1) = F(k)² + F(k+1)². Cada passo dobra o índice, então F(n) sai com cerca de log₂(n) etapas de multiplicação de inteiros grandes, em vez de n somas. É equivalente à exponenciação da matriz [[1,1],[1,0]]. Esta ferramenta calcula F(100000), com 20899 dígitos, por esse método e mostra o tempo medido no seu navegador.

Question 8

Como saber se um número é de Fibonacci?

Accepted Answer

Um inteiro n ≥ 0 é de Fibonacci se, e somente se, 5n² + 4 ou 5n² − 4 é um quadrado perfeito. A ferramenta aplica esse teste com raiz quadrada inteira em BigInt, de modo que funciona até com números de 1000 dígitos. Se o número for de Fibonacci, mostra o índice. Se não for, mostra os termos vizinhos e a decomposição de Zeckendorf: todo inteiro positivo é, de forma única, uma soma de números de Fibonacci não consecutivos, como 100 = 89 + 8 + 3.

Question 9

O que é o período de Pisano e para que serve F(n) mod m?

Accepted Answer

Os resíduos de F(n) mod m formam uma sequência periódica, e o comprimento do ciclo é o período de Pisano π(m). Por exemplo, π(2) = 3, π(3) = 8, π(5) = 20 e π(10) = 60, ou seja, o último dígito dos números de Fibonacci repete a cada 60 termos. π(m) nunca passa de 6m. Isso permite achar F(n) mod m para n gigantesco reduzindo n módulo π(m), algo comum em problemas de programação competitiva. A ferramenta faz as duas contas e confere se coincidem.

Question 10

Até onde a ferramenta calcula e meus dados saem do navegador?

Accepted Answer

A lista de termos vai até 2000, o N-ésimo termo vai até n = 100000, o teste É Fibonacci? aceita até 1000 dígitos e o período de Pisano vai até m = 10000. Tudo usa BigInt, sem arredondamento de ponto flutuante nos valores. Os cálculos rodam no seu navegador e nenhum número digitado é enviado a servidor.

Índice	Valor	Paridade
F(0)	0	par
F(1)	1	ímpar
F(2)	1	ímpar
F(3)	2	par
F(4)	3	ímpar
F(5)	5	ímpar
F(6)	8	par
F(7)	13	ímpar
F(8)	21	ímpar
F(9)	34	par
F(10)	55	ímpar
F(11)	89	ímpar
F(12)	144	par
F(13)	233	ímpar
F(14)	377	ímpar
F(15)	610	par
F(16)	987	ímpar
F(17)	1597	ímpar
F(18)	2584	par
F(19)	4181	ímpar

Índice	Valor	Paridade
F(0)	0	par
F(1)	1	ímpar
F(2)	1	ímpar
F(3)	2	par
F(4)	3	ímpar
F(5)	5	ímpar
F(6)	8	par
F(7)	13	ímpar
F(8)	21	ímpar
F(9)	34	par
F(10)	55	ímpar
F(11)	89	ímpar
F(12)	144	par
F(13)	233	ímpar
F(14)	377	ímpar
F(15)	610	par
F(16)	987	ímpar
F(17)	1597	ímpar
F(18)	2584	par
F(19)	4181	ímpar

Gerador de Fibonacci

Gerador de Sequência de Fibonacci