Project Euler Problem 702

Solution

Answer: 622305608172525546

A key observation is that after $k$ jumps, the flea’s position is always a dyadic convex combination of the six vertices.

The geometry of the reachable regions induces a recursive binary partition of the hexagon, and the problem can be reduced to counting inversions in certain modular-multiplication permutations.

A fast solution uses the following derived formula (valid here because $123456789$ is odd):

$$S(N) = \frac{N(3N+1)}{2}(D+1) - \sum_{d=2}^{D} g(N,2^d) + 2g(N,2^D-N),$$

where

$$D=\lfloor \log_2 N \rfloor+1,$$

and $g(x,m)$ is computed from a recursive inversion-counting function based on the Euclidean algorithm.

The following Python program evaluates the answer efficiently:

def _inv_count_mod_mult(x, m, memo):
    # Number of inversions in:
    # a*x mod m for a = 1..m-1
    if m <= 2:
        return 0

    x %= m

    if x == 1:
        return 0

    if x == m - 1:
        return (m - 1) * (m - 2) // 2

    key = (x, m)
    if key in memo:
        return memo[key]

    t = m // x
    y = m - t * x

    block = (t * (t + 1) // 2) * (x * (x - 1) // 2)

    res = (
        block
        + (t + 1) * _inv_count_mod_mult(x, y, memo)
        - t * _inv_count_mod_mult(x, x - y, memo)
    )

    memo[key] = res
    return res

def _g(x, m, memo):
    if m <= 2:
        return 0
    return (m - 1) * (m - 2) - _inv_count_mod_mult(x, m, memo)

def S(N):
    memo = {}

    D = N.bit_length()

    total = (N * (3 * N + 1) // 2) * (D + 1)

    for d in range(2, D + 1):
        total -= _g(N, 1 << d, memo)

    total += 2 * _g(N, (1 << D) - N, memo)

    return total

# Verification against the problem statement
assert S(3) == 42
assert S(5) == 126
assert S(123) == 167178
assert S(12345) == 3185041956

print(S(123456789))

The verification values exactly match the examples given in the problem statement, confirming the implementation.

Therefore,

Answer: 622305608172525546