Detailed mathematical approach

Problem Summary

The side lengths are generated by

$s_1=1,\quad s_2=2,\quad s_3=3,\quad s_n=s_{n-1}+s_{n-3}\quad (n\ge 4).$

Because \(s_{n-3}\gt 0\), the sequence is strictly increasing, so every subset of \(\{s_1,\dots,s_n\}\) has a unique largest selected side. Let \(f(n)\) be the number of nonempty subsets that can be arranged into a nondegenerate polygon. The solver computes \(f(10^{18}) \bmod 10^9\).

Mathematical Approach

Step 1: Reduce Polygon Feasibility to One Inequality

For any finite set of positive side lengths, a polygon exists if and only if the largest side is smaller than the sum of all remaining sides. If a subset has largest side \(s_n\), then it is bad exactly when the other chosen sides have total length at most \(s_n\).

This immediately turns the geometric problem into a counting problem about subset sums.

Step 2: Count Bad Subsets by Their Largest Index

Define \(b_n\) as the number of subsets of \(\{s_1,\dots,s_{n-1}\}\) whose sum is at most \(s_n\):

$b_n=\#\left\{A\subseteq \{1,\dots,n-1\}:\sum_{i\in A}s_i\le s_n\right\}.$

Every non-polygon subset of \(\{s_1,\dots,s_n\}\) has a unique largest element \(s_k\), and after removing that largest side the remaining subset contributes to \(b_k\). Therefore the bad subsets are counted exactly once by \(\sum_{k=1}^{n} b_k\), and

$\boxed{f(n)=\left(2^n-1\right)-\sum_{k=1}^{n} b_k.}$

This identity is the core formula used by all three implementations.

Step 3: Exact Subset-Sum Counting for the Initial Terms

The C++ reference solution builds the first values of \(b_n\) with an exact memoized counter. Let

$P_i=\sum_{k=1}^{i}s_k,\qquad C(i,L)=\#\left\{A\subseteq \{1,\dots,i\}:\sum_{k\in A}s_k\le L\right\}.$

The recursion implemented in ExactCounter is

$ C(i,L)= \begin{cases} 1, & i=0,\\ 2^i, & L\ge P_i,\\ C(i-1,L), & s_i\gt L,\\ C(i-1,L)+C(i-1,L-s_i), & s_i\le L. \end{cases} $

Then \(b_n=C(n-1,s_n)\). The exact values produced by the local code are

$ (b_1,b_2,b_3,b_4,b_5,b_6,b_7,b_8)=(1,2,4,6,11,20,36,67). $

These eight terms form the base state for the fast solver.

Step 4: Use the Verified Order-8 Recurrence

From the exact sequence one obtains the linear recurrence embedded in all three source files:

$ b_n=3b_{n-1}-2b_{n-2}+2b_{n-3}-5b_{n-4}+b_{n-5}+b_{n-6}+3b_{n-7}-2b_{n-8}, \qquad n\ge 9. $

The C++ program does not merely assume this relation: it recomputes \(b_n\) exactly up to \(n=60\) and checks that the recurrence matches every term from \(n=9\) onward. That validation step is the reason the mathematical description should treat this recurrence as a verified fact coming from the local solution, not as an unsupported guess.

Step 5: Augment the State with the Prefix Sum

We need \(B_n=\sum_{k=1}^{n} b_k\), not just \(b_n\). So the solver stores the 9-component state

$ v_n= \begin{bmatrix} b_n\\ b_{n-1}\\ b_{n-2}\\ b_{n-3}\\ b_{n-4}\\ b_{n-5}\\ b_{n-6}\\ b_{n-7}\\ B_n \end{bmatrix}. $

With the recurrence coefficients in the first row, simple shifts in rows \(2\) through \(8\), and one extra cumulative row, we get

$v_{n+1}=Tv_n,$

where

$ T= \begin{bmatrix} 3 & -2 & 2 & -5 & 1 & 1 & 3 & -2 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 3 & -2 & 2 & -5 & 1 & 1 & 3 & -2 & 1 \end{bmatrix}. $

The starting vector is

$ v_8= \begin{bmatrix} 67\\ 36\\ 20\\ 11\\ 6\\ 4\\ 2\\ 1\\ 147 \end{bmatrix}, \qquad 147=1+2+4+6+11+20+36+67. $

For \(n\gt 8\), binary exponentiation gives \(v_n=T^{\,n-8}v_8\) modulo \(10^9\). The last component is \(B_n\).

Step 6: Final Formula and Checkpoints

Once \(B_n\) is known, the answer is

$\boxed{f(n)\equiv 2^n-1-B_n \pmod{10^9}.}$

A small example shows the decomposition clearly. For \(n=5\), the sequence is \((1,2,3,4,6)\), the exact counter gives

$ (b_1,b_2,b_3,b_4,b_5)=(1,2,4,6,11), $

and therefore

$ f(5)=2^5-1-(1+2+4+6+11)=31-24=7. $

The C++ validation also checks the Project Euler checkpoints

$f(10)=501,\qquad f(25)=18635853.$

Running the local solver for the target input yields

$f(10^{18}) \equiv 697003956 \pmod{10^9}.$

How the Code Works

The C++ file contains both the exact validator and the fast solver. ExactCounter computes \(b_n\) by memoized subset-sum counting and confirms the recurrence on \(n\le 60\). The function prefix_sum_b_mod handles the eight base terms directly, then switches to 9 by 9 matrix exponentiation. Negative recurrence coefficients are normalized modulo \(10^9\) before being inserted into the transition matrix. Finally, solve_mod computes \(2^n \bmod 10^9\), subtracts \(1\) and the prefix sum \(B_n\), and normalizes the result.

The Python and Java files are compact translations of the same fast path: identical base values, identical recurrence coefficients, the same 9-state transition, and the same final congruence.

Complexity Analysis

The exact subset-sum validator is used only on small \(n\), so it does not affect the asymptotic cost of the real computation. The production path performs binary exponentiation on a fixed \(9\times 9\) matrix, giving \(O(9^3\log n)\) time with dense multiplication and \(O(9^2)\) memory. Since \(9\) is constant, this is effectively \(O(\log n)\) time and constant auxiliary space.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=382
2. Polygon existence criterion: Wikipedia — Polygon
3. Matrix exponentiation for linear recurrences: cp-algorithms — Fibonacci Numbers
4. Local reference implementation with exact validation and checkpoints: solutionsCpp/Euler382.cpp
5. Compact fast-path implementations: solutionsPython/Euler382.py and solutionsJava/Euler382.java