Problem 669: The King's Banquet

Project Euler Problem 669 Solution

EulerSolve provides an optimized solution for Project Euler Problem 669, The King's Banquet, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Let $F_1=F_2=1$ and $F_{j+2}=F_{j+1}+F_j$. On the vertex set $\{1,2,\dots,n\}$, we join $u$ and $v$ exactly when $u+v$ is a Fibonacci number. The problem asks for the label at a specified place in a Hamiltonian path when $n=F_{83}$. The crucial point is that for Fibonacci-sized graphs $n=F_k$, the path used by the implementations is not found by search; it is given by a closed arithmetic rule. Mathematical Approach For graphs of size $F_k$, the path can be described with modular arithmetic. The reason this works is that consecutive Fibonacci numbers are coprime, so stepping by $F_{k-1}$ permutes the residue classes modulo $F_k$. Step 1: Model the Banquet as a Fibonacci-Sum Graph Define $$G_k=(\{1,2,\dots,F_k\},E),\qquad \{u,v\}\in E \iff u+v\in\{F_j:j\ge 1\}.$$ A Hamiltonian path is an ordering $a_1,a_2,\dots,a_{F_k}$ that uses every vertex exactly once and satisfies $$a_i+a_{i+1}\in\{F_j:j\ge 1\},\qquad 1\le i \lt F_k.$$ Because the graph is undirected, reversing such an ordering still gives a valid Hamiltonian path. The implementations therefore describe the path from the right end first and convert the requested left-side position only at the end....

Detailed mathematical approach

Problem Summary

Let $F_1=F_2=1$ and $F_{j+2}=F_{j+1}+F_j$. On the vertex set $\{1,2,\dots,n\}$, we join $u$ and $v$ exactly when $u+v$ is a Fibonacci number. The problem asks for the label at a specified place in a Hamiltonian path when $n=F_{83}$. The crucial point is that for Fibonacci-sized graphs $n=F_k$, the path used by the implementations is not found by search; it is given by a closed arithmetic rule.

Mathematical Approach

For graphs of size $F_k$, the path can be described with modular arithmetic. The reason this works is that consecutive Fibonacci numbers are coprime, so stepping by $F_{k-1}$ permutes the residue classes modulo $F_k$.

Step 1: Model the Banquet as a Fibonacci-Sum Graph

Define

$$G_k=(\{1,2,\dots,F_k\},E),\qquad \{u,v\}\in E \iff u+v\in\{F_j:j\ge 1\}.$$

A Hamiltonian path is an ordering $a_1,a_2,\dots,a_{F_k}$ that uses every vertex exactly once and satisfies

$$a_i+a_{i+1}\in\{F_j:j\ge 1\},\qquad 1\le i \lt F_k.$$

Because the graph is undirected, reversing such an ordering still gives a valid Hamiltonian path. The implementations therefore describe the path from the right end first and convert the requested left-side position only at the end.

Step 2: Write the Right-End Order as a Modular Walk

For $m\ge 1$, let $\rho_m$ be the unique integer with

$$\rho_m \equiv mF_{k-1}\pmod{F_k},\qquad 1\le \rho_m \lt F_k.$$

Then the right-to-left order is

$$a_1=F_k,\qquad a_{2m}=\rho_m,\qquad a_{2m+1}=F_k-\rho_m,$$

for every $m$ for which the index exists. If $F_k$ is even, the path simply ends with its final even term; for the target case $F_{83}$ is odd, so all nonterminal terms after $a_1$ come in even-odd pairs.

This is equivalent to the compact position formula used in the implementations. If $r$ is the position counted from the right and $m=\lfloor r/2\rfloor$, compute

$$t \equiv mF_{k-1}\pmod{F_k},\qquad 0\le t \lt F_k,$$

and interpret residue $0$ as the vertex $F_k$. Then

$$v(r)=\begin{cases} F_k, & r=1,\\ t, & r\equiv 0 \pmod{2},\\ (F_k-t)\bmod F_k, & r\equiv 1 \pmod{2}. \end{cases}$$

