- 04 Nov '14 20:24Here'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. - 04 Nov '14 22:39 / 2 edits

Just in case it's unclear, 16^16 means '16 raised to the 16th power'.*Originally posted by DeepThought***Are you expecting me to prove that its 97 or is just spotting the way its 6N + 1 enough?**

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.) - 04 Nov '14 23:04

I forgot to resum the digits again. In which case the answer is 4.*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.) - 04 Nov '14 23:19 / 2 edits

That's wrong. Could you please explain why you think C = 4?*Originally posted by DeepThought***I forgot to resum the digits again. In which case the answer is 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. - 05 Nov '14 01:26 / 1 edit

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:*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.

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. - 05 Nov '14 02:22 / 4 edits

It's correct that C = 7.*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.

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. - 05 Nov '14 20:53 / 1 edit

"16^16 = 2^64 ~ 4E18 so the largest possible answer for the sum of digits is 19*9 = 171."*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.

--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.