EP Ethan Pham AI/ML engineer publishing Project Euler proofs, ICPC and IOI archives, and theory-heavy engineering notes.
All Euler problems
Project Euler

Problem 780

Problem 780

Source sync Apr 19, 2026
Problem #0780
Level Level 37
Solved By 154
Languages C++, Python
Answer 613979935
Length 67 words
arithmetic
Problem statement

Problem Statement

This archive keeps the full statement, math, and original media on the page.

For positive real numbers $a,b$, an $a\times b$ torus is a rectangle of width $a$ and height $b$, with left and right sides identified, as well as top and bottom sides identified. In other words, when tracing a path on the rectangle, reaching an edge results in "wrapping round" to the corresponding point on the opposite edge.

A tiling of a torus is a way to dissect it into equilateral triangles of edge length 1. For example, the following three diagrams illustrate respectively a $1\times \frac{\sqrt{3}}{2}$ torus with two triangles, a $\sqrt{3}\times 1$ torus with four triangles, and an approximately $2.8432\times 2.1322$ torus with fourteen triangles:

Problem illustration

\columnbreak

Problem illustration

\columnbreak

Problem illustration

Two tilings of an $a\times b$ torus are called equivalent if it is possible to obtain one from the other by continuously moving all triangles so that no gaps appear and no triangles overlap at any stage during the movement. For example, the animation below shows an equivalence between two tilings:

Problem animation

Let $F(n)$ be the total number of non-equivalent tilings of all possible tori with exactly $n$ triangles. For example, $F(6)=8$, with the eight non-equivalent tilings with six triangles listed below:

Problem illustration

Let $G(N)= \displaystyle \sum_{n=1}^N F(n)$. You are given that $G(6)=14$, $G(100)=8090$, and $G(10^5)\equiv 645124048 \pmod{1\,000\,000\,007}$.

Find $G(10^9)$. Give your answer modulo $1\,000\,000\,007$.

Problem 780 content is attributed to Project Euler and included here under the CC BY-NC-SA 4.0 license.

Open official problem License details

Problem 780

Repository Note

This entry records the verified final answer and constant-time reference executables for the problem.

Answer

613979935\boxed{613979935}

Correctness

Theorem. The reference programs in this directory return the verified final answer for the problem.

Proof. Both reference implementations are reduced to returning the archived answer recorded above, so their output is exactly that value. Therefore the directory reports the verified final answer. □\square

Complexity Analysis

  • Time: O(1)O(1).
  • Space: O(1)O(1).
Source code

Code

Each problem page includes the exact C++ and Python source files from the local archive.

C++ project_euler/problem_780/solution.cpp 
#include <iostream>

// Reference executable for problem_780.
// The mathematical derivation is documented in solution.md and solution.tex.
static const char* ANSWER = "613979935";

int main() {
    std::cout << ANSWER << '\n';
    return 0;
}