Step 3: Prove That Consecutive Vertices Are Adjacent

There are three kinds of neighboring pairs in the right-end description.

The opening edge is valid because

$$a_1+a_2=F_k+\rho_1=F_k+F_{k-1}=F_{k+1}.$$

Each even-odd pair is valid because

$$a_{2m}+a_{2m+1}=\rho_m+(F_k-\rho_m)=F_k.$$

Finally, between one pair and the next, we use

$$\rho_{m+1}\equiv \rho_m+F_{k-1}\pmod{F_k}.$$

So $\rho_{m+1}$ is either $\rho_m+F_{k-1}$ or $\rho_m+F_{k-1}-F_k$, which gives

$$a_{2m+1}+a_{2m+2}=(F_k-\rho_m)+\rho_{m+1}\in\{F_{k+1},F_{k-1}\}.$$

All three possible sums, $F_{k-1}$, $F_k$, and $F_{k+1}$, are Fibonacci numbers. Hence every consecutive pair in the constructed order is an edge of the graph.

Step 4: Prove That Every Vertex Appears Exactly Once

Since consecutive Fibonacci numbers are coprime,

$$\gcd(F_{k-1},F_k)=1.$$

Therefore multiplication by $F_{k-1}$ permutes the nonzero residue classes modulo $F_k$, so the values $\rho_m$ are all distinct.

The complementary values $F_k-\rho_m$ are also distinct. A collision between the two families would require

$$\rho_m=F_k-\rho_j,$$

which implies

$$(m+j)F_{k-1}\equiv 0\pmod{F_k}.$$

Because $F_{k-1}$ is invertible modulo $F_k$, this forces $m+j\equiv 0\pmod{F_k}$. But in the relevant range we have $1\le m+j \lt F_k$, so this cannot happen. Thus the construction uses each label exactly once and is a Hamiltonian path.

Step 5: Convert the Requested Position

The problem gives a position counted from the left, while the closed form is easiest from the right. If the path length is $F_k$ and the requested left position is $L$, then the corresponding right position is

$$r=F_k-L+1.$$

Since reversing the path preserves adjacency, evaluating $v(r)$ gives the required knight directly.

Worked Example: $n=13=F_7$

Here $F_{k-1}=8$. The modular residues are

$$\rho_m \equiv 8m\pmod{13}\qquad(m=1,\dots,6),$$

namely

$$8,\ 3,\ 11,\ 6,\ 1,\ 9.$$

So the right-end order is

$$13,\ 8,\ 5,\ 3,\ 10,\ 11,\ 2,\ 6,\ 7,\ 1,\ 12,\ 9,\ 4.$$

Reversing it gives the left-to-right order

$$4,\ 9,\ 12,\ 1,\ 7,\ 6,\ 2,\ 11,\ 10,\ 3,\ 5,\ 8,\ 13.$$

The consecutive sums are

$$13,\ 21,\ 13,\ 8,\ 13,\ 8,\ 13,\ 21,\ 13,\ 8,\ 13,\ 21,$$

all Fibonacci numbers, so the construction is visible on a small instance.

How the Code Works

The C++, Python, and Java implementations all follow the same arithmetic plan. They precompute Fibonacci numbers up to the required index, set $n=F_{83}$, convert the requested left position $10^{16}$ to the right-side index $r=n-10^{16}+1$, and then evaluate the modular formula above.

For the target instance they use

$$F_{82}=61305790721611591,\qquad F_{83}=99194853094755497,\qquad r=89194853094755498.$$

One modular multiplication by $F_{82}$, followed by a parity test and possibly a complement with respect to $F_{83}$, produces the final label

$$56342087360542122.$$

The C++ implementation also includes small sanity checks: it finds a Hamiltonian path by brute force on a tiny graph, and for the Fibonacci-sized test case $n=34$ it compares the entire closed form against a brute-force path. The Java implementation protects the modular product with arbitrary-precision arithmetic, Python relies on native big integers, and C++ uses a wider integer intermediate.

Complexity Analysis

If the target size is $F_k$, generating Fibonacci numbers up to index $k$ costs $O(k)$ time and $O(k)$ memory. After that one-time setup, answering the question needs only a subtraction, an integer division by $2$, one modular multiplication, and a parity-dependent branch, so the main computation runs in $O(1)$ time with $O(1)$ extra working memory. The brute-force search used for validation is confined to very small checkpoints and is not part of the large-instance algorithm.

Footnotes and References

Problem page: https://projecteuler.net/problem=669
Hamiltonian path: Wikipedia — Hamiltonian path
Fibonacci number: Wikipedia — Fibonacci number
Modular arithmetic: Wikipedia — Modular arithmetic
Coprime integers: Wikipedia — Coprime integers

Problem 669 source code

C++

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <vector>

namespace {

using u64 = std::uint64_t;
using u128 = __uint128_t;

std::vector<int> fibonacci_up_to(int limit) {
    std::vector<int> fib{1, 2};
    while (fib.back() < limit) {
        fib.push_back(fib[fib.size() - 1] + fib[fib.size() - 2]);
    }
    return fib;
}

std::vector<int> brute_path(int n) {
    const std::vector<int> fib = fibonacci_up_to(2 * n + 5);
    std::vector<char> is_fib(static_cast<std::size_t>(2 * n + 6), 0);
    for (int x : fib) {
        if (x < static_cast<int>(is_fib.size())) {
            is_fib[static_cast<std::size_t>(x)] = 1;
        }
    }

    std::vector<std::vector<int>> adj(static_cast<std::size_t>(n + 1));
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            if (is_fib[static_cast<std::size_t>(i + j)] != 0) {
                adj[static_cast<std::size_t>(i)].push_back(j);
                adj[static_cast<std::size_t>(j)].push_back(i);
            }
        }
    }

    std::vector<int> degree(static_cast<std::size_t>(n + 1), 0);
    for (int i = 1; i <= n; ++i) {
        degree[static_cast<std::size_t>(i)] =
            static_cast<int>(adj[static_cast<std::size_t>(i)].size());
    }

    for (int i = 1; i <= n; ++i) {
        auto& v = adj[static_cast<std::size_t>(i)];
        std::sort(v.begin(), v.end(), [&](int a, int b) {
            if (degree[static_cast<std::size_t>(a)] != degree[static_cast<std::size_t>(b)]) {
                return degree[static_cast<std::size_t>(a)] < degree[static_cast<std::size_t>(b)];
            }
            return a < b;
        });
    }

    std::vector<int> starts;
    for (int i = 1; i <= n; ++i) starts.push_back(i);
    std::sort(starts.begin(), starts.end(), [&](int a, int b) {
        if (degree[static_cast<std::size_t>(a)] != degree[static_cast<std::size_t>(b)]) {
            return degree[static_cast<std::size_t>(a)] < degree[static_cast<std::size_t>(b)];
        }
        return a < b;
    });

    std::vector<char> used(static_cast<std::size_t>(n + 1), 0);
    std::vector<int> path;
    path.reserve(static_cast<std::size_t>(n));

    auto dfs = [&](auto&& self, int v) -> bool {
        if (static_cast<int>(path.size()) == n) {
            return true;
        }
        std::vector<int> cand;
        for (int u : adj[static_cast<std::size_t>(v)]) {
            if (used[static_cast<std::size_t>(u)] == 0) {
                cand.push_back(u);
            }
        }
        std::sort(cand.begin(), cand.end(), [&](int a, int b) {
            int ra = 0;
            int rb = 0;
            for (int x : adj[static_cast<std::size_t>(a)]) {
                if (used[static_cast<std::size_t>(x)] == 0) ++ra;
            }
            for (int x : adj[static_cast<std::size_t>(b)]) {
                if (used[static_cast<std::size_t>(x)] == 0) ++rb;
            }
            if (ra != rb) return ra < rb;
            return a < b;
        });

        for (int u : cand) {
            used[static_cast<std::size_t>(u)] = 1;
            path.push_back(u);
            if (self(self, u)) {
                return true;
            }
            path.pop_back();
            used[static_cast<std::size_t>(u)] = 0;
        }
        return false;
    };

    for (int st : starts) {
        std::fill(used.begin(), used.end(), 0);
        path.clear();
        used[static_cast<std::size_t>(st)] = 1;
        path.push_back(st);
        if (dfs(dfs, st)) {
            if (path.front() > path.back()) {
                std::reverse(path.begin(), path.end());
            }
            return path;
        }
    }

    return {};
}

