Results 1 to 11 of 11

Math Help - Sum of digits

  1. #1
    Super Member malaygoel's Avatar
    Joined
    May 2006
    From
    India
    Posts
    648

    Sum of digits

    The sum of 2^{1000} is written and the sum of the digits of this number is written and the process is repeated a number of times, till a one digit number is obtained. What is this one digit number?

    Keep Smiling
    Malay
    Last edited by malaygoel; July 17th 2006 at 02:38 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,547
    Thanks
    539
    Hello, Malay!

    The sum of 2^{1000} is written and the sum of the digits of this number is written
    and the process is repeated until a one-digit number is obtained.
    What is this one-digit number?

    The sum-of-digits means we are dealing with "digital roots"
    . . . . . that the numbers are reduced modulo-9.

    We can reduce the products as we work, rather than waiting until the final product.


    Since 2^{20} \:= \:1,048,576 \:\equiv \:2^2\pmod 9

    . . then: N \:= \:2^{1000} \:= \:\left(2^{20}\right)^{50} \:\equiv\:\left(2^2\right)^{50}\pmod{9}

    Hence: . N \:\equiv \:2^{100} \:= \:\left(2^{20}\right)^5 \:\equiv\;(2^2)^5\pmod{9}

    Therefore: . N\:\equiv\:2^{10} \:=\:1024\:\equiv\:7\pmod{9}

    The one-digit number is \boxed{7}

    ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

    An alternate solution . . .

    Consider the digit roots of consecutive powers of 2.

    . . . \begin{array}{ccccccc}2^1 \equiv 2 \\ 2^2\equiv 4 \\ 2^3 \equiv 8 \\ 2^4 \equiv 7 \\ 2^5 \equiv 5 \\ 2^6 \equiv 1 \\ \vdots\end{array}

    The digits roots have a six-digit cycle: 2-4-8-7-5-1.


    Since 2000 \div 6\:=\:166,\;rem\;4
    . . the digit root of 2^{1000} is the fourth one: \boxed{7}

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member malaygoel's Avatar
    Joined
    May 2006
    From
    India
    Posts
    648
    but why have you found modulo 9?

    Keep Smiling
    Malay
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,547
    Thanks
    539
    Hello, Malay!

    but why have you found modulo 9?

    It's a bit tricky to explain . . . Given a positive integer N,
    it turns out that N is equivalent to the sum of its digits, modulo 9.

    If N = abc\hdots n, then: . N \,\equiv \,(a+b+c+\hdots+n) \pmod{9}


    Let's see if I can devise a proof for this . . .


    Let N\:=\:10^na + 10^{n-1}b + 10^{n-2}c + \hdots + 10m + n

    . . 10^na - a + a) + (10^{n-1}b - b + b) + (10^{n-2}c - c + c)" alt="= \10^na - a + a) + (10^{n-1}b - b + b) + (10^{n-2}c - c + c)" />  + \hdots + (10m - m + m) + n

    . . 10^n - 1)a + a+ (10^{n-1}-1)b + b + (10^{n-2}-1)c + c" alt="=\10^n - 1)a + a+ (10^{n-1}-1)b + b + (10^{n-2}-1)c + c" />  + \hdots + (10 - 1)m + m + n

    . . = \:\underbrace{(10^n-1)a + (10^{n-1} -1)b + (10^{n-2} - 1)c + \hdots + (10 - 1)m} \,+\,(a + b + c + \hdots + m + n)
    . . . . . . . . . . . . This expression is a multiple of 9 *


    Therefore: . a + b + c + \hdots +n)\pmod{9}" alt="N \:\equiv \a + b + c + \hdots +n)\pmod{9}" />

    ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

    * 10^k - 1 is of the form: . 999\hdots9 (k 9's)

    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member malaygoel's Avatar
    Joined
    May 2006
    From
    India
    Posts
    648
    Quote Originally Posted by Soroban
    Hello, Malay!


    It's a bit tricky to explain . . . Given a positive integer N,
    it turns out that N is equivalent to the sum of its digits, modulo 9.

    If N = abc\hdots n, then: . N \,\equiv \,(a+b+c+\hdots+n) \pmod{9}


    Let's see if I can devise a proof for this . . .


    Let N\:=\:10^na + 10^{n-1}b + 10^{n-2}c + \hdots + 10m + n

    . . 10^na - a + a) + (10^{n-1}b - b + b) + (10^{n-2}c - c + c)" alt="= \10^na - a + a) + (10^{n-1}b - b + b) + (10^{n-2}c - c + c)" />  + \hdots + (10m - m + m) + n

    . . 10^n - 1)a + a+ (10^{n-1}-1)b + b + (10^{n-2}-1)c + c" alt="=\10^n - 1)a + a+ (10^{n-1}-1)b + b + (10^{n-2}-1)c + c" />  + \hdots + (10 - 1)m + m + n

    . . = \:\underbrace{(10^n-1)a + (10^{n-1} -1)b + (10^{n-2} - 1)c + \hdots + (10 - 1)m} \,+\,(a + b + c + \hdots + m + n)
    . . . . . . . . . . . . This expression is a multiple of 9 *


    Therefore: . a + b + c + \hdots +n)\pmod{9}" alt="N \:\equiv \a + b + c + \hdots +n)\pmod{9}" />

    ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

    * 10^k - 1 is of the form: . 999\hdots9 (k 9's)

    Ok.
    Let 2^{1000}is N. It contains n digits. You have found the sum of digits of n(equal to a+b+c+d+....+n)
    But how will you find a+b+c+d+..+n so than we can proceed to the next step.

    Malay
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,547
    Thanks
    539
    Hello, Malay!

    Ok.
    Let 2^{1000} = N . . . It contains n digits.
    You have found the sum of digits of N:\; a+b+c+d+....+n.

    But how will you find a+b+c+d+..+n so that we can proceed to the next step?

    We don't need that sum . . . We can work with smaller quantities.

    If X \equiv a\!\!\pmod{9} and Y \equiv b\!\!\pmod{9}, then XY \equiv ab\!\!\pmod{9}


    Since 2^{10} \,= \,1,024 \,\equiv \,7\!\!\!\pmod{9}
    . . then: . 2^{10})(2^{10}) \:\equiv \:7\cdot7 \:\equiv\:49 \:\equiv\:4\!\!\!\pmod{9} " alt="2^{20}\:=\2^{10})(2^{10}) \:\equiv \:7\cdot7 \:\equiv\:49 \:\equiv\:4\!\!\!\pmod{9} " />

    And from there, we can work our way up to 2^{1000}
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member malaygoel's Avatar
    Joined
    May 2006
    From
    India
    Posts
    648
    I think I was not clear in my last post.
    Suppose we have a number 256784 which is congruent to 5 modulo 9.
    You showed that it is congruent to 2+5+6+7+8+4 modulo 9
    now, what will be the next step

    Malay
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,547
    Thanks
    539
    Hello again, Malay!

    I hope I can finally make this clear . . .

    We don't need the product to find its digital root.


    Your thoughts seem to be along this tline:

    Consider 7^9 and add its digits.
    If the sum is greater than 9, add the digits again.
    Continue until you get a one-digit number.

    Grabbing our calculator: 7^9 \,= \,40,353,607
    Then:  4 + 0 + 3 + 5 + 3 + 6 + 0 + 7 \,= \,28\quad\Rightarrow\quad2 + 8 \,= 10\quad\Rightarrow\quad 1 + 0 \,= \,1


    But we can get the final digit without expanding 7^9.

    We have: . \begin{array}{cccc}7 \equiv 7\text{ (mod 9)} \\ 7^2 = 49 \equiv 4\text{ (mod 9)} \\ 7^3 = 343 \equiv 1\text{ (mod 9)}\\ \vdots\end{array}

    Since 7^3 \equiv 1\text{ (mod 9)}:\;\;(7^3)(7^3)(7^3) \equiv 1\cdot1\cdot1\text{ (mod 9)}

    So we have: . 7^9 \equiv 1\text{ (mod 9)} . . . see?


    The original problem was 2^{1000}.
    We will never see that number ... nor be able to add its digits ... ever!
    . . (It begins 10,715,086... and has 302 digits.)

    So we begin with, say, 2^{20} \equiv 4\text{ (mod 9)}, and create an expression with 2^{1000}.

    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor Quick's Avatar
    Joined
    May 2006
    From
    New England
    Posts
    1,024
    what is modulo 9?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    This comes from the old "casting out nines" technique.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member malaygoel's Avatar
    Joined
    May 2006
    From
    India
    Posts
    648
    Quote Originally Posted by Soroban
    Hello again, Malay!

    I hope I can finally make this clear . . .

    We don't need the product to find its digital root.


    Your thoughts seem to be along this tline:

    Consider 7^9 and add its digits.
    If the sum is greater than 9, add the digits again.
    Continue until you get a one-digit number.

    Grabbing our calculator: 7^9 \,= \,40,353,607
    Then:  4 + 0 + 3 + 5 + 3 + 6 + 0 + 7 \,= \,28\quad\Rightarrow\quad2 + 8 \,= 10\quad\Rightarrow\quad 1 + 0 \,= \,1


    But we can get the final digit without expanding 7^9.

    We have: . \begin{array}{cccc}7 \equiv 7\text{ (mod 9)} \\ 7^2 = 49 \equiv 4\text{ (mod 9)} \\ 7^3 = 343 \equiv 1\text{ (mod 9)}\\ \vdots\end{array}

    Since 7^3 \equiv 1\text{ (mod 9)}:\;\;(7^3)(7^3)(7^3) \equiv 1\cdot1\cdot1\text{ (mod 9)}

    So we have: . 7^9 \equiv 1\text{ (mod 9)} . . . see?


    The original problem was 2^{1000}.
    We will never see that number ... nor be able to add its digits ... ever!
    . . (It begins 10,715,086... and has 302 digits.)

    So we begin with, say, 2^{20} \equiv 4\text{ (mod 9)}, and create an expression with 2^{1000}.

    I have no doubt in your method. I am pretty sure it works. The only thing I want to know why it works?(As galactus pointed out 'casting out nines' was taught to us in schools, we used it to get lucky number by procesing the same way on date of birth).
    I just got. There was some misunderstanding.

    Thanks

    Keep Smiling
    Malay
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. How many digits?
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: April 19th 2011, 11:51 AM
  2. Replies: 7
    Last Post: November 28th 2010, 09:22 PM
  3. Digits
    Posted in the Algebra Forum
    Replies: 2
    Last Post: March 23rd 2010, 05:11 AM
  4. Sum of the digits
    Posted in the Algebra Forum
    Replies: 1
    Last Post: April 7th 2008, 03:50 AM
  5. Replies: 2
    Last Post: April 3rd 2007, 12:31 PM

Search Tags


/mathhelpforum @mathhelpforum