Problem 473: Phigital Number Base

Project Euler Problem 473 Solution

EulerSolve provides an optimized solution for Project Euler Problem 473, Phigital Number Base, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Let $\phi=\dfrac{1+\sqrt5}{2}$. The problem asks for the sum of all positive integers at most $L$ whose canonical base-$\phi$ representation is palindromic around the radix point. The implementation uses the standard phinary digit rules: every digit is $0$ or $1$, and no two adjacent digits may both be $1$. If the left half of the palindrome is $d_{n-1}\dots d_1d_0$, then the full representation is $d_{n-1}\dots d_1d_0.d_0d_1\dots d_{n-1}$ in base $\phi$. The highest digit must be $1$, and the central pair forces $d_0=0$, because the two digits adjacent to the radix point are equal and therefore cannot both be $1$. The actual limit is $L=10^{10}$. A built-in checkpoint is $$\sum_{\substack{x\le 1000\\ x\text{ phigital}}} x = 4345,$$ which the C++, Python, and Java implementations all use as a sanity check. Mathematical Approach The key observation is that a palindromic base-$\phi$ string can be rewritten as a sum of paired powers $\phi^i+\phi^{-i-1}$. That converts the problem from digit strings into a meet-in-the-middle search over integer linear combinations....

Detailed mathematical approach

Problem Summary

Let $\phi=\dfrac{1+\sqrt5}{2}$. The problem asks for the sum of all positive integers at most $L$ whose canonical base-$\phi$ representation is palindromic around the radix point. The implementation uses the standard phinary digit rules: every digit is $0$ or $1$, and no two adjacent digits may both be $1$.

If the left half of the palindrome is $d_{n-1}\dots d_1d_0$, then the full representation is $d_{n-1}\dots d_1d_0.d_0d_1\dots d_{n-1}$ in base $\phi$. The highest digit must be $1$, and the central pair forces $d_0=0$, because the two digits adjacent to the radix point are equal and therefore cannot both be $1$.

The actual limit is $L=10^{10}$. A built-in checkpoint is

$$\sum_{\substack{x\le 1000\\ x\text{ phigital}}} x = 4345,$$

which the C++, Python, and Java implementations all use as a sanity check.

Mathematical Approach

The key observation is that a palindromic base-$\phi$ string can be rewritten as a sum of paired powers $\phi^i+\phi^{-i-1}$. That converts the problem from digit strings into a meet-in-the-middle search over integer linear combinations.

Step 1: Encode the Palindrome with Paired Weights

For digits $d_i\in\{0,1\}$, define

$$w_i=\phi^i+\phi^{-i-1}.$$

Then every palindromic representation described above has value

$$x=\sum_{i=0}^{n-1} d_i w_i.$$

The admissibility conditions become purely combinatorial:

$$d_{n-1}=1,\qquad d_0=0,\qquad d_i d_{i+1}=0 \text{ for } 0\le i\lt n-1.$$

So the search space is not all binary strings, but exactly the legal no-adjacent-ones strings with fixed boundary digits.

Step 2: Rewrite Each Weight in the Basis $\{1,\phi\}$

Let $F_0=0$, $F_1=1$. For $k\ge 1$,

$$\phi^k = F_k\phi + F_{k-1}.$$

For negative powers,

$$\phi^{-m}=(-1)^m\left(F_{m+1}-F_m\phi\right).$$

Therefore every paired weight can be written as

$$w_i=u_i+v_i\phi,$$

with integer coefficients $u_i,v_i$ that can be precomputed once. The first few values are

$$w_0=\phi,\qquad w_1=2,\qquad w_2=3\phi-2,\qquad w_3=6-\phi,\qquad w_4=8\phi-5.$$

This is exactly why the implementation stores, for each digit position, one coefficient for the rational part and one coefficient for the $\phi$-part.

Step 3: An Integer Appears Exactly When the $\phi$-Part Cancels

Summing the chosen weights gives

