Summing Digits

Logic Level 4

It's common that, given a positive integer $n$ , to find the sum of its digits. For example, 2016 has digit sum 9, and 9686 has digit sum 29. This process can be iterated until we get a digit sum that has only a single digit. For example, 2016 arrives to the single-digit 9 in a single step, but 9686 takes three steps, going to 29, 11, before arriving at 2.

Let $Z(n)$ be the number of digit-sum iterations needed from $n$ to arrive to a single-digit result. For example, $Z(2016) = 1$ and $Z(9686) = 3$ .

Let $X(z)$ be the smallest positive integer $n$ such that $Z(n) = z$ . For example, $X(1) = 10$ and $X(2) = 19$ .

Find $X(4562) \bmod 6$ .

The answer is 1.

1 solution

Tran Hieu
Jan 5, 2016

We have X(2) = 19 because all number less than 19 has Z = 1 Let's A = X(3). We could easily see that S(A) = X(2) = 19, because if S(A) >19, we can reduce some of digit of A and make A' so that S(A') = 19, and A'<A, and Z(A') = 3 so A, by definition, could not be X(3).

In general, we can see that S(X(n+1)) = X(n).

Lets call X(n+1) = $\overline{a_1a_2...a_k}$ . In order to get the smallest, we will need $a_2=a_3=..=a_k=9 \text{ and } a_1 = S(X(n+1)) - 9*k = X(n)-9*k$

But we have X(2) = 19 = 9*2+1, so for X(3) we have $a_1 = 1\text{ and } k = 3, \text{ that means } X(3) = 199 = 99*2 + 1 = 9*22 + 1$

Using recursion, we can see X(n) will always have a form $\overline{19..9}$ with N > 1, so X(4562) mod 6 = 1

It almost resembles my solution, to prove your last claim, it's more solid to use the algebraic demonstration of a number. In addition, you have a slight mistake and I quote: "all number less than 19 has Z = 1", it's actually all the numbers more than or equal to 10 and less than 19.

Majed Khalaf - 5 years, 5 months ago

Thanks. That again roll back to the definition of Z, I mean for n<10 do you take its sum of digits once or just leave it that it is

Tran Hieu - 5 years, 5 months ago

We iterate the sum until we get a one-digit number, so if the number is already that, the Z would be zero, so X (1)=10

Majed Khalaf - 5 years, 5 months ago

Summing Digits

The answer is 1.

1 solution

0 pending reports