Números pares de Fibonacci

Inspirado por um comentário em um post de Fibonacci para uma entrevista . O usuário pavellyzhin mencionou a seguinte tarefa de entrevista ( comentário ):

Mais de um ano atrás, o “programador de php” respondeu à vaga, eles enviaram TK e havia uma tarefa de Fibonacci: selecionar todos os números até Fibonacci no intervalo de 1 a 10000 . Decidido usando um loop (for). Lá, também foi necessário fazer uma consulta SQL para selecionar os aniversários mais próximos dos usuários, inventar algo, eu simplesmente não lembro e escrevi algum tipo de função. Eu fiz tudo, enviei. Eles enviaram uma resposta: "de acordo com os resultados da tarefa de teste, você não é aceito". O que exatamente eles não gostaram não foi escrito. Agora estou sentado e pensando, provavelmente depois de tudo por causa de Fibonacci eu voei ... :)

Neste post, mostrarei como foi possível resolver esse problema com eficiência, e talvez até com eficiência, mas isso não é exato. Ao mesmo tempo, demonstrarei alguns milhares de fatos comprovados sobre os números de Fibonacci.

Teorização

A melhor maneira de começar é olhar através dos olhos dos primeiros números de N Fibonacci e tentar encontrar um padrão na organização dos números pares.

$$

$$1,1, {\ bf 2}, 3,5, {\ bf 8}, 13,21, {\ bf 34}, 55,89, {\ bf 144}, \ ldots$$

Os números pares são marcados na sequência, como você pode ver todos os números do 3º Fibonacci são pares e, provavelmente, todos os números pares estão em posições de múltiplos de 3. Esse é o nosso palpite, agora precisamos confirmar e elaborar um algoritmo de cálculo.

A melhor prova é simples, então, graças ao AllexIn pela idéia simples que eu inicialmente perdi. Cada número subsequente de Fibonacci é a soma dos dois anteriores, se os dois números anteriores forem ímpares, o próximo será par; se nos dois números anteriores um for ímpar e o outro for par, o próximo será ímpar. Em princípio, essa idéia já é suficiente para "tatear intuitivamente" o fato comprovado. A prova por indução é óbvia, mas não consigo resistir, para não trazê-la

Provamos que "todo terceiro número de Fibonacci é par e os dois que precedem cada um desses números são ímpares".

• Indução de base . Primeiros dois números de fibonacci $$$1,1$ - ímpar, terceiro número $$$2$ - mesmo
• Hipótese . Suponha que até algum número múltiplo de Fibonacci seja 3, é verdade que cada terço é par e os dois anteriores são ímpares.
• Passo de indução . O número após o último par da hipótese é ímpar, porque é obtido da soma do ímpar com o par, após esse número já ser também ímpar, porque é obtido da soma do par com o ímpar e o próximo depois do par, porque os dois anteriores que ele recebeu são ímpares; por construção, seu número é múltiplo de 3; é par; e os dois anteriores são ímpares.

É assim que podemos provar nosso palpite sem sequer recorrer a cálculos matemáticos. Você pode formalizar essa ideia, ao mesmo tempo em que obtém uma fórmula para calcular cada terceiro número de Fibonacci $$$F_ {n + 3}$ de $$$F_n$ e $$$F_ {n + 1}$ . Usando a relação recursiva $$$F_ {n + 2} = F_ {n + 1} + F_ {n}$ nós obtemos:

$$

$$F_ {n + 3} = F_ {n + 2} + F_ {n + 1} = 2 F_ {n + 1} + F_n$$

Então se $$$F_n$ - mesmo assim $$$F_ {n + 3}$ também mesmo em virtude desta fórmula. Dado que $$$F_3 = 2$ , então todo terceiro número de Fibonacci é realmente par, o que confirma parte de nosso palpite. Aqui, você precisa garantir que não perdemos outros números pares, ou seja, que todos eles têm múltiplos de 3. Agradeço a janatem por sua idéia simples, porque da fórmula acima para $$$F_ {n + 3}$ segue-se também que se $$$F_n$ - estranho então $$$F_ {n + 3}$ também ímpar, então obtemos esses números com números $$$3k-2,3k-1, k \ in \ mathbb {N}$ - ímpar (por indução, comece com $$$F_1 = F_2 = 1$ - ímpar) e $$$3k, k \ in \ mathbb {N}$ - even, que abrange todos os números de Fibonacci, o que significa que realmente cobrimos todos os números pares.

Existe outra maneira, pois seria possível mostrar que não há outros números pares. Suponha que exista um número $$$F_m$ - par e $$$0 \ not \ equiv m \ mod 3$ então $$$m = 3 mil - 1$ ou $$$m = 3k + 1$ onde $$$k$ - algum tipo de natural.

Vamos voltar à representação matricial dos números de Fibonacci do post original

$$

$$\ begin {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} ^ n = \ begin {pmatrix} F_ {n-1} e F_n \\ F_n & F_ {n + 1} \ end {pmatrix}$$

