P953
projecteuler.net

Factorisation Nim

ℹ️Published on Sunday, 6th July 2025, 05:00 am; Solved by 208;
Difficulty level: 23

In the classical game of Nim two players take turns removing stones from piles. A player may remove any positive number of stones from a single pile. If there are no remaining stones, the next player to move loses.

In Factorisation Nim the initial position of the game is chosen according to the prime factorisation of a given natural number $n$ by setting a pile for each prime factor, including multiplicity. For example, if $n=12=2 \times 2 \times 3$ the game starts with three piles: two piles with two stones and one pile with three stones.

It can be verified that the first player to move loses for $n=1$ and for $n=70$, assuming both players play optimally.

Let $S(N)$ be the sum of $n$ for $1 \le n \le N$ such that the first player to move loses, assuming both players play optimally. You are given $S(10) = 14$ and $S(100) = 455$.

Find $S(10^{14})$. Give your answer modulo $10^9 + 7$.



Soluzione

Last modified: February 25, 2026. Website built with Franklin.jl and the lovely Julia programming language.