Detailed mathematical approach

Problem Summary

A near power sum is a positive integer \(n\) with decimal digits \(a_1,\dots,a_\ell\) for which there exists an integer \(k\ge 1\) such that

$\left|\sum_{i=1}^{\ell} a_i^k - n\right|=1.$

The task is to find every distinct near power sum with \(n\le 10^{16}-1\) and add them together. The crucial observation is that the power sum depends only on how many times each digit occurs, not on the order of those digits.

Mathematical Approach

Instead of scanning all integers below \(10^{16}\), the implementation scans digit multisets. For fixed length \(\ell\) and exponent \(k\), let \(c_d\) be the number of occurrences of digit \(d\). Then

$c_d\in\mathbb{Z}_{\ge 0},\qquad \sum_{d=0}^{9} c_d=\ell.$

From this count vector we define the digit-power sum

$P_k(c_0,\dots,c_9)=\sum_{d=0}^{9} c_d d^k.$

The whole search is built around this quantity.

Step 1: Replace Ordered Digits by a Count Vector

If two \(\ell\)-digit numbers use the same multiset of digits, they produce the same value of \(P_k\). Therefore the ordered decimal string is not the right object to enumerate. The right object is the vector \((c_0,\dots,c_9)\), which records how many zeros, ones, twos, and so on occur.

This compresses many permutations into one state. For example, the numbers \(35\) and \(53\) correspond to the same vector with \(c_3=c_5=1\) and all other counts equal to \(0\).

Step 2: A Fixed Multiset Gives Only Two Possible Values of \(n\)

If a number \(n\) with digit counts \((c_0,\dots,c_9)\) is a near power sum for exponent \(k\), then by definition

$P_k(c_0,\dots,c_9)=n-1 \qquad \text{or} \qquad P_k(c_0,\dots,c_9)=n+1.$

Equivalently, once the count vector and \(k\) are fixed, the only candidates are

$n=P_k(c_0,\dots,c_9)-1,\qquad n=P_k(c_0,\dots,c_9)+1.$

This is the key reduction. We do not need to generate every permutation of the chosen digits. We only need to test these two integers and verify whether one of them really has the same decimal digit frequencies and the same length \(\ell\).

Step 3: Enumerate Every Digit Multiset Exactly Once

For fixed \(\ell\), the admissible count vectors are exactly the weak compositions of \(\ell\) into \(10\) parts, so their number is

$\binom{\ell+9}{9}.$

A depth-first recursion can assign the count of digit \(0\), then digit \(1\), and so on, while keeping track of how many digit slots remain. When the remaining total reaches \(0\), we have one complete multiset. Because each vector is constructed once, there are no duplicate states coming from digit permutations.

The one degenerate leaf with \(c_0=\ell\) is discarded, since it corresponds only to the value \(0\), which is outside the positive search range.

Step 4: Bound the Exponent and Prune Impossible Branches

The implementations only need exponents up to \(53\). The reason is that

$2^{54}=18{,}014{,}398{,}509{,}481{,}984>10^{16}.$

So if \(k\ge 54\), then any occurrence of a digit \(d\ge 2\) already contributes more than the maximum possible value of \(n\pm 1\). That makes the branch impossible. If only digits \(0\) and \(1\) remain, then \(P_k\le 16\), which cannot produce any new valid near power sum with matching decimal length. Hence \(1\le k\le 53\) is a complete search.

There is also a branch-level pruning rule. During the recursion, the partial sum

$\sum_{d=0}^{m} c_d d^k$

can only increase as more digits are assigned. Once it exceeds \(10^{16}+1\), neither \(P_k-1\) nor \(P_k+1\) can lie in the allowed range, so that entire subtree can be abandoned immediately.

Step 5: Validate by Recounting the Candidate's Digits

The test at the leaf is exact. Given the completed multiset and exponent, compute \(P_k\), form the two candidates \(P_k-1\) and \(P_k+1\), and reject any value outside \(1\le n\le 10^{16}-1\). For each surviving candidate, recount its decimal digits. It is accepted if and only if its length is exactly \(\ell\) and its frequency table is identical to \((c_0,\dots,c_9)\).

This validation is what reconnects the multiset back to an actual number. A count vector may describe many permutations, but only the one or two numbers \(P_k\pm 1\) are relevant, and most of them fail the digit-frequency check.

Worked Example

Take \(\ell=2\), \(k=2\), and the multiset \(\{3,5\}\). Then \(c_3=c_5=1\) and all other counts are \(0\), so

$P_2=3^2+5^2=9+25=34.$

The only possible near power sums from this multiset are

$34-1=33,\qquad 34+1=35.$

The value \(33\) has digit counts \((0,0,0,2,0,\dots,0)\), so it fails. But \(35\) has exactly one \(3\) and one \(5\), so it is accepted.

Another simple example is \(\{5,7\}\) with \(k=2\):

$5^2+7^2=25+49=74,$

hence \(75\) is accepted. The implementations also contain the small checkpoint that the sum of all near power sums with at most two digits is

$110.$

How the Code Works

The C++, Python, and Java implementations all follow the same mathematical search. For each exponent \(k=1,\dots,53\), they precompute the ten values \(0^k,1^k,\dots,9^k\), capping any value that already exceeds the useful range. Then, for each length \(\ell=1,\dots,16\), they run a depth-first enumeration of all digit-count vectors whose entries sum to \(\ell\).

At each completed vector, the implementation forms the digit-power sum \(P_k\), tests the two candidates \(P_k-1\) and \(P_k+1\), and recounts the decimal digits of each candidate. A value is kept only if it is positive, within the \(16\)-digit limit, has exactly \(\ell\) digits, and reproduces the same digit-frequency vector that generated \(P_k\).

Accepted values are inserted into a set, because the same near power sum could in principle be discovered for more than one exponent. After the search finishes, the distinct stored values are added. The Java implementation performs this search directly, while the Python implementation delegates the heavy numerical work to the C++ program and returns the parsed result, so the underlying algorithm is still the same across all three implementations.

Complexity Analysis

Let \(D=16\) be the maximum number of digits and \(E=53\) the largest exponent that must be checked. For fixed \(\ell\), the number of digit multisets is \(\binom{\ell+9}{9}\), so the search examines

$E\sum_{\ell=1}^{D}\binom{\ell+9}{9}$

leaf states before pruning. Candidate validation scans at most \(\ell\) decimal digits, which yields the clean upper bound

$O\left(E\sum_{\ell=1}^{D}\ell\binom{\ell+9}{9}\right).$

For this problem, \(D\) and \(E\) are fixed constants, so the important practical point is not asymptotic growth but the reduction in state space: the algorithm explores digit multisets instead of almost \(10^{16}\) individual integers. The memory usage is \(O(10+D)\) for the current counts, recursion stack, and power table, plus \(O(S)\) for the set of \(S\) distinct near power sums that survive deduplication.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=749
2. Multiset: Wikipedia - Multiset
3. Stars and bars: Wikipedia - Stars and bars
4. Narcissistic number: Wikipedia - Narcissistic number
5. Depth-first search: Wikipedia - Depth-first search