Substrings so far
Definition: a(n) is the count of substrings a(n+1) so far in the sequence, including a(n+1) itself.
S = 1,2,1,3,1,4,1,5,1,6,1,7,1,8,1,11,1,13,1,15,1,17,1,19,1,21,1,22,1,23,1,24,1,25,1,26,1,27,1,28,1,29,1,31,1,32,1,33,1,34,1,35,1,36,1,37,1,38,1,39,1,41,1,42,1,43,1,44,1,45,1,46,1,47,1,48,1,49,1,51,1,52,1,53,1,54,1,55,1,56,1,57,1,58,1,59,1,61,1,62,1,63,1,64,1,65,1,66,1,67,1,68,1,69,1,71,1,72,1,73,1,74,1,75,1,76,1,77,1,78,1,79,1,81,1,82,1,83,1,84,1,85,1,86,1,87,1,88,1,89,1,91,1,92,1,93,1,94,1,95,1,96,1,97,1,98,1,101,1,103,1,105,1,107,1,109,1,112,1,115,1,118,1,120,1,122,1,124,1,126,1,…
S must be
“read” like this, term by term from the left to the right:
a(1) – there
is 1 substring “2” so far in S; (true, if you consider the segment <1,2>);
a(2) – there
are 2 substrings “1” so far in S; (true, if you consider the segment <1,2,1>);
a(3) – there
is 1 substring “3” so far in S; (true, if you consider the segment <1,2,1,3>);
a(4) – there
are 3 substrings “1” so far in S; (true, if you consider the segment <1,2,1,3,1>);
a(5) – there
is 1 substring “4” so far in S; (true, if you consider the segment <1,2,1,3,1,4>);
…
a(14) – there
are 8 substrings “1” so far in S; (true, if you consider the segment <1,2,1,3,1,4,1,5,1,6,1,7,1,8,1>);
a(15) – there
is 1 substring “11” so far in S; (true, if you consider the segment <1,2,1,3,1,4,1,5,1,6,1,7,1,8,1,11>);
a(16) – there
are 11 substrings “1” so far in S; (true, if you consider the segment <1,2,1,3,1,4,1,5,1,6,1,7,1,8,1,11,1>);
Etc.
Here are
my worries:
1) Is the term substring clear? A
substring is intended here as the concatenation of k digits of a(n),
with k > 0 and k=< d [d is the number of digits in a(n)]. For example, “11” shows one substring “11” and two
substrings “1”; similarly “13” shows one substring “13”, one substring “1” and
one substring “3”. Now, what does “101” show? As no term of S can start with 0,
we will say that “101” shows the substrings “101” (once), “10” (once) and “1”
(twice). Similarly, “112” shows the substrings “112” (once), “11” (once), “12”
(once), “1” (twice) and “2” (once).
2) How can we describe this sequence? Yes, we
want S to be infinite – but there might still exist a lexicographically
earliest sequence than S! Compare the start of S to the start of T:
S = 1,2,1,3,1,4,1,5,1,6,1,7,1,8,1,11,1,13,1,15,…
T = 1,2,1,3,1,4,1,5,1,6,1,7,1,8,1, 9,1,10,…
T beats
S. But there is a problem – T cannot be extended after 10.
Other
starts still beat S – but fail, like the sequence U:
S = 1,2,1,3,1,4,1,5,1,6,1,7,1,8,1,11,1,13,1,15,…
U = 1,2,1,3,1,4,1,5,1,6,1,7,1,8,1,10,1,12,1,14,1,16,1,18,1,9,
and stop.
What if
S (in its current form, with all odd-indexed terms being “1”) blocks itself after, say,
10000 terms?
We might then be forced to backtrack… and restart perhaps with the sequences V, W, X, Y or Z (which I
didn’t investigate):
V = 1,2,2,1,3,1,4,1,5,1,6,1,7,1,8,…
W = 1,2,2,1,3,2,3,1,4,1,5,1,6,1,7,…
X = 1,2,2,1,3,2,3,1,4,2,4,1,5,1,6,…
Y = 1,2,2,1,3,2,3,1,4,2,4,1,5,2,5,…
Z = 1,2,2,1,3,2,3,3,1,4,2,4,1,5,1,…
Best,
__________________________
Update (in French), March 9, 2020
Update (in French), March 9, 2020
[Carole D.]
> L'idée de départ était jolie mais finalement ça revient à alterner des 1 et a(n)= nombre de 1 rencontrés jusque là, y compris dans a(n+1), c'est un peu décevant mais ça rend le programme beaucoup plus rapide. À+ !
> Voilà :
> 1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 11, 1, 13, 1,15, 1, 17, 1, 19, 1, 21, 1, 22, 1, 23, 1, 24, 1, 25, 1, 26, 1, 27, 1, 28, 1,29, 1, 31, 1, 32, 1, 33, 1, 34, 1, 35, 1, 36, 1, 37, 1, 38, 1, 39, 1, 41, 1,42, 1, 43, 1, 44, 1, 45, 1, 46, 1, 47, 1, 48, 1, 49, 1, 51, 1, 52, 1, 53, 1,54, 1, 55, 1, 56, 1, 57, 1, 58, 1, 59, 1, 61, 1, 62, 1, 63, 1, 64, 1, 65, 1,66, 1, 67, 1, 68, 1, 69, 1, 71, 1, 72, 1, 73, 1, 74, 1, 75, 1, 76, 1, 77, 1,78, 1, 79, 1, 81, 1, 82, 1, 83, 1, 84, 1, 85, 1, 86, 1, 87, 1, 88, 1, 89, 1,91, 1, 92, 1, 93, 1, 94, 1, 95, 1, 96, 1, 97, 1, 98, 1, 101, 1, (...)
[Éric A.]
> c'est un peu décevant
... oui, mais tu m'as envoyé le plan B, celui qui marchera toujours (je crois) avec une infinité de termes (décevants) à la clef !
Mais ta suite est-elle la lexico-1st ? Ah ah !
Regarde les derniers termes en jaune -- d'abord ton départ :
1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 11, 1, 13, 1,15, 1, 17, 1, 19, 1, 21, 1, 22, 1, 23, 1, 24, 1, 25, 1, 26, 1, 27, 1, 28, 1, 29, 1,...
Maintenant un des miens possibles, lexico-mieux :
1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 11, 1, 13, 1,15, 1, 17, 1, 19, 1, 21, 1, 22, 1, 23, 1, 24, 1, 25, 1, 26, 1, 27, 1, 10, 2,...
Tu as vu l’astuce ?
J’ai compté les substrings « 2 » jusqu’à ce que le compte des « 2 » soit égal à une substring non comptabilisée encore -- valant donc mon 1 jaune avant le 10 et le 2 jaunes ! (car après « 27, 1, » chez toi et chez moi, il faut essayer de prolonger par une substring nouvelle inférieure à 28 pour faire lexico-mieux ! J’ai donc vu que la substring « 10 » convenait car elle n’avait pas encore été employée, et j’ai compté les occurrences de « 2 » jusqu’à ce qu’elles valent 10 !-)
Le programme doit donc compter en plus des « 1 », toutes les autres chaînes (2, 3, 4, 5, ..., 10, 11, 12, ...) et se poser systématiquement la question : quelle est la plus petite paire de nouveaux termes susceptibles de prolonger la suite... sans bloquer celle-ci plus loin !
En effet, la lexico-mieux que je te propose (avec 1, 10, 2 en jaune) va peut-être se bloquer -- voyons.
D'abord la lexico-mieux comme ci-dessus :
1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 11, 1, 13, 1,15, 1, 17, 1, 19, 1, 21, 1, 22, 1, 23, 1, 24, 1, 25, 1, 26, 1, 27, 1, 10, 2,...
Maintenant cette lexico-mieux prolongée par A, que nous cherchons :
1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 11, 1, 13, 1,15, 1, 17, 1, 19, 1, 21, 1, 22, 1, 23, 1, 24, 1, 25, 1, 26, 1, 27, 1, 10, 2, A, ...
Ce A peut valoir 8, 10, 11, 13, 15, 17, 19, 21, 22, 23, 24, 25, 26 ou 27, car ces substrings ne figurent qu'à un seul exemplaire – exemplaires qui seront 2 quand A aura été trouvé ;
Essayons le plus petit terme possible (A = 8) :
1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 11, 1, 13, 1,15, 1, 17, 1, 19, 1, 21, 1, 22, 1, 23, 1, 24, 1, 25, 1, 26, 1, 27, 1, 10, 2, 8, B, ...
Par quel B faire suivre ce 8 ? Il faut compter 7 « objets » uniques qui figurent déjà dans la suite, et prolonger celle-ci avec cet « objet ». Eh bien aucun B de fonctionne, qu'il soit égal à 1, ou 2, ou 3, ... ou quoi que ce soit !
Remplaçons A = 8 par A = 10, et cherchons si un autre B fonctionne. Nib là aussi !
Alors?
Alors je souhaite bon courage à ton algo !-)
____________________
Update de l'update :
Carole avait évidemment pensé à ces "astuces" et testé toutes les branches possibles au fur et à mesure de l'avancée de la suite (avec sa litanie de « 1 »). Pas de miracle donc, toutes les branches se bloquent tôt ou tard comme ci-dessus — et on continue de manière « décevante » jusqu'à 2000. Je vais proposer la suite quand même à l'OEIS et voir si elle est accepté.
Merci et bravo Carole !
... oui, mais tu m'as envoyé le plan B, celui qui marchera toujours (je crois) avec une infinité de termes (décevants) à la clef !
Mais ta suite est-elle la lexico-1st ? Ah ah !
Regarde les derniers termes en jaune -- d'abord ton départ :
1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 11, 1, 13, 1,15, 1, 17, 1, 19, 1, 21, 1, 22, 1, 23, 1, 24, 1, 25, 1, 26, 1, 27, 1, 28, 1, 29, 1,...
Maintenant un des miens possibles, lexico-mieux :
1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 11, 1, 13, 1,15, 1, 17, 1, 19, 1, 21, 1, 22, 1, 23, 1, 24, 1, 25, 1, 26, 1, 27, 1, 10, 2,...
Tu as vu l’astuce ?
J’ai compté les substrings « 2 » jusqu’à ce que le compte des « 2 » soit égal à une substring non comptabilisée encore -- valant donc mon 1 jaune avant le 10 et le 2 jaunes ! (car après « 27, 1, » chez toi et chez moi, il faut essayer de prolonger par une substring nouvelle inférieure à 28 pour faire lexico-mieux ! J’ai donc vu que la substring « 10 » convenait car elle n’avait pas encore été employée, et j’ai compté les occurrences de « 2 » jusqu’à ce qu’elles valent 10 !-)
Le programme doit donc compter en plus des « 1 », toutes les autres chaînes (2, 3, 4, 5, ..., 10, 11, 12, ...) et se poser systématiquement la question : quelle est la plus petite paire de nouveaux termes susceptibles de prolonger la suite... sans bloquer celle-ci plus loin !
En effet, la lexico-mieux que je te propose (avec 1, 10, 2 en jaune) va peut-être se bloquer -- voyons.
D'abord la lexico-mieux comme ci-dessus :
1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 11, 1, 13, 1,15, 1, 17, 1, 19, 1, 21, 1, 22, 1, 23, 1, 24, 1, 25, 1, 26, 1, 27, 1, 10, 2,...
Maintenant cette lexico-mieux prolongée par A, que nous cherchons :
1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 11, 1, 13, 1,15, 1, 17, 1, 19, 1, 21, 1, 22, 1, 23, 1, 24, 1, 25, 1, 26, 1, 27, 1, 10, 2, A, ...
Ce A peut valoir 8, 10, 11, 13, 15, 17, 19, 21, 22, 23, 24, 25, 26 ou 27, car ces substrings ne figurent qu'à un seul exemplaire – exemplaires qui seront 2 quand A aura été trouvé ;
Essayons le plus petit terme possible (A = 8) :
1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 11, 1, 13, 1,15, 1, 17, 1, 19, 1, 21, 1, 22, 1, 23, 1, 24, 1, 25, 1, 26, 1, 27, 1, 10, 2, 8, B, ...
Par quel B faire suivre ce 8 ? Il faut compter 7 « objets » uniques qui figurent déjà dans la suite, et prolonger celle-ci avec cet « objet ». Eh bien aucun B de fonctionne, qu'il soit égal à 1, ou 2, ou 3, ... ou quoi que ce soit !
Remplaçons A = 8 par A = 10, et cherchons si un autre B fonctionne. Nib là aussi !
Alors?
Alors je souhaite bon courage à ton algo !-)
____________________
Update de l'update :
Carole avait évidemment pensé à ces "astuces" et testé toutes les branches possibles au fur et à mesure de l'avancée de la suite (avec sa litanie de « 1 »). Pas de miracle donc, toutes les branches se bloquent tôt ou tard comme ci-dessus — et on continue de manière « décevante » jusqu'à 2000. Je vais proposer la suite quand même à l'OEIS et voir si elle est accepté.
Merci et bravo Carole !
jolie image !!!
RépondreSupprimer