$$x=\sum_{i=0}^{n-1} d_i(u_i+v_i\phi)=U+V\phi,$$

where

$$U=\sum_{i=0}^{n-1} d_i u_i,\qquad V=\sum_{i=0}^{n-1} d_i v_i.$$

Because $1$ and $\phi$ are linearly independent over $\mathbb{Q}$, the value $x$ is an integer if and only if

$$V=0.$$

When that happens, the actual integer is simply

$$x=U.$$

So the problem is reduced to finding all legal digit strings for which the irrational coefficient vanishes and the remaining integer coefficient satisfies

$$1\le U\le L.$$

Step 4: Split the Digit Positions into Two Independent Halves

For a fixed length $n$, split the positions at a midpoint. The lower half contributes a pair $(U_{\ell},V_{\ell})$ and remembers its last digit near the split. The upper half contributes $(U_h,V_h)$ and remembers its first digit near the split.

A merge is valid exactly when three conditions hold:

$$V_{\ell}+V_h=0,$$

$$1\le U_{\ell}+U_h\le L,$$

and the two boundary digits are not both $1$.

This turns a global search into two smaller enumerations plus a structured merge step.

Step 5: Use Sorted Buckets to Sum All Compatible Merges Quickly

All upper-half states are grouped by their value of $V_h$ and by their first boundary digit. Inside each group, the $U_h$ values are sorted and equipped with prefix sums.

For one fixed lower-half state, only groups with

$$V_h=-V_{\ell}$$

can possibly cancel the $\phi$-part. The range condition becomes

$$1-U_{\ell}\le U_h\le L-U_{\ell}.$$

Two binary searches locate the admissible interval in the sorted list. If that interval contains $c$ states and their $U_h$-sum is $S$, then the total contribution of this lower-half state is

$$c\,U_{\ell}+S.$$

That formula accumulates the sum of all resulting integers without iterating over every matching pair one by one.

Worked Example

The legal palindrome

$$100100.001001_{\phi}$$

uses positions $5$ and $2$, so

$$x=w_5+w_2=(13-3\phi)+(3\phi-2)=11.$$

The $\phi$-terms cancel exactly, leaving the integer $11$. This is the basic phenomenon the algorithm searches for at scale. The special case $x=1$ is handled separately at the start, because it is a one-digit phigital number and does not belong to the paired-length loop.

How the Code Works

The implementation first precomputes Fibonacci numbers and, from them, the paired coefficients $(u_i,v_i)$ for all digit positions that can matter below the given limit. It then immediately initializes the answer with $1$, covering the standalone phigital number $1$.

For each candidate palindrome length, the implementation computes the minimum and maximum possible value of the integer coefficient $U$ under the digit rules. If that interval does not intersect $[1,L]$, the entire length can be skipped before any meet-in-the-middle work begins.

Otherwise it recursively enumerates all legal lower-half states and all legal upper-half states. Each state records its contribution to the rational coefficient, its contribution to the $\phi$-coefficient, and the boundary digit needed to enforce the no-adjacent-ones rule across the split.

The upper-half states are reorganized into lookup tables keyed by the $\phi$-coefficient and the boundary bit. Inside each table entry, the rational coefficients are sorted and accompanied by prefix sums. The lower-half enumeration then probes only the entries that can cancel the irrational part, performs two binary searches for the admissible interval, and adds the resulting block contribution to the total.

Complexity Analysis

For a length $n$, each half enumerates only legal binary strings with no adjacent ones, so the state count grows like a Fibonacci sequence. A convenient worst-case description is still

$$O\!\left(2^{n/2}\log 2^{n/2}\right),$$

because sorting and binary searching dominate after the split. In practice the no-adjacent-ones restriction makes the actual state count noticeably smaller than $2^{n/2}$.

The memory usage is linear in the number of stored upper-half states for the current length. Since only lengths up to a fixed safe cutoff are explored, the method is easily feasible for $L=10^{10}$, whereas a direct enumeration of all full digit strings would be hopeless.

Footnotes and References

