Problem 472: Comfortable Distance II
View on Project EulerProject Euler Problem 472 Solution
EulerSolve provides an optimized solution for Project Euler Problem 472, Comfortable Distance II, with C++, Python, Java, and a step-by-step mathematical explanation.
Problem Summary This problem defines an integer sequence \(f(n)\) coming from the comfortable-distance construction and asks for the large prefix sum $$S(n)=\sum_{k=1}^{n} f(k),$$ with the final result reported modulo \(10^8\). The implementations target values as large as \(n=10^{12}\), so a direct simulation of every term is completely impractical. The checkpoints built into the solution are $$f(1)=1,\qquad f(15)=9,\qquad f(20)=6,\qquad f(500)=16,$$ and $$S(20)=83,\qquad S(500)=13343.$$ The key observation is that the sequence is not generated term by term. Instead, it is organized into self-similar blocks on dyadic intervals, and each large block can be reduced to a smaller one plus three explicit arithmetic segments. Mathematical Approach For each \(k \ge 0\), define the block $$B_k=\bigl(f(2^k+1),f(2^k+2),\ldots,f(2^{k+1})\bigr),$$ so \(|B_k|=2^k\). Also define the power-of-two prefix and the internal block prefix by $$P_k=\sum_{n=1}^{2^k} f(n),\qquad G_k(m)=\sum_{j=1}^{m} B_k(j),\qquad G_k(0)=0.$$ Step 1: Seed Blocks and Notation The first five blocks are stored explicitly: $$B_0=(2),\qquad B_1=(2,4),$$ $$B_2=(3,6,2,6),\qquad B_3=(3,8,2,6,2,4,9,4),$$ $$B_4=(3,8,2,6,2,4,10,4,2,4,6,8,15,6,5,4).$$ Together with \(f(1)=1\), these values determine all small checkpoints. They also serve as the exact base of the recursion, so no approximation is introduced anywhere....
Detailed mathematical approach
Problem Summary
This problem defines an integer sequence \(f(n)\) coming from the comfortable-distance construction and asks for the large prefix sum
$$S(n)=\sum_{k=1}^{n} f(k),$$
with the final result reported modulo \(10^8\). The implementations target values as large as \(n=10^{12}\), so a direct simulation of every term is completely impractical. The checkpoints built into the solution are
$$f(1)=1,\qquad f(15)=9,\qquad f(20)=6,\qquad f(500)=16,$$
and
$$S(20)=83,\qquad S(500)=13343.$$
The key observation is that the sequence is not generated term by term. Instead, it is organized into self-similar blocks on dyadic intervals, and each large block can be reduced to a smaller one plus three explicit arithmetic segments.
Mathematical Approach
For each \(k \ge 0\), define the block
$$B_k=\bigl(f(2^k+1),f(2^k+2),\ldots,f(2^{k+1})\bigr),$$
so \(|B_k|=2^k\). Also define the power-of-two prefix and the internal block prefix by
$$P_k=\sum_{n=1}^{2^k} f(n),\qquad G_k(m)=\sum_{j=1}^{m} B_k(j),\qquad G_k(0)=0.$$
Step 1: Seed Blocks and Notation
The first five blocks are stored explicitly:
$$B_0=(2),\qquad B_1=(2,4),$$
$$B_2=(3,6,2,6),\qquad B_3=(3,8,2,6,2,4,9,4),$$
$$B_4=(3,8,2,6,2,4,10,4,2,4,6,8,15,6,5,4).$$
Together with \(f(1)=1\), these values determine all small checkpoints. They also serve as the exact base of the recursion, so no approximation is introduced anywhere.
Step 2: Large Blocks Split into Four Deterministic Pieces
For \(k \ge 5\), set
$$r=2^{k-3}.$$
Then \(|B_k|=2^k=8r\), and the block decomposes into four consecutive pieces:
$$\text{Part I: } B_k(1),\ldots,B_k(3r)=B_{k-1}(1),\ldots,B_{k-1}(3r),$$
$$\text{Part II: } 4r+2,\ 2r,\ 2r-2,\ \ldots,\ 4,$$
$$\text{Part III: } 2,\ 4,\ 6,\ \ldots,\ 4r,$$
$$\text{Part IV: } 6r+3,\ 2r+2,\ 2r+1,\ \ldots,\ 4.$$
So the first \(3r\) values are copied from the first three quarters of the previous block, while the remaining \(5r\) values are generated by closed arithmetic rules. This is the structural reason the problem becomes logarithmic rather than linear.
Step 3: Closed Forms for the Three New Pieces
Let the prefix sums of Parts II, III, and IV be denoted by \(A(r,m)\), \(E(m)\), and \(U(r,m)\).
For Part II, with \(1 \le m \le r\),
$$A(r,m)=4r+2+(m-1)(2r-m+2),$$
and the full segment sum is
$$\Sigma_A(r)=A(r,r)=r(r+5).$$
For Part III, with \(1 \le m \le 2r\),
$$E(m)=m(m+1),$$
because the segment is simply \(2,4,6,\ldots,2m\). Its full sum is
$$\Sigma_E(r)=E(2r)=4r^2+2r.$$
For Part IV, with \(1 \le m \le 2r\),
$$U(r,m)=6r+3+\frac{(m-1)(4r-m+6)}{2},$$
and the full segment sum is
$$\Sigma_U(r)=U(r,2r)=2r^2+11r.$$
If \(Q_k\) denotes the sum of the first three quarters of \(B_k\), then
$$Q_k=Q_{k-1}+\Sigma_A(r)+\Sigma_E(r)=Q_{k-1}+5r^2+7r,$$
and the whole block sum is
$$\Sigma_k=Q_k+\Sigma_U(r).$$
Step 4: Prefix Sums Reduce to One Block Query
Write any \(n \ge 1\) in the form
$$n=2^k+t,\qquad 0 \le t \le 2^k.$$
Then
$$S(n)=P_k+G_k(t).$$
For \(k \le 4\), \(G_k(t)\) is read directly from the stored seed-block prefixes. For \(k \ge 5\), the block prefix is piecewise:
$$G_k(t)= \begin{cases} 0, & t=0,\\ G_{k-1}(t), & 1 \le t \le 3r,\\ Q_{k-1}+A(r,t-3r), & 3r \lt t \le 4r,\\ Q_{k-1}+\Sigma_A(r)+E(t-4r), & 4r \lt t \le 6r,\\ Q_{k-1}+\Sigma_A(r)+\Sigma_E(r)+U(r,t-6r), & 6r \lt t \le 8r. \end{cases}$$
Only the first case makes a recursive descent, and each descent lowers the block index by one. That is why the query depth is \(O(\log n)\).
Step 5: Worked Example
The first nontrivial large block is \(B_5\), where \(r=2^{5-3}=4\). The first \(12\) entries are copied from the first \(12\) entries of \(B_4\):
$$3,8,2,6,2,4,10,4,2,4,6,8.$$
The three analytic pieces are then
$$18,8,6,4,$$
$$2,4,6,8,10,12,14,16,$$
and
$$27,10,9,8,7,6,5,4.$$
Hence
$$B_5=(3,8,2,6,2,4,10,4,2,4,6,8,18,8,6,4,2,4,6,8,10,12,14,16,27,10,9,8,7,6,5,4).$$
As a quick prefix check,
$$P_4=1+2+6+17+38=64,$$
and since \(20=16+4\),
$$S(20)=P_4+G_4(4)=64+(3+8+2+6)=83,$$
which matches the required checkpoint.
How the Code Works
The C++, Python, and Java implementations all follow the same plan. They store the five seed blocks, build prefix tables for those exact values, and then precompute for each higher level three quantities: the sum of the whole block, the sum of the first three quarters of the block, and the prefix sum up to the next power of two.
When a query \(S(n)\) arrives, the implementation finds the highest power of two not exceeding \(n\). The stored prefix up to that power contributes immediately, and only the remainder inside one block still has to be evaluated. That remainder is handled by the piecewise formulas above, using recursion only when the remainder falls into the copied first segment.
The arithmetic is exact before the final reduction modulo \(10^8\). The C++ version uses 128-bit integers for intermediate totals, the Java version uses arbitrary-precision integers, and the Python version relies on Python's built-in unbounded integers.
Complexity Analysis
If the target range is below \(2^{64}\), only \(64\) block levels are ever needed. Precomputing all stored block totals and power-of-two prefixes therefore costs \(O(\log n_{\max})\) time and \(O(\log n_{\max})\) memory. A single query for \(S(n)\) performs at most one descent per level, so its running time is \(O(\log n)\) and its extra working memory is \(O(1)\) beyond the precomputed tables.
Footnotes and References
- Problem page: https://projecteuler.net/problem=472
- Prefix sum: Wikipedia - Prefix sum
- Recurrence relation: Wikipedia - Recurrence relation
- Arithmetic progression: Wikipedia - Arithmetic progression
Problem 472 source code
C++
#include <array>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>
namespace {
using u64 = std::uint64_t;
using u128 = __uint128_t;
constexpr u64 kMod = 100'000'000ULL;
struct Options {
u64 n = 1'000'000'000'000ULL;
bool run_checkpoints = true;
};
bool parse_u64_after_prefix(const std::string& arg, const std::string& prefix, u64& 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<u64>(std::stoull(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_u64_after_prefix(arg, "--n=", options.n)) {
continue;
}
std::cerr << "Unknown argument: " << arg << '\n';
return false;
}
if (options.n == 0ULL) {
std::cerr << "--n must be positive.\n";
return false;
}
return true;
}
struct Precomp {
// block k stores f(2^k + 1) ... f(2^(k+1)), length 2^k
std::array<u128, 64> block_sum{};
std::array<u128, 64> block_pref_3q{};
std::array<u128, 64> pow_prefix{};
std::array<std::vector<u64>, 5> base_blocks{};
std::array<std::vector<u128>, 5> base_pref{};
};
u128 prefix_R(const u64 r, const u64 m) {
if (m == 0ULL) {
return 0;
}
if (m == 1ULL) {
return static_cast<u128>(4ULL * r + 2ULL);
}
const u64 t = m - 1ULL;
return static_cast<u128>(4ULL * r + 2ULL) + static_cast<u128>(t) *
static_cast<u128>(2ULL * r - m + 2ULL);
}
u128 sum_R(const u64 r) { return static_cast<u128>(r) * static_cast<u128>(r + 5ULL); }
u128 prefix_S(const u64 m) { return static_cast<u128>(m) * static_cast<u128>(m + 1ULL); }
u128 sum_S(const u64 r) {
const u128 rr = static_cast<u128>(r) * static_cast<u128>(r);
return 4ULL * rr + 2ULL * static_cast<u128>(r);
}
u128 prefix_U(const u64 r, const u64 m) {
if (m == 0ULL) {
return 0;
}
if (m == 1ULL) {
return static_cast<u128>(6ULL * r + 3ULL);
}
const u64 t = m - 1ULL;
return static_cast<u128>(6ULL * r + 3ULL) +
(static_cast<u128>(t) * static_cast<u128>(4ULL * r - m + 6ULL)) / 2ULL;
}
u128 sum_U(const u64 r) {
const u128 rr = static_cast<u128>(r) * static_cast<u128>(r);
return 2ULL * rr + 11ULL * static_cast<u128>(r);
}
Precomp build_precomp() {
Precomp pc;
pc.base_blocks[0] = {2ULL};
pc.base_blocks[1] = {2ULL, 4ULL};
pc.base_blocks[2] = {3ULL, 6ULL, 2ULL, 6ULL};
pc.base_blocks[3] = {3ULL, 8ULL, 2ULL, 6ULL, 2ULL, 4ULL, 9ULL, 4ULL};
pc.base_blocks[4] = {3ULL, 8ULL, 2ULL, 6ULL, 2ULL, 4ULL, 10ULL, 4ULL,
2ULL, 4ULL, 6ULL, 8ULL, 15ULL, 6ULL, 5ULL, 4ULL};
for (int k = 0; k <= 4; ++k) {
const auto& blk = pc.base_blocks[static_cast<std::size_t>(k)];
auto& pref = pc.base_pref[static_cast<std::size_t>(k)];
pref.assign(blk.size() + 1U, 0);
for (std::size_t i = 0; i < blk.size(); ++i) {
pref[i + 1U] = pref[i] + static_cast<u128>(blk[i]);
}
pc.block_sum[static_cast<std::size_t>(k)] = pref.back();
const std::size_t first_three_quarters = (3ULL * (1ULL << k)) / 4ULL;
pc.block_pref_3q[static_cast<std::size_t>(k)] = pref[first_three_quarters];
}
for (int k = 5; k < 64; ++k) {
const u64 r = (1ULL << (k - 3));
const u128 rr = static_cast<u128>(r) * static_cast<u128>(r);
pc.block_pref_3q[static_cast<std::size_t>(k)] =
pc.block_pref_3q[static_cast<std::size_t>(k - 1)] + 5ULL * rr + 7ULL * r;
pc.block_sum[static_cast<std::size_t>(k)] =
pc.block_pref_3q[static_cast<std::size_t>(k)] + 2ULL * rr + 11ULL * r;
}
pc.pow_prefix[0] = 1; // sum_{n<=1} f(n)
for (int k = 1; k < 64; ++k) {
pc.pow_prefix[static_cast<std::size_t>(k)] =
pc.pow_prefix[static_cast<std::size_t>(k - 1)] +
pc.block_sum[static_cast<std::size_t>(k - 1)];
}
return pc;
}
u128 block_prefix_sum(const Precomp& pc, const int k, const u64 m) {
if (m == 0ULL) {
return 0;
}
const u64 len = (1ULL << k);
if (m >= len) {
return pc.block_sum[static_cast<std::size_t>(k)];
}
if (k <= 4) {
return pc.base_pref[static_cast<std::size_t>(k)][static_cast<std::size_t>(m)];
}
const u64 q = 3ULL * (1ULL << (k - 3));
const u64 r = (1ULL << (k - 3));
const u64 s = (1ULL << (k - 2));
if (m <= q) {
return block_prefix_sum(pc, k - 1, m);
}
if (m <= q + r) {
return pc.block_pref_3q[static_cast<std::size_t>(k - 1)] + prefix_R(r, m - q);
}
if (m <= q + r + s) {
return pc.block_pref_3q[static_cast<std::size_t>(k - 1)] + sum_R(r) +
prefix_S(m - q - r);
}
return pc.block_pref_3q[static_cast<std::size_t>(k - 1)] + sum_R(r) + sum_S(r) +
prefix_U(r, m - q - r - s);
}
u128 prefix_sum(const Precomp& pc, const u64 n) {
if (n == 0ULL) {
return 0;
}
if (n == 1ULL) {
return 1;
}
const int k = 63 - __builtin_clzll(n);
const u64 p = (1ULL << k);
u128 out = pc.pow_prefix[static_cast<std::size_t>(k)];
if (n > p) {
out += block_prefix_sum(pc, k, n - p);
}
return out;
}
u64 f_value(const Precomp& pc, const u64 n) {
if (n == 0ULL) {
return 0ULL;
}
return static_cast<u64>(prefix_sum(pc, n) - prefix_sum(pc, n - 1ULL));
}
bool run_checkpoints(const Precomp& pc) {
if (f_value(pc, 1ULL) != 1ULL) {
std::cerr << "Checkpoint failed: f(1)\n";
return false;
}
if (f_value(pc, 15ULL) != 9ULL) {
std::cerr << "Checkpoint failed: f(15)\n";
return false;
}
if (f_value(pc, 20ULL) != 6ULL) {
std::cerr << "Checkpoint failed: f(20)\n";
return false;
}
if (f_value(pc, 500ULL) != 16ULL) {
std::cerr << "Checkpoint failed: f(500)\n";
return false;
}
if (prefix_sum(pc, 20ULL) != static_cast<u128>(83ULL)) {
std::cerr << "Checkpoint failed: sum f(N), 1<=N<=20\n";
return false;
}
if (prefix_sum(pc, 500ULL) != static_cast<u128>(13'343ULL)) {
std::cerr << "Checkpoint failed: sum f(N), 1<=N<=500\n";
return false;
}
return true;
}
} // namespace
int main(int argc, char** argv) {
Options options;
if (!parse_arguments(argc, argv, options)) {
return 1;
}
const Precomp pc = build_precomp();
if (options.run_checkpoints && !run_checkpoints(pc)) {
return 1;
}
const u128 total = prefix_sum(pc, options.n);
const u64 answer = static_cast<u64>(total % static_cast<u128>(kMod));
std::cout << std::setw(8) << std::setfill('0') << answer << '\n';
return 0;
}
Python
def prefix_R(r, m):
if m == 0:
return 0
if m == 1:
return 4 * r + 2
t = m - 1
return (4 * r + 2) + t * (2 * r - m + 2)
def sum_R(r):
return r * (r + 5)
def prefix_S(m):
return m * (m + 1)
def sum_S(r):
rr = r * r
return 4 * rr + 2 * r
def prefix_U(r, m):
if m == 0:
return 0
if m == 1:
return 6 * r + 3
t = m - 1
return (6 * r + 3) + (t * (4 * r - m + 6)) // 2
def sum_U(r):
rr = r * r
return 2 * rr + 11 * r
class Precomp:
def __init__(self):
self.block_sum = [0] * 64
self.block_pref_3q = [0] * 64
self.pow_prefix = [0] * 64
self.base_blocks = [[] for _ in range(5)]
self.base_pref = [[] for _ in range(5)]
def build_precomp():
pc = Precomp()
pc.base_blocks[0] = [2]
pc.base_blocks[1] = [2, 4]
pc.base_blocks[2] = [3, 6, 2, 6]
pc.base_blocks[3] = [3, 8, 2, 6, 2, 4, 9, 4]
pc.base_blocks[4] = [3, 8, 2, 6, 2, 4, 10, 4, 2, 4, 6, 8, 15, 6, 5, 4]
for k in range(5):
blk = pc.base_blocks[k]
pref = [0] * (len(blk) + 1)
for i in range(len(blk)):
pref[i + 1] = pref[i] + blk[i]
pc.base_pref[k] = pref
pc.block_sum[k] = pref[-1]
first_three_quarters = (3 * (1 << k)) // 4
pc.block_pref_3q[k] = pref[first_three_quarters]
for k in range(5, 64):
r = 1 << (k - 3)
rr = r * r
pc.block_pref_3q[k] = pc.block_pref_3q[k - 1] + 5 * rr + 7 * r
pc.block_sum[k] = pc.block_pref_3q[k] + 2 * rr + 11 * r
pc.pow_prefix[0] = 1
for k in range(1, 64):
pc.pow_prefix[k] = pc.pow_prefix[k - 1] + pc.block_sum[k - 1]
return pc
def block_prefix_sum(pc, k, m):
if m == 0:
return 0
length = 1 << k
if m >= length:
return pc.block_sum[k]
if k <= 4:
return pc.base_pref[k][m]
q = 3 * (1 << (k - 3))
r = 1 << (k - 3)
s = 1 << (k - 2)
if m <= q:
return block_prefix_sum(pc, k - 1, m)
if m <= q + r:
return pc.block_pref_3q[k - 1] + prefix_R(r, m - q)
if m <= q + r + s:
return pc.block_pref_3q[k - 1] + sum_R(r) + prefix_S(m - q - r)
return pc.block_pref_3q[k - 1] + sum_R(r) + sum_S(r) + prefix_U(r, m - q - r - s)
def prefix_sum(pc, n):
if n == 0:
return 0
if n == 1:
return 1
k = n.bit_length() - 1
p = 1 << k
out = pc.pow_prefix[k]
if n > p:
out += block_prefix_sum(pc, k, n - p)
return out
def solve():
n = 1_000_000_000_000
mod = 100_000_000
pc = build_precomp()
total = prefix_sum(pc, n)
# Output properly zero-padded to 8 digits
return f"{total % mod:08d}"
if __name__ == '__main__':
print(solve())
Java
import java.math.BigInteger;
public class Euler472 {
private static final long MOD = 100_000_000L;
private static class Precomp {
BigInteger[] blockSum = new BigInteger[64];
BigInteger[] blockPref3q = new BigInteger[64];
BigInteger[] powPrefix = new BigInteger[64];
long[][] baseBlocks = new long[5][];
BigInteger[][] basePref = new BigInteger[5][];
public Precomp() {
for (int i = 0; i < 64; i++) {
blockSum[i] = BigInteger.ZERO;
blockPref3q[i] = BigInteger.ZERO;
powPrefix[i] = BigInteger.ZERO;
}
}
}
private static BigInteger b(long v) {
return BigInteger.valueOf(v);
}
private static BigInteger prefixR(long r, long m) {
if (m == 0)
return BigInteger.ZERO;
if (m == 1)
return b(4 * r + 2);
long t = m - 1;
BigInteger p1 = b(4 * r + 2);
BigInteger p2 = b(t).multiply(b(2 * r - m + 2));
return p1.add(p2);
}
private static BigInteger sumR(long r) {
return b(r).multiply(b(r + 5));
}
private static BigInteger prefixS(long m) {
return b(m).multiply(b(m + 1));
}
private static BigInteger sumS(long r) {
BigInteger rr = b(r).multiply(b(r));
return rr.multiply(b(4)).add(b(2 * r));
}
private static BigInteger prefixU(long r, long m) {
if (m == 0)
return BigInteger.ZERO;
if (m == 1)
return b(6 * r + 3);
long t = m - 1;
BigInteger p1 = b(6 * r + 3);
BigInteger p2 = b(t).multiply(b(4 * r - m + 6)).divide(b(2));
return p1.add(p2);
}
private static BigInteger sumU(long r) {
BigInteger rr = b(r).multiply(b(r));
return rr.multiply(b(2)).add(b(11 * r));
}
private static Precomp buildPrecomp() {
Precomp pc = new Precomp();
pc.baseBlocks[0] = new long[] { 2 };
pc.baseBlocks[1] = new long[] { 2, 4 };
pc.baseBlocks[2] = new long[] { 3, 6, 2, 6 };
pc.baseBlocks[3] = new long[] { 3, 8, 2, 6, 2, 4, 9, 4 };
pc.baseBlocks[4] = new long[] { 3, 8, 2, 6, 2, 4, 10, 4, 2, 4, 6, 8, 15, 6, 5, 4 };
for (int k = 0; k <= 4; ++k) {
long[] blk = pc.baseBlocks[k];
pc.basePref[k] = new BigInteger[blk.length + 1];
pc.basePref[k][0] = BigInteger.ZERO;
for (int i = 0; i < blk.length; ++i) {
pc.basePref[k][i + 1] = pc.basePref[k][i].add(b(blk[i]));
}
pc.blockSum[k] = pc.basePref[k][blk.length];
int firstThreeQuarters = (3 * (1 << k)) / 4;
pc.blockPref3q[k] = pc.basePref[k][firstThreeQuarters];
}
for (int k = 5; k < 64; ++k) {
long r = 1L << (k - 3);
BigInteger rr = b(r).multiply(b(r));
pc.blockPref3q[k] = pc.blockPref3q[k - 1].add(b(5).multiply(rr)).add(b(7 * r));
pc.blockSum[k] = pc.blockPref3q[k].add(b(2).multiply(rr)).add(b(11 * r));
}
pc.powPrefix[0] = BigInteger.ONE;
for (int k = 1; k < 64; ++k) {
pc.powPrefix[k] = pc.powPrefix[k - 1].add(pc.blockSum[k - 1]);
}
return pc;
}
private static BigInteger blockPrefixSum(Precomp pc, int k, long m) {
if (m == 0)
return BigInteger.ZERO;
long len = 1L << k;
if (m >= len)
return pc.blockSum[k];
if (k <= 4) {
return pc.basePref[k][(int) m];
}
long q = 3L * (1L << (k - 3));
long r = 1L << (k - 3);
long s = 1L << (k - 2);
if (m <= q) {
return blockPrefixSum(pc, k - 1, m);
}
if (m <= q + r) {
return pc.blockPref3q[k - 1].add(prefixR(r, m - q));
}
if (m <= q + r + s) {
return pc.blockPref3q[k - 1].add(sumR(r)).add(prefixS(m - q - r));
}
return pc.blockPref3q[k - 1].add(sumR(r)).add(sumS(r)).add(prefixU(r, m - q - r - s));
}
private static BigInteger prefixSum(Precomp pc, long n) {
if (n == 0)
return BigInteger.ZERO;
if (n == 1)
return BigInteger.ONE;
int k = 63 - Long.numberOfLeadingZeros(n);
long p = 1L << k;
BigInteger out = pc.powPrefix[k];
if (n > p) {
out = out.add(blockPrefixSum(pc, k, n - p));
}
return out;
}
public static void main(String[] args) {
long n = 1_000_000_000_000L;
Precomp pc = buildPrecomp();
BigInteger total = prefixSum(pc, n);
long answer = total.remainder(b(MOD)).longValue();
System.out.printf("%08d%n", answer);
}
}