Fast-Potenzsummen

Eine positive ganze Zahl $n$ heißt Fast-Potenzsumme, wenn es eine positive natürliche Zahl $k$ gibt, so dass die Summe der $k$-ten Potenzen der Ziffern in ihrer Dezimaldarstellung entweder $n+1$ oder $n-1$ ergibt. Beispielsweise ist 35 eine Fast-Potenzsumme wegen $3^2+5^2 = 34$.

Sei $S(d)$ die Summe aller Fast-Potenzsummen mit bis zu $d$ Ziffern. Dann ist $S(2) = 110$ und $S(6) = 2562701$.

Finden Sie $S(16)$.