cp's OEIS Frontend

A262323 Lexicographically earliest sequence of distinct terms such that the decimal representations of two consecutive terms overlap.

%I A262323 #68 Jan 11 2021 02:57:09
%S A262323 1,10,11,12,2,20,22,21,13,3,23,30,33,31,14,4,24,32,25,5,15,41,16,6,26,
%T A262323 42,27,7,17,51,18,8,28,52,29,9,19,61,36,43,34,40,44,45,50,35,53,37,63,
%U A262323 38,73,39,83,48,54,46,60,56,55,57,65,58,75,47,64,49,74
%N A262323 Lexicographically earliest sequence of distinct terms such that the decimal representations of two consecutive terms overlap.
%C A262323 Two terms are said to overlap:
%C A262323 - if the decimal representation of one term is contained in the decimal representation of the other term (for example, 12 and 2 overlap),
%C A262323 - or if, for some k>0, the first k decimal digits (without leading zero) of one term correspond to the k last decimal digits of the other term (for example, 1017 and 1101 overlap).
%C A262323 This sequence is a permutation of the positive integers, with inverse A262255.
%C A262323 The first overlap involving 1 digit occurs between a(1)=1 and a(2)=10.
%C A262323 The first overlap involving 2 digits occurs between a(108)=100 and a(109)=110.
%C A262323 The first overlap involving 3 digits occurs between a(1039)=1017 and a(1040)=1101.
%C A262323 The first overlap involving 4 digits occurs between a(10584)=10212 and a(10585)=11021.
%H A262323 Paul Tek, <a href="/A262323/b262323.txt">Table of n, a(n) for n = 1..10000</a>
%H A262323 Paul Tek, <a href="/A262323/a262323.pl.txt">PERL program for this sequence</a>
%H A262323 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%e A262323 The first terms of the sequence are:
%e A262323 +----+---------+
%e A262323 | n  | a(n)    |
%e A262323 +----+---------+
%e A262323 |  1 |  1      |
%e A262323 |  2 |  10     |
%e A262323 |  3 | 11      |
%e A262323 |  4 |  12     |
%e A262323 |  5 |   2     |
%e A262323 |  6 |   20    |
%e A262323 |  7 |  22     |
%e A262323 |  8 |   21    |
%e A262323 |  9 |    13   |
%e A262323 | 10 |     3   |
%e A262323 | 11 |    23   |
%e A262323 | 12 |     30  |
%e A262323 | 13 |    33   |
%e A262323 | 14 |     31  |
%e A262323 | 15 |      14 |
%e A262323 | 16 |       4 |
%e A262323 | 17 |      24 |
%e A262323 | 18 |     32  |
%e A262323 | 19 |      25 |
%e A262323 | 20 |       5 |
%e A262323 +----+---------+
%o A262323 (Perl) See Links section.
%o A262323 (Haskell)
%o A262323 import Data.List (inits, tails, intersect, delete)
%o A262323 a262323 n = a262323_list !! (n-1)
%o A262323 a262323_list = 1 : f "1" (map show [2..]) where
%o A262323    f xs zss = g zss where
%o A262323      g (ys:yss) | null (intersect its $ tail $ inits ys) &&
%o A262323                   null (intersect tis $ init $ tails ys) = g yss
%o A262323                 | otherwise = (read ys :: Int) : f ys (delete ys zss)
%o A262323      its = init $ tails xs; tis = tail $ inits xs
%o A262323 -- _Reinhard Zumkeller_, Sep 21 2015
%o A262323 (Python)
%o A262323 def overlaps(a, b):
%o A262323   s, t = sorted([str(a), str(b)], key = lambda x: len(x))
%o A262323   if any(t.startswith(s[i:]) for i in range(len(s))): return True
%o A262323   return any(t.endswith(s[:i]) for i in range(1, len(s)+1))
%o A262323 def aupto(nn):
%o A262323   alst, aset = [1], {1}
%o A262323   for n in range(2, nn+1):
%o A262323     an = 1
%o A262323     while True:
%o A262323       while an in aset: an += 1
%o A262323       if overlaps(an, alst[-1]): alst.append(an); aset.add(an); break
%o A262323       an += 1
%o A262323   return alst
%o A262323 print(aupto(67)) # _Michael S. Branicky_, Jan 10 2021
%Y A262323 Cf. A076654, A262255, A262283.
%Y A262323 Cf. A262367 (fixed points), A262411 (ternary version), A262460 (hexadecimal version).
%K A262323 nonn,look,base,nice
%O A262323 1,2
%A A262323 _Paul Tek_, Sep 19 2015