# Recreational Mathematics Problem 3

Duchess64
Science 04 Nov '14 20:24
1. 04 Nov '14 20:24
Here's one that seems easier than the previous problem that I posted.

Let A be the sum of digits in decimal representation of 16^16 and B
be the sum of digits of A. What is C = the sum of digits of B?
Requirement: You may *not* do a 'brute-force' calculation of 16^16.
I prefer that you do *not* use logarithms to do a close estimate of 16^16.

Advice: This problem requires little particular knowledge of mathematics.
Once you get the key insight, it should be fairly straightforward to work out.
Good luck, as usual, to everyone who makes an honest effort to solve it.
2. DeepThought
04 Nov '14 22:02
Are you expecting me to prove that its 97 or is just spotting the way its 6N + 1 enough?
3. 04 Nov '14 22:392 edits
Originally posted by DeepThought
Are you expecting me to prove that its 97 or is just spotting the way its 6N + 1 enough?
Just in case it's unclear, 16^16 means '16 raised to the 16th power'.
I really don't know what you mean by '6N + 1'; what's N?
So you should show me why you think C (sum of digits of B) = 97.
(I am not saying that it's necessarily correct.)
4. DeepThought
04 Nov '14 23:04
Originally posted by Duchess64
Just in case it's unclear, 16^16 means '16 raised to the 16th power'.
I really don't know what you mean by '6N + 1'; what's N?
So you should show me why you think C (sum of digits of B) = 97.
(I am not saying that it's necessarily correct.)
I forgot to resum the digits again. In which case the answer is 4.
5. 04 Nov '14 23:192 edits
Originally posted by DeepThought
I forgot to resum the digits again. In which case the answer is 4.
That's wrong. Could you please explain why you think C = 4?
I don't think you were just guessing, but without evidence of your thinking,
there's no way to be certain that you were not just guessing.
6. DeepThought
05 Nov '14 01:261 edit
Originally posted by Duchess64
That's wrong. Could you please explain why you think C = 4?
I don't think you were just guessing, but without evidence of your thinking,
there's no way to be certain that you were not just guessing.
That was due to carelessness. I should have written 97 --> 9 + 7 = 16 --> 1 + 6 = 7. Earlier on I didn't realise that you wanted the digits resummed. Between my earlier semi-guess, which was empirical and now I know how to do the problem rigorously. First what I did earlier:

number, sum of digits, iterated sum
1 : sum = 1 : iterated sum = 1
16 : sum = 7 : iterated sum = 7
256 : sum = 13 : iterated sum = 4
4096 : sum = 19 : iterated sum = 1
65536 : sum = 25 : iterated sum = 7
1048576 : sum = 31 : iterated sum = 4
16777216 : sum = 37 : iterated sum = 1

From which I inferred that the first sum of digits was given by 6N + 1. I can't prove this yet, but it's consistent with what I can prove. I can prove the cycles 1, 7, 4 etc.

suppose a, b, and c are integers, a%c means a modulo c and:
a = mc + x, x < c
b = nc + y, y < c
x,y,m,n all integer, then
A) (a + b)%c = ((m + n)c + x + y)%c = (x + y)%c = (mc + x + y)%c = (a + b%c)%c
and
B) (ab)%c = (mnc² + (my + nx)c + xy)%c = (xy)%c = (myc + xy)%c = (ay)%c = (a(b%c))%c

Now, suppose a has digits a(0), a(1), a(2), ···, a(N) with

a = a(0) + a(1)*10 + ··· + a(N)*10^N
|b| is the integer part of b so |3/2| = 1

a/9 = |a(N)/9|*10^N + (a(N)%9)*10^N + a(N-1)/9 * 10^(N - 1) + ··· + a(0)/9
a/9 = |a(N)/9|*10^N + |(10*(a(N)%10) + a(N-1))/9|*10^(N - 1) + (a(N)%9 + a(N-1))%9 + ···
Using result A we have:
a/9 = |a(N)/9|*10^N + |(10*(a(N)%10) + a(N-1))/9|*10^(N - 1) + (a(N) + a(N - 1))%9 + ···
repeating this process eventually yields:
a/9 = |a/9| + (a(0) + a(1) + ··· + a(N))%9

=> a%9 = (a(0) + a(1) + ··· + a(N))%9

In other words the sum of the digits of any number mod 9 is the same as the number mod 9. Someone pointed this out to me. I worked out the proof (which is a rehash of the normal algorithm for division). Iteratively summing the digits of 16^16 would eventually give (16^16)%9.

