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; }

The official Project Euler has K only going up to 7! I'm not mad but this does feel like a significant scale up from the original question. For K = 7 I didn't need dynamic programming as much as I needed to be able to generate the # to add from each permutation, but then I'm generating every combination of digits. With 200 digits...???

Even if all digits werre 9, I know the intermediate steps max out at k* 9^2, but I guess I got to think about how to keep track of intermediate steps and combos.

Because I got frustrated with the problem, I made a dictionary of all digits whose chain of square of digits reaches 1 which can be found in this OEIS link for numbers upto 200 and then return:

print((10**k-(d[k]%MOD))%MOD)

You can also read about happy numbers on wikipedia

can anyone explain me the question what it wants.i didn't understand it

We should try to think the reverse solution. For eg. we have to get 89 using squares of numbers (1-9). Obtain 89 using 1, 4, 9, 16, 25, 36, 49, 64, 81 once or more than once. eg. 4+4+81=89 (the numbers are permutations of 2,9,2,0,0,0,0,0,0,0) use recursion and count