Les résultats pour toute base N et nombre d'autocollants par chiffre par DVD "S" sont :
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 |
----+--------+
Je ne peux pas voir de motifs.
Alternativement, si l'autocollant commence à partir de 0 au lieu de 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 |
----+---------+
Supposons que c'est l'autocollant "1" qui se termine en premier - ce qui est en effet le cas pour la plupart des autres informations calculées.
Supposons que nous sommes en base N et qu'il y aura S nouveaux autocollants par chiffre par DVD.
À la DVD n°X, il y aura totalement X×S autocollants "1", utilisés ou non.
Le nombre d'autocollants "1" utilisés est simplement le nombre de "1" dans les chiffres de 1 à X dans l'expansion en base N.
Il suffit donc de trouver le point de croisement entre X×S et le total du nombre de chiffres "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,…
Il ne semble pas y avoir de formule fermée pour toutes ces séquences, donc une boucle proportionnelle à X est nécessaire. Les chiffres peuvent être extraits en log X temps, donc en principe l'algorithme peut être terminé en O(X log X) temps.
Ce n'est pas mieux que l'autre algorithme mais au moins beaucoup de calculs peuvent être supprimés. Un exemple de code 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;
}
