login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A342135 Lexicographically earliest strictly increasing sequence whose concatenation is equal to that of the longest common substrings (see comment) of consecutive terms. 0
1, 10, 100, 101, 2012 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,2
COMMENTS
The longest common substring (LCS) of two consecutive terms must always be nonempty and well-defined, i.e., unambiguous: there must be no other (i.e., distinct) common substring of the same length. (The same substring could possibly occur multiple times at different locations in either or both of the two consecutive terms.)
The sequence is well defined, since A011557 = (1, 10, 100, 1000, ...) does satisfy the characteristic property (the sequence of LCS among consecutive terms is again A011557), so there is at least one (and therefore a unique minimal) such sequence.
LINKS
Eric Angelini, Common patterns sequence, math-fun mailing list, Feb 22, 2021.
EXAMPLE
Seq. of terms = 1, 10, 100, 101, 2012, 10121?...: T = 1'10'100'1 01'2 012'10121
Common substr. = 1, 10, 10, 01, 012, ... : S = 1'10'10'01'01 2'...
(=> concatenation of the next L.C.S. must give "012'10121'...")
.
After a(1) = 1, the next larger number sharing a digit with 1 is a(2) = 10.
The concatenated terms so far give T = "110(...)", and the (concatenated) common substring(s) give S = "1(...)". Since S must equal T, the concatenation of the next longest common substrings (LCS) must yield "10(...)".
So the next term a(3) must share a digit 1 with a(2), but it must also contain a digit 0 to produce the digit 0 subsequently required in S.
The next larger number which satisfies both of these requirements is a(3) = 100. This gives S = "110100(...)" and T = "110(...)". Concatenation of subsequent longest common substrings (LCS) must therefore give "100(...)".
As before it is impossible to have as LCS only one digit "1", because then there may be no '0' in the next term, but the next digit in T must be a '0'.
So we must have LCS(a(3), a(4)) = "10" (or longer, but this would require a(4) >= 1000 and we will find a smaller solution).
The next larger possible term, a(4) = 101, indeed satisfies the constraints, and we will see that it does not lead to contradictions.
This gives T = "1'10'100'101(...)" and S = "1'10'10(...)", so concatenation of subsequent LCS must produce "01'01(...)". (We use a separator ' for better readability, but this is not to be considered an element of the string.)
As before it is impossible to have the next LCS equal to "0", because then there may be no '1' in the next term, but the subsequent digit in S must be a '1'.
So we look for a(5) with LCS(a(4), a(5)) = "01" (but no "10" in a(5) as to have a well-defined LCS). The subsequent LCS(a(5),a(6)) and following must then produce "01"+a(5)+"(...)".
We find that 201 is not possible for a(5): This would require S to go on with "012(...)", so we'd again need LCS(a(5),a(6)) = "01" but no "20" in a(6), but this allows no acceptable a(7) such that LCS(a(6),a(7)) starts with the required '2'. Similarly, 301, ..., 901 are not possible.
Also the next larger choice (with well-defined LCS) 1201 is not possible. (We'd need a(6) with "01", but no "12" nor "20", but then a(7) would need an LCS "12" with a(6): impossible.)
The next larger possible choice is a(5) = 201x for some digit x > 0. We find that there can't be a solution with LCS(a(5), a(6)) of length <= 2, but it is possible for LCS = "012", whence x = 2 finally yields a solution. It gives T = "1'10'100'101'2012(...)" and S = "1'10'10'01(...)", so the next LCS must give "012012(...)", and for example a(6) = "10121" appears to give a valid solution.
PROG
(PARI) /* get longest common substring of A and B, but return 0 if the LCS is ambiguous or empty or if a >= b: */
LCS(a, b, A=digits(a), B=digits(b), s)={
(#setintersect(Set(A), Set(B)) && a<b) || return;
forstep( L=#A, 1, -1, for( i=0, #A-L, my(p=A[i+1..i+L]); for( j=0, #B-L,
p==B[j+1..j+L] || next; #s && s!=p && return /* not unique! */;
s=A[i+1..i+L]; next(2))); #s && return(s))}
/* check(S): if the seq. S is consistent (compatible with concatenation of LCS which must be well defined), then show what the next "shared patterns" must be, starting with last term of S and the subsequent one. This helps to see whether the last term in S may be incorrect in spite of S being consistent so far. */
{check(S, verbose=1, T=concat(apply(digits, S)), P=[LCS(S[i-1], S[i])| i<-[2..#S]]) = vecmin([#s | s<-P]) || print("BAD: P=", P, " has an empty element!") || return; verbose && printf("Seq. of LCS = %d. ", P); #P && P=concat(P);
if(#T < #P, print("P longer than S! Swapping; proceed with fingers crossed...");
[T, P] = [P, T]);
if( P==T[1..#P], T=T[#P+1..#T],
!#T || !#P || error("S="S" incompatible with P="P));
verbose && printf("P = %d, to be continued with %d.\n", P, T); [P, T] /* okay */}
CROSSREFS
Cf. A011557 (powers of 10).
Sequence in context: A115832 A336611 A342215 * A169665 A257795 A257950
KEYWORD
nonn,base,more,hard
AUTHOR
Eric Angelini and M. F. Hasler, Mar 01 2021
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 02:23 EDT 2024. Contains 371264 sequences. (Running on oeis4.)