Detailed mathematical approach

Problem Summary

Let \(\operatorname{digitSum}(N)\) denote the sum of the decimal digits of \(N\). We want the increasing sequence of integers \(N\) with at least two digits such that

$N=\operatorname{digitSum}(N)^k,\qquad k\ge 2,\qquad N\ge 10.$

The task is to determine the 30th term of that sequence. Typical examples are \(81=9^2\), \(512=8^3\), \(2401=7^4\), and \(4913=17^3\). The important feature is that the base is not chosen freely: it is forced to be the digit sum of the final number.

A brute-force scan over all integers is the wrong viewpoint, because almost every number fails immediately. The implementations instead reverse the logic: they iterate over plausible digit sums \(s\), generate the power chain \(s^2,s^3,s^4,\dots\), and keep only the values whose digit sum comes back to \(s\).

Mathematical Approach

The whole solution is a bounded search over digit sums. Once the correct search space is identified, the rest is just a complete enumeration of short power chains.

The Base Is Determined by the Digit Sum

If a number \(N\) belongs to the sequence, then its defining base is

$s=\operatorname{digitSum}(N).$

So every valid term has the form \(N=s^k\) for some \(k\ge 2\). That means the real objects of interest are not arbitrary integers, but the chains of powers attached to possible digit sums. The search therefore starts at \(s=2\): \(s=1\) would only produce the one-digit value \(1\), which is excluded.

For a fixed \(s\), the candidates are exactly

$s^2,\ s^3,\ s^4,\ \dots$

No other numbers can possibly qualify for that same digit sum, because the defining equation already pins down the base.

A Decimal Bound Makes the Search Finite

Suppose we only care about valid terms up to a ceiling \(B\). Let \(d(x)\) be the number of decimal digits of \(x\). Then any \(N\le B\) satisfies

$\operatorname{digitSum}(N)\le 9\,d(N)\le 9\,d(B).$

Therefore every valid term below \(B\) must come from a base in the finite range

$2\le s\le 9\,d(B).$

This is the key invariant used by the implementations. One version computes that upper bound directly from the current ceiling. The fixed-ceiling versions use hard-coded safe ranges derived from the same idea, so the mathematics is identical even though the literal constant differs slightly.

The Power Chain Is Generated by a Simple Recurrence

For each candidate digit sum \(s\), the implementations do not recompute \(s^k\) from scratch. They use the recurrence

$v_2=s^2,\qquad v_{k+1}=s\,v_k\quad (k\ge 2).$

Because \(s\ge 2\), this chain is strictly increasing. So once a term exceeds the current ceiling \(B\), every later exponent is also too large, and that base can be abandoned permanently. This gives a complete and duplicate-free scan of all powers of \(s\) below the ceiling.

The completeness argument is short and decisive: if \(N\le B\) is valid, then its base is exactly \(s=\operatorname{digitSum}(N)\), and when that \(s\) is scanned, the recurrence eventually reaches \(s^k=N\) before the loop stops.

Worked Example

Take \(s=8\). The chain begins

$8^2=64,\qquad 8^3=512,\qquad 8^4=4096,\qquad 8^5=32768.$

The corresponding digit sums are

$\operatorname{digitSum}(64)=10,\qquad \operatorname{digitSum}(512)=8,\qquad \operatorname{digitSum}(4096)=19,\qquad \operatorname{digitSum}(32768)=26.$

So \(512\) is accepted, while the neighboring powers are rejected. The same pattern appears for other bases: \(17^2=289\) fails because its digit sum is \(19\), but \(17^3=4913\) succeeds because \(4+9+1+3=17\). This is why the search must test each power on the chain, not just the base itself.

Why Sorting the Hits Produces the Sequence

The natural search order is by digit sum \(s\), but the sequence in the problem is ordered by the numerical value of the final numbers. Those two orders do not match. A hit from a larger base can easily lie between hits produced by smaller bases.

So the implementations collect every valid value under the chosen ceiling, keep the collection deduplicated, and then read it in sorted order. The adaptive C++ version starts from a modest ceiling and multiplies it by 10 until at least the requested index is present. The Python and Java versions choose a single large ceiling near \(10^{18}\), which is sufficient for the 30th term. In both cases, once all hits below the ceiling have been generated, the required element is obtained by ordinary sorting and indexing.

How the Code Works

The C++, Python, and Java implementations all use the same core loop: iterate over candidate digit sums \(s\), start at \(s^2\), repeatedly multiply by \(s\), and after each multiplication compute the digit sum by stripping decimal digits with repeated division by 10. A value is recorded only if it has at least two digits and its digit sum is exactly \(s\).

The main difference is how the outer ceiling is managed. The C++ implementation is written for a general requested index, so it regenerates the full list under an initial ceiling and then raises that ceiling by powers of 10 until enough terms exist. The Python and Java implementations solve the specific 30th-term query directly under a single large ceiling. In the fixed-width languages, the repeated multiplication step is also guarded against overflow; the Python version relies on built-in arbitrary-precision integers even though the actual search still stays within the chosen bound.

Accepted values are stored in a deduplicated container and then read in increasing order. The C++ implementation also includes a small checkpoint that the second term is \(512\), which matches the worked example and confirms that the enumeration is behaving correctly before the requested index is returned.

Complexity Analysis

Let \(B\) be the search ceiling and let \(D=d(B)\) be its decimal digit count. There are \(O(D)\) candidate bases, because \(s\le 9D\). For a fixed base \(s\), the number of generated powers is

$\#\{k\ge 2:s^k\le B\}=\max\!\left(0,\left\lfloor \log_s B\right\rfloor-1\right),$

which is at most \(O(D)\). So the total number of tested powers is \(O(D^2)\).

Each test computes a digit sum over at most \(D\) decimal digits, so the overall work is \(O(D^3)\) in decimal-digit operations, or simply “tiny” for the concrete limits used here. Memory usage is \(O(m)\), where \(m\) is the number of accepted terms stored before the final lookup. The adaptive-ceiling version may repeat the bounded search a few times, but each repeat only changes the ceiling by one decimal order of magnitude, so the practical overhead remains small.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=119
2. Digit sum: Wikipedia - Digit sum
3. Exponentiation: Wikipedia - Exponentiation
4. Positional notation: Wikipedia - Positional notation
5. Arbitrary-precision arithmetic: Wikipedia - Arbitrary-precision arithmetic