Detailed mathematical approach

Problem Summary

For each positive integer \(n\), let \(s(n)\) be the number of cube-full divisors of \(n\). A positive integer \(d=\prod p_i^{e_i}\) is cube-full when every prime that appears has exponent at least \(3\). By the usual empty-product convention, \(1\) is cube-full as well. The goal is to compute

$S(N)=\sum_{n=1}^{N}s(n)$

for the huge value \(N=10^{18}\). Factoring every integer up to \(N\) is impossible, so the solution reorganizes the count around the cube-full divisors themselves.

Mathematical Approach

The central observation is that it is much easier to count how often a fixed cube-full divisor occurs than to inspect every integer \(n\) separately.

Step 1: Swap the order of counting

For a fixed integer \(n\), the number of cube-full divisors is

$s(n)=\sum_{\substack{d\mid n\\ d\ \text{cube-full}}}1.$

Now sum this over all \(1\le n\le N\):

$S(N)=\sum_{n=1}^{N}\sum_{\substack{d\mid n\\ d\ \text{cube-full}}}1.$

Interchanging the two sums gives

$S(N)=\sum_{\substack{d\le N\\ d\ \text{cube-full}}}\left\lfloor\frac{N}{d}\right\rfloor.$

This formula is exact because \(\lfloor N/d\rfloor\) is precisely the number of multiples of \(d\) in \(\{1,2,\dots,N\}\). So the whole task reduces to enumerating all cube-full numbers \(d\le N\).

Step 2: Describe the structure of a cube-full number

If

$d=\prod_{i=1}^{k} p_i^{e_i},$

then \(d\) is cube-full exactly when every exponent satisfies \(e_i\ge 3\). There are no allowed exponents \(1\) or \(2\). Therefore a cube-full number is determined by two pieces of data:

its distinct prime factors, listed in increasing order, and the exponent chosen for each of those primes from the set \(\{3,4,5,\dots\}\).

This is why the search naturally becomes a recursion over primes. The number \(1\) fits the same framework as the empty choice of primes and contributes the term \(\lfloor N/1\rfloor=N\).

Step 3: Limit the prime search to the integer cube root

If a prime \(p\) appears in a cube-full divisor \(d\le N\), then \(p^3\mid d\), hence

$p^3\le d\le N.$

So every relevant prime must satisfy

$p\le \left\lfloor\sqrt[3]{N}\right\rfloor.$

That is a dramatic reduction. For \(N=10^{18}\), the bound is only \(10^6\), so a simple prime sieve is sufficient to generate every prime that can possibly participate in the recursion.

Step 4: Enumerate every cube-full number exactly once

Start from the current product \(d=1\). At each stage, choose the next prime only from positions after the primes already used. If the next chosen prime is \(p\), its first legal contribution is \(p^3\), and then the same prime may be raised to exponent \(4,5,6,\dots\) as long as the product stays at most \(N\).

This produces a unique construction path for every cube-full number. Indeed, if

$d=q_1^{a_1}q_2^{a_2}\cdots q_m^{a_m},\qquad q_1<q_2<\cdots<q_m,\qquad a_i\ge 3,$

then the recursion can reach \(d\) only by choosing \(q_1\) first with exponent \(a_1\), then \(q_2\), and so on. Because later recursive levels are allowed to use only larger primes, no alternative ordering is possible, so there is no double counting.

Step 5: Use the monotone cutoff to prune the search

Suppose the current cube-full product is \(d\). For a candidate next prime \(p\), the smallest new factor would be \(p^3\). If

$d\,p^3>N,$

then this prime cannot be used, and neither can any larger prime, because larger primes have even larger cubes. The prime loop can stop immediately at that point. This monotonicity is the key reason the recursion stays small.

Worked Example: \(N=100\)

The cube-full numbers not exceeding \(100\) are

$1,\ 8,\ 16,\ 27,\ 32,\ 64,\ 81.$

Therefore

$S(100)=\left\lfloor\frac{100}{1}\right\rfloor+\left\lfloor\frac{100}{8}\right\rfloor+\left\lfloor\frac{100}{16}\right\rfloor+\left\lfloor\frac{100}{27}\right\rfloor+\left\lfloor\frac{100}{32}\right\rfloor+\left\lfloor\frac{100}{64}\right\rfloor+\left\lfloor\frac{100}{81}\right\rfloor.$

Evaluating the floors gives

$100+12+6+3+3+1+1=126.$

This matches the small checkpoint used by the implementation, so the summation identity and the enumeration logic agree.

How the Code Works

The C++, Python, and Java implementations all follow the same algorithm. First they compute the integer cube root \(L=\lfloor\sqrt[3]{N}\rfloor\) with a safe binary search, then they generate all primes up to \(L\) with a sieve.

After that, a depth-first recursion represents the current cube-full divisor \(d\). The moment such a value is constructed, the implementation adds \(\lfloor N/d\rfloor\) to the running total, because that is exactly the number of integers up to \(N\) divisible by \(d\).

From each recursive state, the implementation scans the remaining primes in increasing order. For each chosen prime it begins with the third power, then keeps multiplying by the same prime so that exponents \(3,4,5,\dots\) are all covered. The recursive call then moves to later primes only, which is what enforces uniqueness.

The three language versions differ only in low-level arithmetic safeguards. The C++ version uses wider integer arithmetic for some cube and product checks, the Java version rewrites an overflow-sensitive product test as a division test, and Python relies on arbitrary-precision integers. The underlying counting method is identical in all three.

The C++ implementation also includes a few tiny sanity checks, including one brute-force comparison on a small bound, before printing the final \(N=10^{18}\) result.

Complexity Analysis

Let \(L=\lfloor\sqrt[3]{N}\rfloor\). Building the prime list up to \(L\) costs \(O(L\log\log L)\) time and \(O(L)\) memory. If \(C(N)\) denotes the number of cube-full integers not exceeding \(N\), the recursive part visits each of those values exactly once, so the dominant extra work is proportional to the generated search tree rather than to \(N\) itself.

Memory usage remains modest: the sieve or prime list up to \(L\), the recursion stack, and a few integer temporaries. The recursion depth is only the number of distinct primes that appear in the current cube-full number, so it stays small in practice.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=694
2. Cube-full numbers as a \(k\)-full generalization of powerful numbers: Wikipedia — Powerful number
3. Divisor-counting background: Wikipedia — Divisor function
4. Prime generation by sieving: Wikipedia — Sieve of Eratosthenes
5. Search-tree traversal: Wikipedia — Depth-first search