Problem 749

Near Power Sums

A positive integer, $n$ , is a near power sum if there exists a positive integer, $k$ , such that the sum of the $k$ th powers of the digits in its decimal representation is equal to either $n + 1$ or $n - 1$ . For example $35$ is a near power sum number because $3^{2} + 5^{2} = 34$ .

Define $S (d)$ to be the sum of all near power sum numbers of $d$ digits or less.
Then $S (2) = 110$ and $S (6) = 2562701$ .

Find $S (16)$ .

近幂和数

对于正整数 $n$ ，若存在正整数 $k$ 使得 $n$ 的各位数字的 $k$ 次幂之和等于 $n + 1$ 或 $n - 1$ ，则我们称 $n$ 为近幂和数。例如， $35$ 是近幂和数，因为 $3^{2} + 5^{2} = 34$ 。

记 $S (d)$ 为所有至多 $d$ 位数字的近幂和数之和。
已知 $S (2) = 110$ ， $S (6) = 2562701$ 。

求 $S (16)$ 。