Count the number of numbers x having a digital sum equal to the sum of the digits x * m

Question

I tried to solve the following problem, but I was stuck. I think this is a dynamic programming problem. Could you give some ideas?

Problem:

Given a positive number n (n <= 18) and a positive number m (m <= 100). The call S (x) is the sum of the digits x. For example, S (123) = 6 Count the number of an integer x that has n digits, and S (x) = S (x * m)

Example:

n = 1, m = 2 result = 2

n = 18, m = 1 result = 1000000000000000000

Thanks in advance.

Answer 1

First, we need to come up with a recursive formula:

Starting from the least significant digit (LSD) to the most significant digit (MSD), we have the right solution if, after calculating the MSD, we have S(x) = S(x*m)

To check if a number is a valid solution, we need to know three things:

• What is the current sum of the digit S (x)
• What is the current sum of the digit S (x * m)
• What is the current number.

So, to answer the first and last, it’s easy, we just need to support two parameters sum and digit . To calculate the second, we need to save two additional parameters: sumOfProduct and lastRemaining .

• sumOfProduct - current S (x * m)
• lastRemaining is the result (m * current digit value + lastRemaining) / 10

For example, we have x = 123 and m = 23

• First digit = 3

   sum = 3 digit = 0 sumOfProduct += (lastRemaining + 3*m) % 10 = 9 lastRemaining = (m*3 + 0)/10 = 6 

• Second digit = 2

   sum = 5 digit = 1 sumOfProduct += (lastRemaining + 2*m) % 10 = 11 lastRemaining = (m*2 + lastRemaining)/10 = 5 

• Last digit = 1

   sum = 6 digit = 2 sumOfProduct += (lastRemaining + m) % 10 = 19 lastRemaining = (m + lastRemaining)/10 = 2 

  Since this is the last digit, sumOfProduct += S(lastRemaining) = 21 .

So x = 123 and m = 23 are not a valid number. Check x*m = 2829 -> S(x*m) = S(2829) = 21 .

So, we can have a recursive formula with state (digit, sum, sumOfProdut, lastRemaining) .

Thus, our dynamic programming state is dp[18][18*9 + 1][18*9 + 1][200] (as m <= 100, so lastRemaining not more than 200).

Now the dp state exceeds 300 MB, but if we use an iterative approach, it will become smaller using about 30 MB

Answer 2

This problem can be calculated directly.

From these documents: 1 , 2 , and 3 (thanks @LouisRicci for finding them), we can specify

• The repeating cycle of the sum of the digits of the multiplication begins to repeat on the last digit, but one of the base numbers (9 for base-10)

• S(x) can be defined as: let a be equal to x mod 9 , if a is zero, take 9 as the result, otherwise take a . You can play it in the ES6 snippet below:

 IN.oninput= (_=> OUT.value= (IN.value % 9) || 9); IN.oninput(); 

 Input x:<br> <input id=IN value=123><br> S(x):<br> <input id=OUT disabled> 

3. Multiplication rule: S(x * y) = S(S(x) * S(y)) .

4. S(x) and S(x*m) will always be true for x=0 , so there is no null result.

   ---

Based on the above statements, we must calculate the repeating cycle of the sum of the multiplication digits for S(m) :

 int m = 88; int Sm = S(m); // 7 int true_n_times_in_nine = 0; for (int i=1; i<=9; i++) { true_n_times_in_nine += i == S(i * Sm); } 

Then answer:

 result = ((pow(10, n) / 9) * true_n_times_in_nine); 

Plus one due to zero:

 result++; 

Here is the ES6 solution:

 S= x=> (x % 9) || 9; TrueIn9= (m, Sm=S(m))=> [1,2,3,4,5,6,7,8,9].filter(i=> i==S(i*Sm)).length; F= (n,m)=> ~~(eval('1e'+n)/9) * TrueIn9(m) + 1; N.oninput= M.oninput= f=(_=> OUT.value= F(N.value | 0, M.value | 0)); f(); 

 Input n: (number of digits)<br> <input id=N value=1><br> Input m: (multiplicative number)<br> <input id=M value=2><br> F(n,m):<br> <input id=OUT disabled><br>