Задача 637
Гибкая сумма цифр

При любом данном положительном целом числе $n$ можно построить новое целое число путем вставки знаков "плюс" между некоторыми цифрами числа $n$, представленного в $B$-ичной системе счисления, и выполнения сложения.

Например, из $n=123_{10}$ ($n$ в 10-ичной системе счисления) мы можем построить четыре целых числа в 10-ичной системе счисления: $123_{10}$, $1+23=24_{10}$, $12+3=15_{10}$ и $1+2+3=6_{10}$

Пусть $f(n,B)$ будет наименьшим количеством шагов, необходимых для получения однозначного числа в $B$-ичной системе счисления. Например, $f(7,10)=0$ и $f(123,10)=1$.

Пусть $g(n,B_1,B_2)$ будет суммой положительных целых чисел $i$ не превышающих $n$, таких что $f(i,B_1)=f(i,B_2)$.

Известно, что $g(100,10,3)=3302$.

Найдите $g(10^7,10,3)$

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net