Calculando o determinante de ambas as partes, obtemos

$$

$$(-1) ^ n = F_ {n + 1} F_ {n-1} -F_n ^ 2$$

Segue-se que os divisores de números $$$F_ {n + 1}, F_n$ e $$$F_ {n-1}, F_n$ divisores de jogo $$$(- 1) ^ n$ , ou seja, números de Fibonacci vizinhos são mutuamente simples. Isso também significa que simplicidade e números mútuos $$$F_ {3k}, F_ {3k-1}$ e $$$F_ {3k}, F_ {3k + 1}$ , ou seja, $$$F_ {3k}$ e $$$F_m$ . Mas por suposição $$$F_m$ - par e $$$F_ {3k}$ - mesmo como previamente comprovado. Portanto, outros números pares $$$F_ {3k}$ onde $$$k \ in \ mathbb {N}$ na sequência de Fibonacci não existe. E também estabelecemos um fato interessante de que os números vizinhos de Fibonacci são mútuos simples.

Finalmente, mostramos pelo menos mais uma maneira de provar nosso palpite: use o teorema de Lucas.

Teorema de Lucas . Número inteiro divide $$$F_m$ e $$$F_n$ , se e somente se for um divisor $$$F_d$ onde $$$d = \ gcd (m, n)$ em particular

$$

$$\ gcd (F_m, F_n) = F _ {\ gcd (m, n)}$$

Aqui $$$\ gcd$ É o maior fator comum. Se colocar $$$m = 3$ então $$$\ gcd (2, F_n) = F _ {\ gcd (3, n)}$ . Se $$$F_n$ - mesmo, então o lado esquerdo é 2, para que o lado direito também seja igual a 2, é necessário que $$$n$ dividido por 3 e ao mesmo tempo o oposto é verdadeiro. Assim, conseguimos exatamente o que queríamos provar.

Portanto, todo terceiro número de Fibonacci é par e todo par tem um múltiplo de três. Provamos isso com cuidado e ninguém ousa duvidar disso agora.

Algoritmo

E agora resta criar um algoritmo. Obviamente, você pode fazer o que o pavellyzhin fez originalmente, mas em vez de verificar $$$0 \ equiv. F_n \ mod 2$ nós podemos verificar $$$0 \ equiv n \ mod 3$ , isso é uma torção! É verdade que isso não afeta o número de iterações do algoritmo, porque acabamos de alterar o filtro de sequência. É melhor gerar imediatamente uma subsequência dos números de Fibonacci com a propriedade que precisamos (paridade), portanto, outra maneira óbvia é usar a fórmula Binet

$$

$$F_n = \ left \ lfloor \ frac {\ varphi ^ n} {\ sqrt {5}} \ right \ rceil, \ qquad n \ in \ {3,6, \ ldots, 3k \ ldots \}$$

Existem dificuldades com a eficiência dos cálculos, mais sobre isso no post original. Portanto, proponho o melhor, na minha opinião, método - cálculo iterativo $$$F_ {n + 3}$ , isso pode ser feito, como mostramos anteriormente, pela fórmula $$$F_ {n + 3} = 2F_ {n + 1} + F_n$ . Para construir uma transição iterativa no algoritmo, precisamos calcular $$$F_ {n + 4}$ , tudo é tão simples

$$

$$F_ {n + 4} = F_ {n + 3} + F_ {n + 2} = 2F_ {n + 1} + F_n + F_ {n + 1} + F_n = 3F_ {n + 1} + 2F_n$$

A propósito, de um modo geral, é fácil provar que

$$

$$F_ {n + m} = F_mF_ {n + 1} + F_ {m-1} F_n$$

Em seguida, formalmente, o algoritmo é escrito da seguinte forma (o atual número uniforme de Fibonacci $$$F_n$ seguido pelo número de Fibonacci $$$F_ {n + 1}$ , $$$M$ É o limite superior para números fornecidos na condição do problema):

1. $$$F_n \ leftarrow F_3 = 2, \ quad F_ {n + 1} \ leftarrow F_4 = 3$
2. Se $$$F_n> M$ , depois termine, caso contrário, adicione ao resultado $$$F_n$
3. $$$(F_n, F_ {n + 1}) \ leftarrow (2F_ {n + 1} + F_n, 3F_ {n + 1} + 2F_n)$ vá para o passo 2.

O algoritmo é bastante trivial - simplesmente saltamos para cada terceiro número de Fibonacci e o imprimimos (se não for mais $$$M$ ) A complexidade do algoritmo ainda é linear, mas o número de repetições da etapa 2 é exatamente igual ao número uniforme de números de Fibonacci no intervalo $$$1 \ ldots M$ , para comparação, um algoritmo simples com filtragem requer 3 vezes mais iterações (para cada encontrado, haverá 2 descartados).

O algoritmo existe no papel, qual foi a entrevista, PHP? Bem, finalmente descobrir PHP significa

