Project Euler Problem 693
Two positive integers x and y (x y) can generate a sequence in the following manner: - ax = y is the first term, - a{z+1
Solution
Answer: 699161
A direct brute-force search over all pairs $(x,y)$ up to $3{,}000{,}000$ is impossible, but the problem has an important optimization:
For fixed $x$, instead of simulating every starting value $y$, track the set of all possible active values after each step:
$$A_{z+1}={a^2 \bmod z : a\in A_z}\setminus{0,1}.$$
The sequence length $g(x)$ is exactly the number of steps until this active set becomes empty.
Using:
- deduplication via
bytearray, - a singleton fast-path,
- and a branch-and-bound search for
$$f(n)=\max_{x\le n} g(x),$$
the computation finishes quickly and reproduces the given checks:
- $f(100)=145$,
- $f(10,000)=8824$.
Running the optimized program for $n=3{,}000{,}000$ yields:
Answer: 699161