Digits in Squares

Define $m = M(n, d)$ to be the smallest positive integer such that when $m^2$ is written in base $n$ it includes the base $n$ digit $d$. For example, $M(10,7) = 24$ because if all the squares are written out in base 10 the first time the digit 7 occurs is in $24^2 = 576$. $M(11,10) = 19$ as $19^2 = 361=2A9_{11}$.

Find $\displaystyle \sum_{d = 1}^{10^5}M(p, p – d)$ where $p = 10^9 + 7$.

This is a very interesting problem on number theory involving the concept of number bases. To solve this problem, we need to understand the logic and properties of the expressions mentioned before we can arrive at a solution.

Here it’s important to know that to minimize M(n, d), we need to make sure that the lower place values in the base n representation of m^2 contains the digit d.

For 1 ≤ d ≤ p – 1, it is easy to see that M(p, p – d) = d, because for positive integer m, m^2 equals to p*(m^2 / p). In base p, this expression suggests that m^2 ends with m^2 / p in base p. When d ≤ m, m^2 / p = d / p ≤ 0.1_p, thus the last digit of m^2 written in base p is d.

For p – d = 0, M(p, 0) equals to the smallest m such that the result of IntegerPart[m^2 / p] is not 0. By performing the inequality m^2 > p and taking sqrt of the inequality, we can know that M(p, 0) = ceil (sqrt(p)).

So, as per question, the sum equals to

∑[from d=1 to 10^5] M(10^9 + 7, 10^9 + 7 – d) = ∑[from d=p-10^5 to p-1] d + ceil(sqrt(10^9 + 7)).

Evaluate this expression, we have,
= ∑[from d=p-10^5 to p-1] d + sqrt(10^9 + 7) + 1
= (10^5 * (2*p – 10^5 + 1) / 2) + sqrt(10^9 + 7) * 10^5 + 10^5
= (10^5 * (2*10^9 + 6) / 2) + sqrt(10^9 + 7) * 10^5 + 10^5

You can calculate this expression for the numerical answer.

More Answers: