This C++ program counts how many numbers, below a given limit (10^digits), become 89 in their digit square sum chains. The algorithm uses dynamic programming to calculate the number of ways to obtain each sum in the range of 1 to digits99.

Here's a brief explanation:

becomes89 is a helper function that determines whether a number eventually becomes 89 in its digit square sum chain.

The main function initializes an array sums to store the number of ways to obtain each sum in the digit square sum chain using dynamic programming.

The program then iterates through all possible starting digits and calculates the number of ways to obtain each sum for each length of the chain using dynamic programming.

Finally, it counts how many numbers from 1 to digits99 become 89 and adds the corresponding count from the dynamic programming array.

The result is printed modulo 1000000007.

Note: This algorithm takes advantage of dynamic programming to efficiently calculate the number of ways to obtain each sum in the digit square sum chain for a given length. The modulo operation is applied throughout the calculations to prevent overflow.

include

bool becomes89(unsigned int x) { do { unsigned int squareDigitSum = 0; auto reduce = x; while (reduce > 0) { auto digit = reduce % 10; reduce /= 10; squareDigitSum += digit * digit; } if (squareDigitSum == 89) return true; if (squareDigitSum == 1) return false; x = squareDigitSum; } while (true); }

int main() { unsigned int digits = 7; // 10^7 = 10,000,000 std::cin >> digits; const unsigned int Modulo = 1000000007; unsigned int sums[200*9*9 + 1] = { 0 }; for (unsigned int first = 0; first <= 9; first++) sums[first * first]++; for (unsigned int length = 2; length <= digits; length++) for (unsigned int sum = length*9*9; sum > 0; sum--) for (unsigned int high = 1; high <= 9; high++) { auto square = high * high; if (square > sum) break; sums[sum] += sums[sum - square]; sums[sum] %= Modulo; } unsigned int count89 = 0; for (unsigned int i = 1; i <= digits*9*9; i++) if (becomes89(i)) { count89 += sums[i]; count89 %= Modulo;
}

std::cout << count89 << std::endl; return 0; }