Сколько единиц участвует в десятичной записи 1001004-значного числа 121122111222111122221…111…11222..22…?
Идея задачи: число строится как бесконечная последовательность блоков вида для каждого k = 1, 2, 3, ...: сначала k единиц, потом k двойк. Т.е. после M полноценных блоков всего в числе digits = M(M+1), а единиц в этом префиксе — сумма первых M чисел = M(M+1)/2.
Дано L = 1 001 004 digits. Найдём, сколько полных блоков помещается в этот префикс.
- Найдём максимальный M такой, что M(M+1) ≤ L.
- Для M = 1000: 1000·1001 = 1 001 000 ≤ L.
- Для M = 1001: 1001·1002 = 1 003 002 > L. Следовательно, M = 1000 полных блоков умещаются, и осталось R = L − M(M+1) = 1 001 004 − 1 001 000 = 4 цифры.
Сколько единиц в первых M полных блоках? Это сумма первых M натуральных чисел: M(M+1)/2 = 1000·1001/2 = 500 500.
Учтём остаток R в следующем блоке (блоке 1001): Блок 1001 состоит из 1001 единицы, за которыми идут 1001 двойка. Рассмотрим первые R = 4 digits этого блока: все они единицы, следовательно добавляем ещё min(R, 1001) = 4 единицы.
Итого количество единиц в первых 1 001 004 цифрах равно: 500 500 + 4 = 500 504.
Ответ: 500504.
