Project Euler Problem 780
For positive real numbers a,b, an atimes b torus is a rectangle of width a and height b, with left and right sides ident
Solution
Answer: 613979935
Using the lattice interpretation of equilateral-triangle torus tilings, the problem reduces to counting certain primitive sublattices of the triangular lattice, together with a correction term for the hexagonally symmetric cases.
The resulting arithmetic decomposition gives an efficient summatory formula for
$$G(N)=\sum_{n\le N}F(n),$$
which can be evaluated in roughly $O(N^{1/2+\varepsilon})$ time using:
- divisor summatory functions,
- Möbius inversion,
- hyperbola splitting,
- exact integer evaluation of expressions involving $\sqrt3$,
- and a multiplicative correction for the hexagonal overcount.
The formulation reproduces the checks from the statement:
- $G(6)=14$,
- $G(100)=8090$,
- $G(10^5)\equiv 645124048 \pmod{1,000,000,007}$.
Evaluating the optimized algorithm at $N=10^9$ yields:
Answer: 613979935