function evenfibs($ubound) { $result = []; [$evenf, $nextf] = [2, 3]; while($evenf <= $ubound) { array_push($result, $evenf); [$nextf, $evenf] = [ 3 * $nextf + 2 * $evenf, 2 * $nextf + $evenf]; } return $result; } 

Nota : Esse método sempre pode ser aprimorado, como, por exemplo, o hunroll do usuário mostrou. A idéia é que, para cálculos, não precisamos de nada supérfluo, exceto pelo resultado parcialmente obtido, ou seja, podemos calcular números pares usando apenas os números pares anteriores de Fibonacci.

$$

$$F_ {n + 3} = 2F_ {n + 1} + F_ {n} = 3F_n + 2F_ {n-1} = 3F_n + F_ {n-1} + F_ {n-1} = \\ 3F_n + ( F_ {n-1} + F_ {n-2}) + F_ {n-3} = 4F_n + F_ {n-3}$$

 function evenfibs($ubound) { if($ubound < 2) return []; $evens = [2]; $next = 8; for($i = 1; $next <= $ubound; $i++) { $evens[$i] = $next; $next = $evens[$i]*4 + $evens[$i-1]; } return $evens; } 

Generalização

Mencionamos aqui o teorema de Lucas, que afirma que $$$\ gcd (F_m, F_n) = F _ {\ gcd (m, n)}$ . Como conseqüência disso, podemos obter que o número de Fibonacci $$$F_n$ múltiplo de $$$F_m$ , se e somente se seu número $$$n$ múltiplo para número $$$m$ . I.e. todo quarto número de Fibonacci é dividido por 3, todo quinto por 5, todo sexto por 8, etc.

Então, de uma maneira simples, obtemos um algoritmo para calcular a subsequência de Fibonacci, na qual os elementos são múltiplos de um determinado número $$$F_m$ . Usando o fato de que

$$

$$F_ {n + m} = F_mF_ {n + 1} + F_ {m-1} F_n \\ F_ {n + m + 1} = F_ {m + 1} F_ {n + 1} + F_mF_n$$

O algoritmo anterior se transforma em

1. $$$F_n \ leftarrow F_m, \ quadrante F_ {n + 1} \ leftarrow F_ {m + 1}$
2. Se $$$F_n> M$ , depois termine, caso contrário, adicione ao resultado $$$F_n$
3. $$$(F_n, F_ {n + 1}) \ leftarrow (F_mF_ {n + 1} + F_ {m-1} F_n, F_ {m + 1} F_ {n + 1} + F_mF_n)$ vá para o passo 2.

Onde $$$F_ {m-1}, F_m, F_ {m + 1}$ pode ser definido como constantes.

Resumo das notas . Como a ignorância do usuário observou corretamente, no caso generalizado, também é possível construir um algoritmo que usa apenas números de um resultado parcial.

$$

$$F_ {n + 1} = F_n + F_ {n-1} \\ F_ {n + 2} = 3F_ {n} - F_ {n-2} \\ F_ {n + 3} = 4F_ {n} + F_ {n-3} \\ F_ {n + 4} = 7F_ {n} - F_ {n-4} \\ F_ {n + 5} = 11F_ {n} + F_ {n-5} \\ \ cdots \\ F_ {n + t} = (F_t + 2F_ {t-1}) F_n + (-1) ^ {t-1} F_ {nt}$$

Vamos provar isso pelo método de indução matemática, para t = 1 e t = 2, o cumprimento é óbvio. Suponha que ele aguente alguns t; então

$$

$$F_ {n + t + 1} = F_ {n + t} + F_ {n + t-1} = \\ (F_t + 2F_ {t-1}) F_n + (-1) ^ {t-1} F_ {nt} + \\ (F_ {t-1} + 2F_ {t-2}) F_n + (-1) ^ {t-2} F_ {n-t + 1} = \\ (F_t + F_ { t-1} + 2 (F_ {t-1} + F_ {t-2})) F_n + (-1) ^ {t-1} (F_ {nt} -F_ {n-t + 1}) = \\ (F_ {t + 1} + 2F_t) F_n + (-1) ^ {t-1} (F_ {nt} -F_ {nt} -F_ {nt-1}) = \\ (F_ {t + 1} + 2F_t) F_n + (-1) ^ tF_ {nt-1}$$

Algo como um total

A tarefa, é claro, é completamente sintética, o número de iterações é muito pequeno (por $$$M = $ 10.00$ a resposta contém apenas 6 números, ou seja, 6 iterações teriam sido concluídas e o algoritmo "frontal" original exigiria 18), mas dessa maneira um usuário que descobriu algo novo aqui agora pode mostrar um conhecimento matemático um pouco mais profundo nos números de Fibonacci na entrevista.

Edit: Graças aos usuários do janatem e do AllexIn pelas provas simples, incluí-os em "Teorema", além de adotar o algoritmo usando apenas os números pares já obtidos nos cálculos e a ignorância do usuário em generalizá-lo.