Recreational Mathematics Problem 3

The post that was quoted here has been removed

I forgot to resum the digits again. In which case the answer is 4.

The post that was quoted here has been removed

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.