Результаты для любой базовой N и количества наклеек на цифру на DVD "S":
N\S ] 1 | 2 | 3 | 4 | 5 | S?
===================================================================
2 ] 2 | 14 | 62 | 254 | 1022 | 4^S - 2
----+--------+----------+------------+-----------+------+----------
3 ] 12 | 363 | 9840 | 265719 | (27^S - 3)/2
----+--------+----------+------------+-----------+-----------------
4 ] 28 | 7672 | 1965558 | 503184885 |
----+--------+----------+------------+-----------+
5 ] 181 | 571865 | 1787099985 |
----+--------+----------+------------+
6 ] 426 | 19968756 |
----+--------+----------+
7 ] 3930 | (≥ 2^31) |
----+--------+----------+
8 ] 8184 |
----+--------+
9 ] 102780 |
----+--------+
10 ] 199990 |
----+--------+
Я не вижу узоров.
В качестве альтернативы, если наклейка начинается с 0 вместо 1,
N\S ] 1 | 2 | 3 | 4 | 5 | S?
======================================================================
2 ] 4 | 20 | 84 | 340 | 1364 | (4^S-1)*4/3
----+---------+----------+------------+-----------+------+------------
3 ] 12 | 363 | 9840 | 265719 | (27^S - 3)/2
----+---------+----------+------------+-----------+-------------------
4 ] 84 | 7764 | 1965652 | 503184980 |
----+---------+----------+------------+-----------+
5 ] 182 | 571875 | 1787100182 |
----+---------+----------+------------+
6 ] 1728 | 19970496 |
----+---------+----------+
7 ] 3931 | (≥ 2^31) |
----+---------+----------+
8 ] 49152 |
----+---------+
9 ] 102789 |
----+---------+
10 ] 1600000 |
----+---------+
Давайте предположим , что сначала наклеивается наклейка «1», что действительно имеет место для большинства других вычисляемых данных.
Предположим, мы находимся в базе N, и на цифру каждого DVD будет приходиться S новых наклеек.
На DVD #X будет полностью X & times; S «1» наклейки, использованные или нет.
Количество использованных наклеек «1» - это просто число «1» в цифрах от 1 до X в расширении базы N.
Таким образом, нам просто нужно найти точку пересечения X & times; S и общее количество цифр «1».
- N = 2: 1,2,4,5,7,9,12,13,15,17,20,22,25,28,32,33,35,37,40,42, 45,48,52,54,57 ...
- N = 3: 1,1,2,4,5,5,6,6,7,9,10,12,15,17,18,20,21,21,22,22,23,25 , 26,26,27, ...
- N = 10: 1,1,1,1,1,1,1,1,1,2,4,5,6,7,8,9,10,11,12,12, 13,13,13,13,13 ...
не представляется замкнутым для всех этих последовательностей, поэтому петлевые пропорциональные X итерации необходимы. Цифры могут быть извлечены за время log X, поэтому в принципе алгоритм может завершиться за время O (X log X).
Это не лучше, чем другой алгоритм, но по крайней мере много вычислений можно удалить. Пример кода C:
#include <stdio.h>
static inline int ones_in_digit(int X, int N) {
int res = 0;
while (X) {
if (X % N == 1)
++ res;
X /= N;
}
return res;
}
int main() {
int N, S, X;
printf("Base N? ");
scanf("%d", &N);
printf("Stickers? ");
scanf("%d", &S);
int count_of_1 = 0;
X = 0;
do {
++ X;
count_of_1 += S - ones_in_digit(X, N);
if (X % 10000000 == 0)
printf("%d -> %d\n", X/10000000, count_of_1);
} while (count_of_1 >= 0);
printf("%d\n", X-1);
return 0;
}