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 \ne 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 \le 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 $\displaystyle \sum_{k=3}^6 \sum_{l=1}^{k-2}M(10^{16},2^k,2^l)$, giving the last $16$ digits as the answer.

To solve this problem, we can iterate through all possible values of $i$ from 1 to $n$ and calculate the digit sum of $i$ in base $b_1$ and base $b_2$. If the digit sums are equal, we add $i$ to our result.

In the code below, we define a helper function `digit_sum` that calculates the digit sum of a number in a given base. Using this function, we iterate through all numbers from 1 to $n$, calculate their digit sums in base $b_1$ and base $b_2$, and add them to our result if they are equal.

“`python
def digit_sum(number, base):
# Calculate the digit sum of a number in a given base
sum = 0
while number != 0:
sum += number % base
number //= base
return sum

def M(n, b1, b2):
result = 0
for i in range(1, n+1):
if digit_sum(i, b1) == digit_sum(i, b2):
result += i
return result

sum_M = 0
for k in range(3, 7):
for l in range(1, k-1):
sum_M += M(10**16, 2**k, 2**l)

last_16_digits = sum_M % 10**16
print(last_16_digits)
“`

The code calculates the sum of $M(n, b_1, b_2)$ for each combination of $k$ and $l$ within the specified ranges. Finally, it calculates the last 16 digits by taking the modulo of the result with $10^{16}$.

Please note that solving this problem with $n = 10^{16}$ may take a significant amount of time due to the large number of iterations. You may try a smaller value for $n$ first to verify the correctness of the solution and then proceed with the larger value.

More Answers: