Power of 2 - Part 2

Number Theory Level 4

Let the remainder when $2^{7,812,530}$ is divided by $10,000,000,000$ be $N$ . Find the digit sum of $N$ .

$Notes$ $and$ $Assumptions:$ The digit sum of a number is the sum of the number's digits. For instance, $2014$ has a digit sum of $7$ because $2+0+1+4=7$

The answer is 37.

1 solution

Yash Bansal
Mar 9, 2014

I did it using programming. (a b) mod c=((a mod c) (b mod c)) mod c.

Here, put 'b' as 2 and 'c' as 1,000,000,000. compute 'a' iteratively by multiplying it by 2.

Note : It requires 64 bit integers to process the value of 'c'

Took 0.251 s on Codeblocks C++ to get the answer : 1073741824

Alter : Do on Wolfram!.

What is the mathematical approach?

Nanayaranaraknas Vahdam - 7 years, 2 months ago

good

shyamol sarkar - 7 years, 3 months ago

solved it manually... 10,000,000,000= 2^10*5^10.... made the numerator and denominator co-prime by cancelling 2^10

that leaves us with 2^7812520/5^10

5^10 has a cycle of ==5^10(1-1/5)=4 5^9=100 5^7=7812500

used this cycle to divide power of 2 that is 7812520
after dividing that the extra or remainder of 7812520 by cycle (7812500) which is 20

is the equivalent power of 2

i.e 2^20 is remainder out of 5^10

but 5^10 was not the initial denominator so we need to multiply back 2^10 in both numerator and denominator to get the original denominator back.

that leaves us with a remainder of 2^20*2^10=2^30 out of 10,000,000,000

which is (2^10)^3=(1024)^3=1073741824 digit sum of (1073741824)=37

hitesh hitesh - 7 years, 1 month ago

I don't understand about the cycle

Aloysius Ng - 7 years ago

Power of 2 - Part 2

The answer is 37.

1 solution

0 pending reports