Project Euler 853 - Pisano Periods 1

Official link:

Thought Process

Fun problem, requires 3 facts.

(1) and (2) can be found on the Pisano Period Wikipedia page. The proof for (1) is simple, and (2) is conjectured to be true. (3) is extremely simple since if the period is of length n then that means Fn (mod p) = 0.

With these we can solve the problem by finding all primes such that π(p) divides n and then generating the multiples of all these numbers and checking if their period if equal to n.

A sketch of the algorithm is as follows:

The hardest part was to make an efficient multiples generator. I used recursion, I include the snippet of this function below.

Interactive Code

Input 2 integers seperated by a space (n, limit)

Code will output the sum of all numbers, x < limit, such that π(x) = n