Problem 676

Matching Digit Sums

Let $d (i, b)$ be the digit sum of the number $i$ in base $b$ . For example $d (9, 2) = 2$ , since $9 = 1001_{2}$ . When using different bases, the respective digit sums most of the time deviate from each other, for example $d (9, 4) = 3 \neq d (9, 2)$ .

However, for some numbers $i$ there will be a match, like $d (17, 4) = d (17, 2) = 2$ . Let $M (n, b_{1}, b_{2})$ be the sum of all natural numbers $i \leq n$ for which $d (i, b_{1}) = d (i, b_{2})$ . For example, $M (10, 8, 2) = 18$ , $M (100, 8, 2) = 292$ and $M (10^{6}, 8, 2) = 19173952$ .

Find $\sum_{k = 3}^{6} \sum_{l = 1}^{k - 2} M (10^{16}, 2^{k}, 2^{l})$ , giving the last $16$ digits as the answer.

相同数字和

记 $d (i, b)$ 为数 $i$ 在 $b$ 进制下的数字和。例如， $d (9, 2) = 2$ ，因为 $9 = 1001_{2}$ 。不同进制下的数字和通常是不同的，例如 $d (9, 4) = 3 \neq d (9, 2)$ 。

然而，对于某些数 $i$ ，在不同进制下的数字和可能会相同，比如 $d (17, 4) = d (17, 2) = 2$ 。记 $M (n, b_{1}, b_{2})$ 为所有满足 $i \leq n$ 且 $d (i, b_{1}) = d (i, b_{2})$ 的自然数 $i$ 之和。例如， $M (10, 8, 2) = 18$ ， $M (100, 8, 2) = 292$ ， $M (10^{6}, 8, 2) = 19173952$ 。

求 $\sum_{k = 3}^{6} \sum_{l = 1}^{k - 2} M (10^{16}, 2^{k}, 2^{l})$ ，并给出其最后 $16$ 位数字作为你的答案。