Project Euler Problem 853 Solution

Project Euler Problem 853 Statement

For every positive integer $n$ the Fibonacci sequence modulo $n$ is periodic. The period depends on the value of $n$. This period is called the Pisano period for $n$, often shortened to $\pi(n)$.

There are three values of $n$ for which $\pi(n)$ equals $18$: $19$, $38$ and $76$. The sum of those smaller than $50$ is $57$.

Find the sum of the values of $n$ smaller than $1\,000\,000\,000$ for which $\pi(n)$ equals $120$.

Solution

For every positive integer $n$ the Fibonacci sequence modulo $n$ is periodic, and this period is called the Pisano period, denoted $\pi(n)$. The problem asks to find the sum of all integers $n\lt 10^9$ for which the Pisano period $\pi(n)$ equals 120. This involves identifying all such $n$ and computing their sum.

The solution involves finding all integers \( n < 10^9 \) for which the Pisano period \( \pi(n) \) equals 120. By leveraging properties of Fibonacci numbers and their divisors, the code computes the greatest common divisor (GCD) of specific Fibonacci terms and uses it to identify valid \( n \). It excludes divisors that do not satisfy the Pisano period condition and sums the remaining valid \( n \).

1. Pisano Period Properties:
   • The Pisano period \( \pi(n) \) depends on the prime factorization of \( n \).
   • If \( n = p_1^{k_1} p_2^{k_2} \dots p_m^{k_m} \), then \( \pi(n) \) is the least common multiple (LCM) of the Pisano periods of the prime powers: $$ \pi(n) = \text{LCM}(\pi(p_1^{k_1}), \pi(p_2^{k_2}), \dots, \pi(p_m^{k_m})). $$
2. Pisano Period for Prime Powers:
   • For a prime \( p \), \( \pi(p^k) \) divides \( p^{k-1} \cdot \pi(p) \).
   • The Pisano period for a prime \( p \) is often related to the multiplicative order of certain matrices or eigenvalues modulo \( p \).
3. Goal:
   • We need to find all \( n < 10^9 \) such that \( \pi(n) = 120 \).

To solve this problem, we need to:

1. Factorize 120: \[ 120 = 2^3 \cdot 3 \cdot 5. \] This means that \( \pi(n) = 120 \) if and only if the LCM of the Pisano periods of the prime powers in the factorization of \( n \) equals 120.
2. Find Primes with Specific Pisano Periods:
   • We need to find primes \( p \) such that \( \pi(p) \) divides 120.
   • For each such prime, we can compute the maximum power \( k \) such that \( \pi(p^k) \) divides 120.
3. Construct Valid \( n \):
   • Combine the valid prime powers to form \( n \) such that \( \pi(n) = 120 \).
4. Sum All Valid \( n \):
   • Sum all \( n \lt 10^9 \) that satisfy the above conditions.

1. Imports and Initialization:

   from math import gcd
   from sympy import divisors, fibonacci
   n = 120

   • gcd: Used to compute the greatest common divisor.
   • divisors: Used to find all divisors of a number.
   • fibonacci: Used to compute Fibonacci numbers.
   • n = 120: The target Pisano period.
2. Base Function:

   base = lambda i: divisors(gcd(fibonacci(i), fibonacci(i + 1) - 1))

   • This function computes the divisors of \( \gcd(F_i, F_{i+1} - 1) \), where \( F_i \) is the \( i \)-th Fibonacci number.
   • This is related to the Pisano period because \( \gcd(F_i, F_{i+1} - 1) \) often reveals properties of the Pisano period.
3. Excluded Divisors:

   excluded = {x for d in divisors(n) if d < n for x in base(d)}

   • This set comprehension generates a set of divisors that should be excluded from the final result.
   • It iterates over all divisors \( d \) of 120 (where \( d \lt 120 \)) and computes the divisors of \( \gcd(F_d, F_{d+1} - 1) \) using the base function.
   • These divisors are added to the excluded set.
4. Result Calculation:

   result = (d for d in base(n) if d not in excluded and d < 10**9)

   • This generator expression computes the final result.
   • It iterates over all divisors \( d \) of \( \gcd(F_{120}, F_{121} - 1) \) (computed using the base function).
   • It includes only those divisors \( d \) that are not in the excluded set and are less than \( 10^9 \).
5. Output:

   print(sum(result))

   • The code sums all the divisors that meet the conditions and prints the result.