16^16 = 2^64 ~ 4E18 so the largest possible answer for the sum of digits is 19*9 = 171. The largest sum of any three digit number is 27 and the largest possible sums are 1 + 6 + 9 = 16 and 9 + 9 = 18, so we can be sure that the sum of digits of the sum of digits of the sum of digits will only have one digit.

Now, using B we have:
16^0 %9 = 1
16^1 %9 = 7
16^2 %9 = (16*(16%9))%9 = (16*7)%9 = 112%9 = 4
16^3 %9 = (16*(16^2))%9 = (16*4)%9 = 64%9 = 1
so:
(16^(3N))%9 = 1
(16^(3N + 1))%9 = 7
(16^(3N + 2))%9 = 4

16%3 = 1 so the answer is 7. My empirical formula for the sum of the digits of 16^16 (6N + 1) gives 97, 97%9 = 7.
7. 05 Nov '14 02:224 edits
Originally posted by DeepThought
That was due to carelessness. I should have written 97 --> 9 + 7 = 16 --> 1 + 6 = 7. Earlier on I didn't realise that you wanted the digits resummed. Between my earlier semi-guess, which was empirical and now I know how to do the problem rigorously. First what I did earlier:

number, sum of digits, iterated sum
1 : sum = 1 : iterated sum = 1
16 ...[text shortened]... swer is 7. My empirical formula for the sum of the digits of 16^16 (6N + 1) gives 97, 97%9 = 7.
It's correct that C = 7.

I think that I stated the problem clearly enough. I wonder why you keep
introducing expressions such as '6N+1' as though I could read your mind.
Your style of exposition leaves something to be desired in my view.

I have to say that you seem to prefer a more or less 'brute-force' approach
to these problems, resulting in unnecessary complications, and sometimes
(though not so much in this case) relying on knowledge or techniques that
seem beyond the scope of elementary mathematics.

Here's how I solved this problem (explaining my reasoning):
First of all, it's vital to understand a relationship between a natural number and
the sum of its digits in decimal representation. The key insight (which I had
assumed is widely known) is that if A is the sum of B's digits, then A = B (mod 9).
Let the digits (from right to left) of B be b0, b1, b2 ... bn.
A = b0 + b1 + b2 + ... + bn. B = b0 + b1(10) + b2(10)^2 + ... + bn(10)^n
So B - A = b1(9) + b2(99) + ... bn(999...) = 0 (mod 9)
Since B - A = 0 (mod 9), A = B (mod 9) (which is trivially true yet useful)

So 16^16 = A = B = C (mod 9), which gives us much information.
16^16 = 2^64 = (2^60) x (2^4) = (2^6)^10 x (2^4)
2^6 = 64 = 1 (mod 9) so 16^16 = 2^4 (mod 9)
C = 7 (mod 9) (i.e. C = 7 + 9K for some K >= 0)

Now we seek an upper bound on C by first seeking upper bounds for A and B.
I asked people not to use logarithms to estimate 16^16. If one ignores that,
knowing log 2 ~ 0.301, one could estimate 16^16=2^64 as around 10^19
so 16^16 would have at most 20 digits and A <= 20 x 9 = 180.
(This is a 'brute-force' approach similar to the one that you used.)

Yet it's unnecessary to cut the cloth so fine. 16^16 < 100^16 = 10^32.
So 16^16 has at most 32 digits and A <= 32 x 9 = 288.
Then B <= 19 (e.g. in the case that A=199) and C <= 10.
C = 7 (mod 9), so C = 7.
8. 05 Nov '14 20:531 edit
Originally posted by DeepThought
That was due to carelessness. I should have written 97 --> 9 + 7 = 16 --> 1 + 6 = 7. Earlier on I didn't realise that you wanted the digits resummed. Between my earlier semi-guess, which was empirical and now I know how to do the problem rigorously. First what I did earlier:

number, sum of digits, iterated sum
1 : sum = 1 : iterated sum = 1
16 ...[text shortened]... swer is 7. My empirical formula for the sum of the digits of 16^16 (6N + 1) gives 97, 97%9 = 7.
"16^16 = 2^64 ~ 4E18 so the largest possible answer for the sum of digits is 19*9 = 171."
--DeepThought

Your conclusion that 16^16 has at most 19 digits (= n x 10^18) is not quite correct.
16^16 has 20 digits (~ 1.8 x 10^19), so (without calculating the exact
value of 16^16) you cannot be certain that its digits' sum is <= 171.