Problem page: https://projecteuler.net/problem=473
Golden ratio: Wikipedia — Golden ratio
Fibonacci number: Wikipedia — Fibonacci number
Zeckendorf-style non-adjacent representations: Wikipedia — Zeckendorf's theorem
Meet-in-the-middle: Wikipedia — Meet-in-the-middle

Problem 473 source code

C++

#include <algorithm>
#include <array>
#include <cstdint>
#include <iostream>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
#include <functional>

namespace {

using i64 = std::int64_t;
using u64 = std::uint64_t;
using u128 = __uint128_t;

struct Options {
    i64 limit = 10'000'000'000LL;
    bool run_checkpoints = true;
};

struct LowState {
    i64 b = 0;
    i64 a = 0;
    std::uint8_t last = 0;
};

struct HighState {
    i64 b = 0;
    i64 a = 0;
    std::uint8_t first = 0;
};

struct Bucket {
    std::vector<i64> values;
    std::vector<i64> pref;  // pref[0]=0, pref[i+1]=sum values[0..i]
};

bool parse_i64_after_prefix(const std::string& arg, const std::string& prefix, i64& out) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    try {
        out = static_cast<i64>(std::stoll(tail));
    } catch (...) {
        return false;
    }
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_i64_after_prefix(arg, "--limit=", options.limit)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    if (options.limit <= 0) {
        std::cerr << "--limit must be positive.\n";
        return false;
    }
    return true;
}

std::array<i64, 100> build_fib() {
    std::array<i64, 100> f{};
    f[0] = 0;
    f[1] = 1;
    for (int i = 2; i < 100; ++i) {
        f[i] = f[i - 1] + f[i - 2];
    }
    return f;
}

void build_pair_coefficients(const std::array<i64, 100>& fib,
                             std::vector<i64>& coeff_a,
                             std::vector<i64>& coeff_b,
                             const int max_index) {
    coeff_a.assign(static_cast<std::size_t>(max_index + 1), 0);
    coeff_b.assign(static_cast<std::size_t>(max_index + 1), 0);

    for (int i = 0; i <= max_index; ++i) {
        i64 pos_a = 0;
        i64 pos_b = 0;
        if (i == 0) {
            pos_a = 1;
            pos_b = 0;
        } else {
            pos_a = fib[static_cast<std::size_t>(i - 1)];
            pos_b = fib[static_cast<std::size_t>(i)];
        }

        const int m = i + 1;
        const i64 sign = (m % 2 == 0) ? 1 : -1;  // (-1)^m
        const i64 neg_a = sign * fib[static_cast<std::size_t>(m + 1)];
        const i64 neg_b = -sign * fib[static_cast<std::size_t>(m)];

        coeff_a[static_cast<std::size_t>(i)] = pos_a + neg_a;
        coeff_b[static_cast<std::size_t>(i)] = pos_b + neg_b;
    }
}

std::pair<i64, i64> min_max_possible_a_for_length(const int n, const std::vector<i64>& coeff_a) {
    constexpr i64 kInf = (1LL << 62);
    std::vector<std::array<i64, 2>> min_dp(static_cast<std::size_t>(n + 1), {kInf, kInf});
    std::vector<std::array<i64, 2>> max_dp(static_cast<std::size_t>(n + 1), {-kInf, -kInf});
    min_dp[static_cast<std::size_t>(n)] = {0, 0};
    max_dp[static_cast<std::size_t>(n)] = {0, 0};

    for (int idx = n - 1; idx >= 0; --idx) {
        for (int prev = 0; prev <= 1; ++prev) {
            i64 best_min = kInf;
            i64 best_max = -kInf;

            auto relax = [&](const int bit) {
                if (prev == 1 && bit == 1) {
                    return;
                }
                const i64 add = (bit == 1) ? coeff_a[static_cast<std::size_t>(idx)] : 0;
                const i64 child_min = min_dp[static_cast<std::size_t>(idx + 1)][bit];
                const i64 child_max = max_dp[static_cast<std::size_t>(idx + 1)][bit];
                if (child_min >= kInf / 2 || child_max <= -kInf / 2) {
                    return;
                }
                best_min = std::min(best_min, add + child_min);
                best_max = std::max(best_max, add + child_max);
            };

            if (idx == 0) {
                relax(0);  // d_0 = 0 (otherwise d_0 and d_{-1} would be consecutive 1's in palindrome)
            } else if (idx == n - 1) {
                relax(1);  // highest digit must be 1 (no leading zero)
            } else {
                relax(0);
                relax(1);
            }

            min_dp[static_cast<std::size_t>(idx)][prev] = best_min;
            max_dp[static_cast<std::size_t>(idx)][prev] = best_max;
        }
    }

    return {min_dp[0][0], max_dp[0][0]};
}

