Solution

Answer: 697003956

Let

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

For a subset $A\subseteq U_n={s_1,\dots,s_n}$, sorted increasingly, the polygon condition is exactly

$$\max(A)<\sum_{x\in A\setminus{\max(A)}}x.$$

Since all $s_i$ are distinct and increasing, every subset has a unique largest element.

1. Mathematical analysis

Define:

$$g(n)=#{\text{subsets of }U_{n-1}\text{ with sum }\le s_n}.$$

If a subset of $U_n$ has largest element $s_n$, then it generates a polygon iff the remaining chosen elements have sum $>s_n$.

There are $2^{n-1}$ subsets whose largest element is $s_n$, hence

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

So the problem reduces to computing $g(k)$.

Computing the first values

The sequence begins

$$1,2,3,4,6,9,13,19,28,41,\dots$$

and the resulting polygon counts are

$$\begin{aligned} f(1)&=0\ f(2)&=0\ f(3)&=0\ f(4)&=2\ f(5)&=7\ f(6)&=19\ f(7)&=47\ f(8)&=108\ f(9)&=236\ f(10)&=501. \end{aligned}$$

matching the statement.

Key structural fact

Because $s_n=s_{n-1}+s_{n-3}$, the counting sequence $f(n)$ is ultimately linear-recursive (a standard consequence for subset-counting problems over C-finite sequences).

Using the first several exact values and Berlekamp–Massey gives the minimal recurrence:

$$\boxed{ f(n)= 4f(n-1)-5f(n-2)+4f(n-3)-7f(n-4)+6f(n-5) +2f(n-7)-5f(n-8)+2f(n-9) }$$

for $n\ge 10$.

The characteristic polynomial factors as

$$(x-2)(x-1)^2(x^3-x-1)(x^3+x-1).$$

So we can compute $f(10^{18})$ modulo $10^9$ using fast linear-recurrence exponentiation in $O(r^2\log n)$ with $r=9$.

2. Python implementation

MOD = 10**9

# Initial values f(1)..f(9)
init = [
    0,   # f(1)
    0,   # f(2)
    0,   # f(3)
    2,   # f(4)
    7,   # f(5)
    19,  # f(6)
    47,  # f(7)
    108, # f(8)
    236  # f(9)
]

# Recurrence:
# f(n) =
# 4f(n-1)-5f(n-2)+4f(n-3)-7f(n-4)+6f(n-5)
# +2f(n-7)-5f(n-8)+2f(n-9)

rec = [4, -5, 4, -7, 6, 0, 2, -5, 2]

def combine(a, b, rec):
    """
    Multiply two polynomials modulo the recurrence.
    """
    m = len(rec)
    tmp = [0] * (2 * m)

    for i in range(m):
        for j in range(m):
            tmp[i + j] = (tmp[i + j] + a[i] * b[j]) % MOD

    # Reduce using the recurrence
    for i in range(2 * m - 2, m - 1, -1):
        if tmp[i] == 0:
            continue
        for j in range(m):
            tmp[i - 1 - j] = (tmp[i - 1 - j] +
                              tmp[i] * rec[j]) % MOD

    return tmp[:m]

def linear_recurrence(n, init, rec):
    """
    Returns f(n) where indexing is:
        init[0] = f(1)
    """

    m = len(rec)

    if n <= m:
        return init[n - 1] % MOD

    # Binary exponentiation on the companion polynomial
    pol = [1] + [0] * (m - 1)
    e = [0, 1] + [0] * (m - 2)

    k = n - 1

    while k:
        if k & 1:
            pol = combine(pol, e, rec)
        e = combine(e, e, rec)
        k >>= 1

    ans = 0
    for i in range(m):
        ans = (ans + pol[i] * init[i]) % MOD

    return ans

N = 10**18
print(linear_recurrence(N, init, rec))

3. Code walkthrough

Initial values

The first 9 values are computed directly from the polygon condition:

$$0,0,0,2,7,19,47,108,236.$$

These seed the recurrence.

The recurrence coefficients

rec = [4, -5, 4, -7, 6, 0, 2, -5, 2]

represent

$$f(n)=\sum_{i=1}^{9} rec[i-1]\cdot f(n-i).$$

`combine`

This multiplies two polynomials and reduces modulo the recurrence relation, exactly like fast exponentiation modulo a characteristic polynomial.

`linear_recurrence`

Uses binary exponentiation to compute the $n$-th term in logarithmic time.

Complexity:

$$O(r^2\log n)$$

with $r=9$, so even $10^{18}$ is trivial.

4. Verification

The recurrence reproduces:

$f(5)=7$
$f(10)=501$
$f(25)=18635853$

exactly as required.

The computation modulo $10^9$ gives:

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

Answer: 697003956

Project Euler Problem 382