Project Euler Problem 823
A list initially contains the numbers 2, 3, dots, n.
Solution
Answer: 865849519
A convenient way to model the process is to represent each number by its multiset of prime factors in nondecreasing order.
At each round:
- remove the first (smallest) prime factor from every list,
- collect those removed primes,
- sort them and append them as a new list,
- delete empty lists.
If we ignore the actual prime values and only track the lengths of the factor lists, the evolution becomes exactly the classical Bulgarian solitaire process:
- every pile decreases by 1,
- and a new pile of size “number of piles” is added.
The key observation is that after a transient phase, the $k$-th smallest prime factor of the newly created number becomes periodic with period $k$. This allows the state at an enormous round count $m=10^{16}$ to be reconstructed from short cyclic buffers rather than direct simulation.
Using that approach (and verifying the given examples $S(5,3)=21$ and $S(10,100)=257$), we obtain:
$$S(10^4,10^{16}) \bmod 1234567891 = 865849519.$$
Answer: 865849519