Project Euler Problem 749
A positive integer, n, is a near power sum if there exists a positive integer, k, such that the sum of the kth powers of
Solution
Answer: 13459471903176422
Let
$$f_k(n)=\sum (\text{digits of }n)^k.$$
We seek all positive integers $n$ such that for some $k\ge1$,
$$f_k(n)=n-1 \quad \text{or} \quad f_k(n)=n+1.$$
A standard optimization is to enumerate digit multisets instead of integers directly.
For a number with at most $16$ digits:
- the maximum possible value of $f_k(n)$ is $16\cdot 9^k$,
- so only finitely many even exponents $k$ need checking,
- and for each digit count vector $(c_0,\dots,c_9)$ we compute
$$s=\sum_{d=0}^9 c_d d^k,$$
then test whether $s-1$ or $s+1$ has exactly the same digit counts.
The exhaustive search finds all valid near power sums up to $16$ digits, and their total is:
$$S(16)=13459471903176422.$$
Answer: 13459471903176422