void enumerate_low_states(const int end,
                          const std::vector<i64>& coeff_a,
                          const std::vector<i64>& coeff_b,
                          std::vector<LowState>& out) {
    out.clear();
    out.reserve(1U << 16);

    std::function<void(int, int, i64, i64, std::uint8_t)> dfs =
        [&](const int idx, const int prev, const i64 sum_b, const i64 sum_a, const std::uint8_t last) {
            if (idx > end) {
                out.push_back(LowState{sum_b, sum_a, last});
                return;
            }
            if (idx == 0) {
                dfs(1, 0, sum_b, sum_a, 0);
                return;
            }

            // bit = 0
            dfs(idx + 1, 0, sum_b, sum_a, 0);

            // bit = 1
            if (prev == 0) {
                dfs(idx + 1, 1, sum_b + coeff_b[static_cast<std::size_t>(idx)],
                    sum_a + coeff_a[static_cast<std::size_t>(idx)], 1);
            }
        };

    if (end < 0) {
        out.push_back(LowState{0, 0, 0});
        return;
    }
    dfs(0, 0, 0, 0, 0);
}

void enumerate_high_states(const int start,
                           const int end,
                           const std::vector<i64>& coeff_a,
                           const std::vector<i64>& coeff_b,
                           std::vector<HighState>& out) {
    out.clear();
    out.reserve(1U << 16);

    std::function<void(int, int, i64, i64, std::uint8_t)> dfs =
        [&](const int idx, const int prev, const i64 sum_b, const i64 sum_a, const std::uint8_t first) {
            if (idx > end) {
                out.push_back(HighState{sum_b, sum_a, first});
                return;
            }

            auto first_after = [&](const int bit) -> std::uint8_t {
                return (idx == start) ? static_cast<std::uint8_t>(bit) : first;
            };

            if (idx == end) {
                const int bit = 1;  // highest digit fixed to 1
                if (prev == 1) {
                    return;
                }
                dfs(idx + 1, 1, sum_b + coeff_b[static_cast<std::size_t>(idx)],
                    sum_a + coeff_a[static_cast<std::size_t>(idx)], first_after(1));
                return;
            }

            // bit = 0
            dfs(idx + 1, 0, sum_b, sum_a, first_after(0));

            // bit = 1
            if (prev == 0) {
                dfs(idx + 1, 1, sum_b + coeff_b[static_cast<std::size_t>(idx)],
                    sum_a + coeff_a[static_cast<std::size_t>(idx)], first_after(1));
            }
        };

    if (start > end) {
        out.push_back(HighState{0, 0, 0});
        return;
    }
    dfs(start, 0, 0, 0, 0);
}

