Recreational Mathematics Problem 3

Recreational Mathematics Problem 3

Science

Cookies help us deliver our Services. By using our Services or clicking I agree, you agree to our use of cookies. Learn More.

D

Joined
08 Jun 07
Moves
2120
04 Nov 14

D
Losing the Thread

Quarantined World

Joined
27 Oct 04
Moves
87415
04 Nov 14

Are you expecting me to prove that its 97 or is just spotting the way its 6N + 1 enough?

D

Joined
08 Jun 07
Moves
2120
04 Nov 14
2 edits

D
Losing the Thread

Quarantined World

Joined
27 Oct 04
Moves
87415
04 Nov 14

The post that was quoted here has been removed
I forgot to resum the digits again. In which case the answer is 4.

D

Joined
08 Jun 07
Moves
2120
04 Nov 14
2 edits

D
Losing the Thread

Quarantined World

Joined
27 Oct 04
Moves
87415
05 Nov 14
1 edit

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.

D

Joined
08 Jun 07
Moves
2120
05 Nov 14
4 edits

D

Joined
08 Jun 07
Moves
2120
05 Nov 14
1 edit