← Complete problem index

PROJECT EULER · #0953

Factorisation Nim

Statement only · UnsolvedOriginal problem ↗

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×2×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 1nN 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(1014). Give your answer modulo 109+7.

Write-up coming later

The complete problem is available here. An approach, code, and answer will be added later.