u128 solve_sum(const i64 limit) {
    const int max_index = 64;
    const auto fib = build_fib();
    std::vector<i64> coeff_a;
    std::vector<i64> coeff_b;
    build_pair_coefficients(fib, coeff_a, coeff_b, max_index);

    u128 total = 1;  // representation "1"

    std::vector<LowState> low_states;
    std::vector<HighState> high_states;

    for (int n = 2; n <= 64; ++n) {
        const auto [min_a, max_a] = min_max_possible_a_for_length(n, coeff_a);
        if (max_a < 1 || min_a > limit) {
            continue;
        }

        const int mid = n / 2;
        enumerate_low_states(mid - 1, coeff_a, coeff_b, low_states);
        enumerate_high_states(mid, n - 1, coeff_a, coeff_b, high_states);

        std::array<std::unordered_map<i64, Bucket>, 2> high_maps;
        for (int fb = 0; fb <= 1; ++fb) {
            high_maps[fb].reserve(high_states.size() / 2U + 8U);
        }

        for (const HighState& st : high_states) {
            high_maps[st.first][st.b].values.push_back(st.a);
        }
        for (int fb = 0; fb <= 1; ++fb) {
            for (auto& kv : high_maps[fb]) {
                auto& vals = kv.second.values;
                std::sort(vals.begin(), vals.end());
                auto& pref = kv.second.pref;
                pref.assign(vals.size() + 1U, 0);
                for (std::size_t i = 0; i < vals.size(); ++i) {
                    pref[i + 1U] = pref[i] + vals[i];
                }
            }
        }

        for (const LowState& st : low_states) {
            for (int fb = 0; fb <= 1; ++fb) {
                if (st.last == 1U && fb == 1) {
                    continue;
                }
                const i64 target_b = -st.b;
                auto it = high_maps[fb].find(target_b);
                if (it == high_maps[fb].end()) {
                    continue;
                }

                const auto& vals = it->second.values;
                const auto& pref = it->second.pref;
                const i64 low_needed = 1 - st.a;
                const i64 high_needed = limit - st.a;

                const auto lo_it = std::lower_bound(vals.begin(), vals.end(), low_needed);
                const auto hi_it = std::upper_bound(vals.begin(), vals.end(), high_needed);
                if (lo_it == hi_it) {
                    continue;
                }

                const std::size_t lo = static_cast<std::size_t>(lo_it - vals.begin());
                const std::size_t hi = static_cast<std::size_t>(hi_it - vals.begin());
                const u128 count = static_cast<u128>(hi - lo);
                const i64 sum_high = pref[hi] - pref[lo];
                total += count * static_cast<u128>(st.a) + static_cast<u128>(sum_high);
            }
        }
    }

    return total;
}

bool run_checkpoints() {
    if (solve_sum(1000LL) != static_cast<u128>(4345ULL)) {
        std::cerr << "Checkpoint failed: sum <= 1000\n";
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }

    if (options.run_checkpoints && !run_checkpoints()) {
        return 1;
    }

    const u128 answer = solve_sum(options.limit);
    std::cout << static_cast<u64>(answer) << '\n';
    return 0;
}

Python

import bisect
import math

class LowState:
    def __init__(self, b, a, last):
        self.b = b
        self.a = a
        self.last = last

class HighState:
    def __init__(self, b, a, first):
        self.b = b
        self.a = a
        self.first = first

class Bucket:
    def __init__(self):
        self.values = []
        self.pref = []

def build_fib():
    f = [0] * 100
    f[0] = 0
    f[1] = 1
    for i in range(2, 100):
        f[i] = f[i - 1] + f[i - 2]
    return f

def build_pair_coefficients(fib, max_index):
    coeff_a = [0] * (max_index + 1)
    coeff_b = [0] * (max_index + 1)

    for i in range(max_index + 1):
        if i == 0:
            pos_a = 1
            pos_b = 0
        else:
            pos_a = fib[i - 1]
            pos_b = fib[i]

        m = i + 1
        sign = 1 if m % 2 == 0 else -1
        neg_a = sign * fib[m + 1]
        neg_b = -sign * fib[m]

        coeff_a[i] = pos_a + neg_a
        coeff_b[i] = pos_b + neg_b

    return coeff_a, coeff_b