u64 knight_from_right(u64 right_pos, u64 fk, u64 fk_minus_1) {
    if (right_pos == 1ULL) {
        return fk;
    }
    const u64 m = right_pos / 2ULL;
    const u64 t = static_cast<u64>((static_cast<u128>(m) * static_cast<u128>(fk_minus_1)) % fk);
    u64 v = 0;
    if ((right_pos & 1ULL) == 0ULL) {
        v = t;
    } else {
        v = (fk - t) % fk;
    }
    if (v == 0ULL) {
        v = fk;
    }
    return v;
}

}  // namespace

int main() {
    {
        const std::vector<int> p7 = brute_path(7);
        assert(!p7.empty());
        assert(p7[2] == 7);
    }

    {
        const std::vector<int> p34 = brute_path(34);
        assert(!p34.empty());
        assert(p34[2] == 30);
        for (u64 left = 1; left <= 34; ++left) {
            const u64 right = 34ULL - left + 1ULL;
            const u64 got = knight_from_right(right, 34ULL, 21ULL);
            assert(got == static_cast<u64>(p34[static_cast<std::size_t>(left - 1ULL)]));
        }
    }

    std::vector<u64> fib(85, 0ULL);
    fib[1] = 1ULL;
    fib[2] = 1ULL;
    for (int i = 3; i <= 84; ++i) {
        fib[static_cast<std::size_t>(i)] = fib[static_cast<std::size_t>(i - 1)] + fib[static_cast<std::size_t>(i - 2)];
    }

    const u64 n = fib[83];
    const u64 left_pos = 10'000'000'000'000'000ULL;
    const u64 right_pos = n - left_pos + 1ULL;

    const u64 ans = knight_from_right(right_pos, n, fib[82]);
    std::cout << ans << "\n";
    return 0;
}

Python

def knight_from_right(right_pos, fk, fk_minus_1):
    if right_pos == 1:
        return fk
    m = right_pos // 2
    t = (m * fk_minus_1) % fk
    if right_pos % 2 == 0:
        v = t
    else:
        v = (fk - t) % fk
    if v == 0:
        v = fk
    return v

def solve():
    fib = [0] * 85
    fib[1] = 1
    fib[2] = 1
    for i in range(3, 85):
        fib[i] = fib[i - 1] + fib[i - 2]
        
    n = fib[83]
    left_pos = 10000000000000000
    right_pos = n - left_pos + 1
    
    ans = knight_from_right(right_pos, n, fib[82])
    return str(ans)

if __name__ == '__main__':
    print(solve())

Java

import java.math.BigInteger;

public class Euler669 {

    static long knightFromRight(long rightPos, long fk, long fkMinus1) {
        if (rightPos == 1)
            return fk;

        long m = rightPos / 2;

        BigInteger bm = BigInteger.valueOf(m);
        BigInteger bFkMinus1 = BigInteger.valueOf(fkMinus1);
        BigInteger bFk = BigInteger.valueOf(fk);

        long t = bm.multiply(bFkMinus1).remainder(bFk).longValue();

        long v;
        if (rightPos % 2 == 0) {
            v = t;
        } else {
            v = (fk - t) % fk;
        }

        if (v == 0) {
            v = fk;
        }

        return v;
    }

    public static String solve() {
        long[] fib = new long[85];
        fib[1] = 1;
        fib[2] = 1;
        for (int i = 3; i < 85; ++i) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }

        long n = fib[83];
        long leftPos = 10000000000000000L;
        long rightPos = n - leftPos + 1;

        long ans = knightFromRight(rightPos, n, fib[82]);
        return Long.toString(ans);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}