1

Here's what I know:

  • The modular inverse of 3 for the modular base of $10^9$ is 666,666,667
  • The last nine digits of $2^{120}$ is 280,344,576.
  • The product of the two exceeds $2^{32}$ (it is around $2^{57.375}$)
  • $2^{120}$ - 1 is divisible by 3, but 280,344,575 is not.

I'd appreciate some clues on how to determine the last nine digits of $(2^{120} - 1) /3$ without any intermediate value exceeding $2^{32}$

Happy Green Kid Naps
  • 199
  • $(2^{120}-1)/3$ is larger than $2^{118}$. How do you envision to produce a result that large without any intermediate value exceeding $2^{32}$? – hmakholm left over Monica Sep 18 '15 at 21:00
  • @HenningMakholm -- I indicated in subject but not in the message; I am only interested in the last nine digits of that expression. I will indicate so in the message as well. – Happy Green Kid Naps Sep 18 '15 at 21:02

3 Answers3

6

Suppose you are dividing by hand $2^{120}-1$ by $3$ by the usual algorithm: when you get to the last 9 digits, you'll have on the left the remainder carried over from the preceding division, and that remainder can be $0$, $1$ or $2$. But since we know the division is exact, the only possibility is $1$ and the answer therefore is $$1,280,344,575/3=426781525.$$

Intelligenti pauca
  • 50,470
  • 4
  • 42
  • 77
1

$3=2^2-1$, so $$ \frac{2^{120}-1}{2^2-1}=1+2^2+2^4+2^6+\cdots+2^{118}. $$ This suggests one way of achieving your goal. You can calculate the remainders of all of $2^{2n}$ modulo $10^9$ without ever needing intermediate results in excess of $4\cdot 10^9<2^{32}$. If you have already calculated the remainder $2^{2k}\equiv r_k\pmod{10^9}$, then you can calculate the next remainder $2^{2(k+1)}\equiv 4r_k\equiv r_{k+1}\pmod{10^9}$.

As the last step you just calculate the sum $r_0+r_1+\cdots+r_{59}$. Whenever you overflow $>10^9$ just subtract $10^9$ from the intermediate result.

Jyrki Lahtonen
  • 133,153
  • 1
    Well. This is obviously nowhere nearly as efficient as the other answers, because they only require you to calculate the remainder of $2^{120}$ which can be done by square-and-multiply without calculating all those intermediate remainders. – Jyrki Lahtonen Sep 18 '15 at 21:29
  • Nevertheless, it was a valid answer that met the don't exceed $2^{32}$ limit. Thank you. – Happy Green Kid Naps Sep 18 '15 at 21:55
1

$$\frac{280344575}{3} \equiv \frac{280344576}{3}-\frac13 \equiv 93448192 - 666666667 \equiv 426781525 \pmod{10^9} $$ and you can then check that $$ 426781525 \cdot 3 \equiv 280344575 \pmod{10^9} $$

hmakholm left over Monica
  • 286,031