def min_max_possible_a_for_length(n, coeff_a):
    kInf = 1 << 62
    min_dp = [[kInf, kInf] for _ in range(n + 1)]
    max_dp = [[-kInf, -kInf] for _ in range(n + 1)]
    min_dp[n] = [0, 0]
    max_dp[n] = [0, 0]

    for idx in range(n - 1, -1, -1):
        for prev in range(2):
            best_min = kInf
            best_max = -kInf

            def relax(bit):
                nonlocal best_min, best_max
                if prev == 1 and bit == 1:
                    return
                add = coeff_a[idx] if bit == 1 else 0
                child_min = min_dp[idx + 1][bit]
                child_max = max_dp[idx + 1][bit]
                if child_min >= kInf // 2 or child_max <= -kInf // 2:
                    return
                if add + child_min < best_min:
                    best_min = add + child_min
                if add + child_max > best_max:
                    best_max = add + child_max

            if idx == 0:
                relax(0)
            elif idx == n - 1:
                relax(1)
            else:
                relax(0)
                relax(1)

            min_dp[idx][prev] = best_min
            max_dp[idx][prev] = best_max

    return min_dp[0][0], max_dp[0][0]

def enumerate_low_states(end, coeff_a, coeff_b):
    out = []
    
    def dfs(idx, prev, sum_b, sum_a, last):
        if idx > end:
            out.append(LowState(sum_b, sum_a, last))
            return
        if idx == 0:
            dfs(1, 0, sum_b, sum_a, 0)
            return

        dfs(idx + 1, 0, sum_b, sum_a, 0)

        if prev == 0:
            dfs(idx + 1, 1, sum_b + coeff_b[idx], sum_a + coeff_a[idx], 1)

    if end < 0:
        out.append(LowState(0, 0, 0))
        return out
        
    dfs(0, 0, 0, 0, 0)
    return out

def enumerate_high_states(start, end, coeff_a, coeff_b):
    out = []
    
    def dfs(idx, prev, sum_b, sum_a, first):
        if idx > end:
            out.append(HighState(sum_b, sum_a, first))
            return

        def first_after(bit):
            return bit if idx == start else first

        if idx == end:
            if prev == 1:
                return
            dfs(idx + 1, 1, sum_b + coeff_b[idx], sum_a + coeff_a[idx], first_after(1))
            return

        dfs(idx + 1, 0, sum_b, sum_a, first_after(0))

        if prev == 0:
            dfs(idx + 1, 1, sum_b + coeff_b[idx], sum_a + coeff_a[idx], first_after(1))

    if start > end:
        out.append(HighState(0, 0, 0))
        return out
        
    dfs(start, 0, 0, 0, 0)
    return out

def solve_sum(limit):
    max_index = 64
    fib = build_fib()
    coeff_a, coeff_b = build_pair_coefficients(fib, max_index)

    total = 1

    for n in range(2, 65):
        min_a, max_a = min_max_possible_a_for_length(n, coeff_a)
        if max_a < 1 or min_a > limit:
            continue

        mid = n // 2
        low_states = enumerate_low_states(mid - 1, coeff_a, coeff_b)
        high_states = enumerate_high_states(mid, n - 1, coeff_a, coeff_b)

        high_maps = [{}, {}]

        for st in high_states:
            b_val = st.b
            if b_val not in high_maps[st.first]:
                high_maps[st.first][b_val] = Bucket()
            high_maps[st.first][b_val].values.append(st.a)

        for fb in range(2):
            for b_val, bucket in high_maps[fb].items():
                bucket.values.sort()
                vals = bucket.values
                pref = [0] * (len(vals) + 1)
                for i in range(len(vals)):
                    pref[i + 1] = pref[i] + vals[i]
                bucket.pref = pref

        for st in low_states:
            for fb in range(2):
                if st.last == 1 and fb == 1:
                    continue
                target_b = -st.b
                if target_b not in high_maps[fb]:
                    continue

                bucket = high_maps[fb][target_b]
                vals = bucket.values
                pref = bucket.pref
                
                low_needed = 1 - st.a
                high_needed = limit - st.a

                lo = bisect.bisect_left(vals, low_needed)
                hi = bisect.bisect_right(vals, high_needed)

                if lo == hi:
                    continue

                count = hi - lo
                sum_high = pref[hi] - pref[lo]
                total += count * st.a + sum_high

    return total

