Digit Sum

[BetonaBG]

Let N = 8765^4321 be writen in decimal notation.
If A is the sum of the digits of N and B is the sum
of the digits of A, then what is the sum of the
digits of B?


:confused: :confused: :confused:


Have Fun.

[mossoi]

Do you mean let N = 8765 X 10^4321?

8765^4321 is ridiculously big and makes the question unworkable, whereas A and B are straightforward to work out if N = 8765 x 10^4321 and one understands scientific notation.

[BetonaBG]

No, I mean what I said,


N = 8765^4321



[15 times Editing] Yeah, question is pain for me last 2 days

[mossoi]

Fair enough, my mistake - I approached this question as though it was demonstrating scientific notation to make a point to grade school students. If it's 8765^4321 then I haven't a clue on the methods to use.

Out of interest where is this question from?

[BetonaBG]

Its given from two of the professors in San Jose State University.

There is a whole sequence going on for the last 2 years, I'll try to find
old problems and give you a link if you are interest.

[mossoi]

I would be interested. As far as I can see, with my basic knowledge of maths, the solution will only be found by crunching huge numbers (possibly using a computer program). Unless there is a technique for this sort of thing which then takes the whole thing over my head. :(

[BetonaBG]

I found a formula that might help out but I don't understand even the example

http://www.cut-the-knot.org/Curriculum/Arithmetic/PowerOfDigits.shtml

[mossoi]

Me neither. I'm ok up to the second paragraph but after that...

[Callipygous]

Let N = 8765^4321 be writen in decimal notation.
If A is the sum of the digits of N and B is the sum
of the digits of A, then what is the sum of the
digits of B?


:confused: :confused: :confused:


Have Fun.

C

[BetonaBG]

C



:eek:



btw I found a way to prove that its between 2 and 9.

But that still no good :(

[mossoi]

That seems rather low considering the value of N or have I got the wrong end of the stick here?

If we say N = 8765^2 what value for the sum of the digits of B do you get?

[mossoi]

LOL. Just plugged some numbers into a PHP page and it bails out after 8765^78.

[Callipygous]

That seems rather low considering the value of N or have I got the wrong end of the stick here?

If we say N = 8765^2 what value for the sum of the digits of B do you get?

a=37
b=10
"C"= 1

so if you think about it c=2 could mean a great many things. b could be 11 or 20, a could be 29 or twenty 1's followed by an infinite number of 0's.

[mossoi]

but to return a number between 2 and 9 there would have to be a LOT of 0's in the decimal notation of 8765^4321, A or B.

Consider that 8765^78 = 3.42491497 × 10^307. That's a whole lot of digits if it's written out in decimal notation and without rounding and that's only a fraction of N.

[dave]

I think the idea is to use mathematical methods and bypass the actual calculation part.

[BetonaBG]

Well, my idea about proving that its between 2 and 9 looks like this:

(Note) Totally wrong from the right method to start the problem:

8765^2 = 8 digit number

so in the worst case 8765^4321 = will give us 4*4321 (17284) digit number:

Consider all those digit being 9s (Max) and 1s(min) I discard the case one 1 and lots 0s, just because 8765^4321 doesn't seem like having many 0s.

17284*1 min <= Sum <= max = 17284*9
17284 <= Sum <= 155556 (but we get Max and Min digit sum from)
A: 20000 <= SUm <= 99999
B: 2 <= B <= 45 (digit sum) (39)
C: 2 <= C <= 12 (digit worst case) (9)

C 2<= C <= 9



I don't know if even half of this is correct (I doubt it), so pls find some new approach :p

And yeah, Dave is right, we don't look to calcutate the number but to get the sum

[haggy]

C = 8. Merely calculated using Mathematica.

Haven't had a chance to check for more general cases yet.

[haggy]

Let S(x) = Sum of the digits of x

Thm: S(x) = x mod 9 (more generally Sb(x) = x mod (b-1) if we are working in base b)

S(8765^4321) = 8765^4321 mod 9
= 8^4321 mod 9

8^2 = 64 = 1 mod 9

Therefore

S(8765^4321) = (8^1)*(8^2)^2160 mod 9
= 8 * (1^2160) mod 9
= 8 mod 9
Thought this might help a bit. :-)

[mossoi]

Finding "C" by calculating the number was never going to happen, I was just thinking around the whole thing to get some idea of the values we are looking at.

Sadly I don't understand the various proofs in this thread but I'm still not convinced how 2 <= C <= 9 when the number of digits in N is so great.

[Callipygous]

Well, my idea about proving that its between 2 and 9 looks like this:

(Note) Totally wrong from the right method to start the problem:

8765^2 = 8 digit number

so in the worst case 8765^4321 = will give us 4*4321 (17284) digit number:

Consider all those digit being 9s (Max) and 1s(min) I discard the case one 1 and lots 0s, just because 8765^4321 doesn't seem like having many 0s.

17284*1 min <= Sum <= max = 17284*9
17284 <= Sum <= 155556 (but we get Max and Min digit sum from)
A: 20000 <= SUm <= 99999
B: 2 <= B <= 45 (digit sum) (39)
C: 2 <= C <= 12 (digit worst case) (9)

C 2<= C <= 9



I don't know if even half of this is correct (I doubt it), so pls find some new approach :p

And yeah, Dave is right, we don't look to calcutate the number but to get the sum


there can be zeros :P but it is unlikely that you would get a lower number than if it were all 1's

[BetonaBG]

Let S(x) = Sum of the digits of x

Thm: S(x) = x mod 9 (more generally Sb(x) = x mod (b-1) if we are working in base b)


Following this...


S(8765^4321) = 8765^4321 mod 9
= 8^4321 mod 9


if mod 9, this mean that the base (b-1) = 9 =>> b = 10

I don't see base 10 anywhere, or is it something else?

And can you explain what do you mean by base? :-(

[BetonaBG]

Sadly I don't understand the various proofs in this thread but I'm still not convinced how 2 <= C <= 9 when the number of digits in N is so great.


Yeah digits in N are a lot, but C is the Sum of the Sum of the Sum from the digits in N).


Ex:
[][][]
N = 23523525236235386529783562789364928374 => Sum 4833 = A
A = 4833 => Sum = 18 = B
B = 18 => Sum = 9 = C

C = 9
[][][]

[mossoi]

Understood, but in the question N is magnitudes greater than the example used.

[haggy]

Following this...
if mod 9, this mean that the base (b-1) = 9 =>> b = 10

I don't see base 10 anywhere, or is it something else?

And can you explain what do you mean by base? :-(

We're working in the decimal system aka base 10.

E.g. 156 = 1*10^2 + 5*10^1 + 6 * 10^0
So if we look at S(156),
S(156) = 1+5+6 = 2 mod 9
Now
156 = 1*10^2 + 5*10^1 + 6 * 10^0 = 1*1^2 + 5*1^1 + 6 * 1^0 mod 9
= 1 + 5 + 6 mod 9
The reasoning here can be used to prove a more general theorem/lemma.


Concerning the number of digits of C:
The number of digits of 8765^4321 is approx Log10[8765^4321] ie 17036
The sum of those digits is at most 9*17036 = 153324 ....A
Now the sum of the digits of a 6 digit number is at most 6*9 = 54 ....B

This sum, B, along the same reasoning as before, has to be = 8 mod 9
i.e. B is in {8,17,26,35,44,53}
The sum of the digits of each of these is 8. Thus C = 8

[wk4bd]

Let S(x) = Sum of the digits of x

Thm: S(x) = x mod 9 (more generally Sb(x) = x mod (b-1) if we are working in base b)

S(8765^4321) = 8765^4321 mod 9
= 8^4321 mod 9

8^2 = 64 = 1 mod 9

Therefore

S(8765^4321) = (8^1)*(8^2)^2160 mod 9
= 8 * (1^2160) mod 9
= 8 mod 9
Thought this might help a bit. :-)


This is very useful. Can you explain why 8765^4321 mod 9 = 8^4321 mod 9?
Although I know 8765 mod 9 = 8.

Similarily, why 8^2160 mod 9 = 8?

[haggy]

This is very useful. Can you explain why 8765^4321 mod 9 = 8^4321 mod 9?
Although I know 8765 mod 9 = 8.

It's just the basic rules of modular arithmetic. Google "modular arithmetic".
Remember, I'm using the "=" sign instead of the congruence sign. It's just quicker to type =.

Similarily, why 8^2160 mod 9 = 8?
I didn't say that. I said:
8^2 = 64 = 1 mod 9
Therefore,
(8^2)^2160 = (1)^2160 mod 9

[wk4bd]

I got it now, thank you. actually 8 mod 9=-1,

[Callipygous]

8 mod 9 should be 8.

[Primarygun]

When will the mod be taughted to us?
I learnt it myself.

[dave]

It's not something you'll find outside university level (normally). I've only just started it properly at the end of last year (in the 1st year of my maths degree), and that was nothing but a cursory glance. If you do a degree that involves quite a lot of maths (Physics, Computer Science, etc) you'll get a maths course in the first year that will probably have some kind of introduction to modular arithmetic.

[Primarygun]

Is engineering more interested than science?