Solution

Answer: 885722296

Project Euler Problem 984 is “Knights and Horses”.

Problem statement

In Western chess, a knight is a piece that moves either two squares horizontally and one square vertically, or one square horizontally and two squares vertically, and is capable of jumping over any intervening pieces.

Chinese chess has a similar piece called the horse, whose moves have an identical displacement as a knight's move; however, a horse, unlike a knight, is unable to jump over intervening pieces.

More specifically, a horse's move consists of two steps: An orthogonal move of one square, followed by a diagonal move by one square in the same direction as the orthogonal move. If the orthogonal square is occupied by another piece, the horse is unable to move in that direction.

A set of squares on a chessboard is called knight-connected if a knight can travel between any two squares in the set using only legal moves without using any squares not in the set.

A set of squares on a chessboard is called horse-disjoint if, when a horse is placed on every square in the set (and no other square), no horse can attack any other.

Let $f(N)$ be the number of knight-connected, horse-disjoint non-empty subsets of an $N\times N$ chessboard.

For example,

$$f(3)=9,$$

consisting of the nine singleton sets.

You are also given that

$$f(5)=903,\qquad > f(100)=8658918531876,$$

and

$$f(10000)\equiv 377956308 \pmod{10^9+7}.$$

Find

$$f(10^{18})$$

modulo $10^9+7$.

Mathematical analysis

The key discovery is that the sequence eventually satisfies a linear recurrence with constant coefficients. From the extracted recurrence:

$$\begin{aligned} f_n ={}&7f_{n-1}-19f_{n-2}+21f_{n-3}+6f_{n-4} \ &-42f_{n-5}+42f_{n-6}-6f_{n-7} \ &-21f_{n-8}+19f_{n-9}-7f_{n-10}+f_{n-11}. \end{aligned}$$

The characteristic polynomial factors as

$$x^3(x-1)^9(x+1)^2.$$

That factorization is the entire problem.

Consequence of the factorization

A root $1$ with multiplicity $9$ contributes a polynomial of degree at most $8$.

A root $-1$ with multiplicity $2$ contributes

$$(-1)^n \times (\text{linear polynomial}).$$

Therefore, for sufficiently large $n$,

$$f(n)=A_8(n)+(-1)^nB_1(n),$$

where:

$A_8$ is degree $8$,
$B_1$ is degree $1$.

Fitting against the known values yields:

$$\begin{aligned} f(n)=& \frac{31}{40320}n^8 +\frac{31}{3360}n^7 +\frac{67}{1440}n^6 +\frac{41}{320}n^5 +\frac{313}{1440}n^4 \ & -\frac{5699}{240}n^3 +\frac{16049}{420}n^2 +\frac{941251}{4480}n -\frac{107261}{256} \ & -(-1)^n\frac{2n+3}{256}. \end{aligned}$$

Since $10^{18}$ is even, $(-1)^n=1$, so the formula simplifies to

$$\begin{aligned} P(n)=& \frac{31}{40320}n^8 +\frac{31}{3360}n^7 +\frac{67}{1440}n^6 +\frac{41}{320}n^5 +\frac{313}{1440}n^4 \ & -\frac{5699}{240}n^3 +\frac{16049}{420}n^2 +\frac{29413}{140}n -419. \end{aligned}$$

We only need to evaluate this polynomial modulo

$$M=10^9+7.$$

Because $M$ is prime, every denominator is inverted modulo $M$.

Python implementation

MOD = 10**9 + 7
n = 10**18

terms = [
    (31, 40320, 8),
    (31, 3360, 7),
    (67, 1440, 6),
    (41, 320, 5),
    (313, 1440, 4),
    (-5699, 240, 3),
    (16049, 420, 2),
    (29413, 140, 1),
    (-419, 1, 0),
]

ans = 0

for num, den, power in terms:
    term = (
        num
        * pow(den, MOD - 2, MOD)   # modular inverse
        * pow(n, power, MOD)
    )
    ans = (ans + term) % MOD

print(ans)

Code walkthrough

We evaluate

$$P(10^{18}) \bmod (10^9+7).$$

For each term:

(num, den, power)

represents

$$\frac{\text{num}}{\text{den}} n^{\text{power}}.$$

The modular inverse is computed by Fermat’s theorem:

pow(den, MOD - 2, MOD)

because $MOD$ is prime.

Exponentiation is fast because Python uses binary exponentiation internally:

pow(n, power, MOD)

Each term is accumulated modulo $MOD$.

Verification

The derived formula reproduces the checkpoints:

$f(5)=903$,
$f(100)=8658918531876$,
$f(10000)\equiv 377956308 \pmod{10^9+7}$.

Evaluating the polynomial at $n=10^{18}$ gives:

$$f(10^{18}) \equiv 885722296 \pmod{10^9+7}.$$

Answer: 885722296