def solve():
    limit = 10_000_000_000
    ans = solve_sum(limit)
    return str(ans)

if __name__ == '__main__':
    print(solve())

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Euler473 {

    static class LowState {
        long b, a;
        int last;

        LowState(long b, long a, int last) {
            this.b = b;
            this.a = a;
            this.last = last;
        }
    }

    static class HighState {
        long b, a;
        int first;

        HighState(long b, long a, int first) {
            this.b = b;
            this.a = a;
            this.first = first;
        }
    }

    static class Bucket {
        List<Long> values = new ArrayList<>();
        long[] pref;
    }

    private static long[] buildFib() {
        long[] f = new long[100];
        f[0] = 0;
        f[1] = 1;
        for (int i = 2; i < 100; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }

    private static void buildPairCoefficients(long[] fib, long[] coeffA, long[] coeffB, int maxIndex) {
        for (int i = 0; i <= maxIndex; i++) {
            long posA = 0;
            long posB = 0;
            if (i == 0) {
                posA = 1;
                posB = 0;
            } else {
                posA = fib[i - 1];
                posB = fib[i];
            }

            int m = i + 1;
            long sign = (m % 2 == 0) ? 1 : -1;
            long negA = sign * fib[m + 1];
            long negB = -sign * fib[m];

            coeffA[i] = posA + negA;
            coeffB[i] = posB + negB;
        }
    }

    private static long[] minMaxPossibleA(int n, long[] coeffA) {
        long kInf = 1L << 61;
        long[][] minDp = new long[n + 1][2];
        long[][] maxDp = new long[n + 1][2];

        for (int i = 0; i <= n; i++) {
            minDp[i][0] = kInf;
            minDp[i][1] = kInf;
            maxDp[i][0] = -kInf;
            maxDp[i][1] = -kInf;
        }
        minDp[n][0] = 0;
        minDp[n][1] = 0;
        maxDp[n][0] = 0;
        maxDp[n][1] = 0;

        for (int idx = n - 1; idx >= 0; idx--) {
            for (int prev = 0; prev <= 1; prev++) {
                long bestMin = kInf;
                long bestMax = -kInf;

                for (int bit = 0; bit <= 1; bit++) {
                    if (idx == 0 && bit == 1)
                        continue;
                    if (idx == n - 1 && bit == 0)
                        continue;
                    if (prev == 1 && bit == 1)
                        continue;

                    long add = (bit == 1) ? coeffA[idx] : 0;
                    long childMin = minDp[idx + 1][bit];
                    long childMax = maxDp[idx + 1][bit];

                    if (childMin >= kInf / 2 || childMax <= -kInf / 2)
                        continue;

                    bestMin = Math.min(bestMin, add + childMin);
                    bestMax = Math.max(bestMax, add + childMax);
                }

                minDp[idx][prev] = bestMin;
                maxDp[idx][prev] = bestMax;
            }
        }
        return new long[] { minDp[0][0], maxDp[0][0] };
    }

    private static void dfsLow(int idx, int prev, long sumB, long sumA, int last, int end, long[] coeffA, long[] coeffB,
            List<LowState> out) {
        if (idx > end) {
            out.add(new LowState(sumB, sumA, last));
            return;
        }
        if (idx == 0) {
            dfsLow(1, 0, sumB, sumA, 0, end, coeffA, coeffB, out);
            return;
        }

        dfsLow(idx + 1, 0, sumB, sumA, 0, end, coeffA, coeffB, out);

        if (prev == 0) {
            dfsLow(idx + 1, 1, sumB + coeffB[idx], sumA + coeffA[idx], 1, end, coeffA, coeffB, out);
        }
    }

    private static void dfsHigh(int idx, int prev, long sumB, long sumA, int first, int start, int end, long[] coeffA,
            long[] coeffB, List<HighState> out) {
        if (idx > end) {
            out.add(new HighState(sumB, sumA, first));
            return;
        }

        if (idx == end) {
            if (prev == 1)
                return;
            dfsHigh(idx + 1, 1, sumB + coeffB[idx], sumA + coeffA[idx], idx == start ? 1 : first, start, end, coeffA,
                    coeffB, out);
            return;
        }

        dfsHigh(idx + 1, 0, sumB, sumA, idx == start ? 0 : first, start, end, coeffA, coeffB, out);

        if (prev == 0) {
            dfsHigh(idx + 1, 1, sumB + coeffB[idx], sumA + coeffA[idx], idx == start ? 1 : first, start, end, coeffA,
                    coeffB, out);
        }
    }

    private static long solveSum(long limit) {
        int maxIndex = 64;
        long[] fib = buildFib();
        long[] coeffA = new long[maxIndex + 1];
        long[] coeffB = new long[maxIndex + 1];
        buildPairCoefficients(fib, coeffA, coeffB, maxIndex);

        long total = 1;

        for (int n = 2; n <= 64; n++) {
            long[] minMax = minMaxPossibleA(n, coeffA);
            long minA = minMax[0];
            long maxA = minMax[1];

            if (maxA < 1 || minA > limit)
                continue;

            int mid = n / 2;
            List<LowState> lowStates = new ArrayList<>();
            if (mid - 1 < 0) {
                lowStates.add(new LowState(0, 0, 0));
            } else {
                dfsLow(0, 0, 0, 0, 0, mid - 1, coeffA, coeffB, lowStates);
            }

            List<HighState> highStates = new ArrayList<>();
            if (mid > n - 1) {
                highStates.add(new HighState(0, 0, 0));
            } else {
                dfsHigh(mid, 0, 0, 0, 0, mid, n - 1, coeffA, coeffB, highStates);
            }

            Map<Long, Bucket>[] highMaps = new Map[] { new HashMap<>(), new HashMap<>() };

            for (HighState st : highStates) {
                if (!highMaps[st.first].containsKey(st.b)) {
                    highMaps[st.first].put(st.b, new Bucket());
                }
                highMaps[st.first].get(st.b).values.add(st.a);
            }

            for (int fb = 0; fb <= 1; fb++) {
                for (Bucket bucket : highMaps[fb].values()) {
                    Collections.sort(bucket.values);
                    bucket.pref = new long[bucket.values.size() + 1];
                    for (int i = 0; i < bucket.values.size(); i++) {
                        bucket.pref[i + 1] = bucket.pref[i] + bucket.values.get(i);
                    }
                }
            }

            for (LowState st : lowStates) {
                for (int fb = 0; fb <= 1; fb++) {
                    if (st.last == 1 && fb == 1)
                        continue;
                    long targetB = -st.b;
                    if (!highMaps[fb].containsKey(targetB))
                        continue;

                    Bucket bucket = highMaps[fb].get(targetB);
                    List<Long> pop = bucket.values;
                    long lowNeeded = 1 - st.a;
                    long highNeeded = limit - st.a;

                    int lo = lowerBound(pop, lowNeeded);
                    int hi = upperBound(pop, highNeeded);

                    if (lo == hi)
                        continue;

                    long count = hi - lo;
                    long sumHigh = bucket.pref[hi] - bucket.pref[lo];
                    total += count * st.a + sumHigh;
                }
            }
        }

        return total;
    }

    private static int lowerBound(List<Long> arr, long target) {
        int low = 0, high = arr.size();
        while (low < high) {
            int mid = (low + high) >>> 1;
            if (arr.get(mid) < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    private static int upperBound(List<Long> arr, long target) {
        int low = 0, high = arr.size();
        while (low < high) {
            int mid = (low + high) >>> 1;
            if (arr.get(mid) <= target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    public static void main(String[] args) {
        long limit = 10_000_000_000L;
        long ans = solveSum(limit);
        System.out.println(ans);
    }
}