Partida Rol por web

The sequence of nonnegative integers F₀; F₁; F₂;... is dened recursively as F₀ = 0, F₁ = 1, and F_n+2 = F_n+1 +F_n for all integers n >= 0. Let d be the largest positive integer such that, for all integers n >= 0, d divides F_n+2020 - F_n. Compute the remainder when d is divided by 1001.

The sequence of nonnegative integers F₀; F₁; F₂;... is defined recursively as F₀ = 0, F₁ = 1, and F_n+2 = F_n+1 +F_n for all integers n >= 0. Let d be the largest positive integer such that, for all integers n >= 0, d divides F_n+2020 - F_n. Compute the remainder when d is divided by 1001.

The sequence of nonnegative integers F₀; F₁; F₂;... is defined recursively as F₀ = 0, F₁ = 1, and F_n+2 = F_n+1 +F_n for all integers n >= 0. Let d be the largest positive integer such that, for all integers n >= 0, d divides F_n+2020 - F_n. Compute the remainder when d is divided by 1001.

The sequence of nonnegative integers F₀; F₁; F₂;... is defined recursively as F₀ = 0, F₁ = 1, and F_n+2 = F_n+1 +F_n for all integers n >= 0. Let d be the largest positive integer such that, for all integers n >= 0, d divides F_n+2020 - F_n. Compute the remainder when d is divided by 1001.

Lo que se me ha ocurrido hacer es lo siguiente. He empezado a escribir los términos Fn+2, Fn+3, Fn+4, etc. y he llegado a la siguiente conclusión:

Fn+a= Fibonacci[p]*Fn+1 + Fibonacci[p-1]*Fn

donde Fibonacci[p] es el p-ésimo término de la sucesión de Fibonacci. En el enunciado nos nombran el término Fn+2020, de manera que sería

Fn+2020 = Fibonacci[2020]*Fn+1 + Fibonacci[2019]*Fn

Los términos 2020 y 2019 de la sucesión son bastante gigantes, así que me generó la duda de si esto está bien realizado o no... No sé cuál es la dificultad de estos problemas y cómo son los números con los que se trabaja. Bueno, pese a ello terminé de calcularlo: Cómo se nos dice que d es el mayor divisor de Fn+2020-Fn para cualquier n, entonces calculé el máximo común divisor de Fibonacci[2020] y (Fibonacci[2019]-1)  (el -1 viene del Fn+2020 - ---->Fn<-----), el cuál nuevamente es un número bastante bastante grande.

Por último, calculé el resto entre ese número gigante y 1001 y me ha quedado 638.

Anotaciones:

1. Según las reglas de OMO el resultado final es el que no puede ser un número gigante, pero en principio no dice nada de lso resultados intermedios xD... Así que no sé si estará bien o si no.

2. No soy matemático, ni un experto en estos temas, así que no sé la validez de la solución.. pero lo aporto por si pudiera ser de utilidad. Además, he usado el programa Mathemática para obtener el número de Fibonacci 2020 y 2019. Se podría calcular fácilmente en un bucle sumando... pero bueno, me he ahorrado el hacer el programa xD

Saludos!

Lo que se me ha ocurrido hacer es lo siguiente. He empezado a escribir los términos Fn+2, Fn+3, Fn+4, etc. y he llegado a la siguiente conclusión:

Fn+a= Fibonacci[p]*Fn+1 + Fibonacci[p-1]*Fn

Yo había llegado a la misma conclusión, pero es verdad que los términos 2020 y 2019 eran astronómicos, así que aparqué el problema y pasé a otro.

Como el planteamiento que le has dado es el mismo que esperaba darle yo, sólo puedo mostrarme de acuerdo, confiando en que no haya ningún error en las cuentas.

Según tengo entendido, si mal no recuerdo de cuando estudiaba, la cosa curiosa de la sucesión de Fibonacci es que la suma de 10 términos consecutivos cualesquiera siempre da un valor igual al séptimo elemento por 11.

Así, si piden los 2020 valores, el resultado siempre será divisible por 11.si os fijáis, luego piden dividirlo por 1001,que también es divisible por 11 (91*11). Eso simplifica un poco la operación.

Según eso, partimos de la base de que el número será divisible por 91 y por 11,con lo que seguro que descompuesto en primos el cálculo se podía hacer más sencillo.

¿Por qué digo esto? Pues bien, porque no te piden que expliques la resolución, ergo sabiendo eso podemos poner la solución y, si preguntan, decir que usamos primos.

udas, no entiendo lo que dices.

El resultado que pones de la suma de los 10 términos consecutivos es interesante, pero aquí no piden la suma de los 2020 primeros términos, sino que piden cuál será el máximo común divisor de cualquier resultado de hacer: F₂₀₂₀-F₀, F₂₀₂₁-F₁, F₂₀₂₂-F₂, F₂₀₂₃-F₃,...

Yo me había planteado algo similar a lo que dice Lelouch, pero por desgracia esos número bastante gigantes se me iban de rango. Así pues, estaba pensando si plantearlo a través de la fórmula general de la sucesión.

¿Puedes explicarte un poco más, udas? Porque no veo cómo aplicar lo que dices al problema.

No hablo de aplicarlo al problema. El problema ya está resuelto:

Cita:

Lo que digo es que, si no entiendo mal, no nos deberían pedir como lo solucionamos, pero que si queréis probar algún sistema más sencillo se puede usar esa característica.

¿Cómo se usaría?