Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #68 Jan 11 2021 02:57:09
%S 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 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 38,73,39,83,48,54,46,60,56,55,57,65,58,75,47,64,49,74
%N Lexicographically earliest sequence of distinct terms such that the decimal representations of two consecutive terms overlap.
%C Two terms are said to overlap:
%C - if the decimal representation of one term is contained in the decimal representation of the other term (for example, 12 and 2 overlap),
%C - 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 This sequence is a permutation of the positive integers, with inverse A262255.
%C The first overlap involving 1 digit occurs between a(1)=1 and a(2)=10.
%C The first overlap involving 2 digits occurs between a(108)=100 and a(109)=110.
%C The first overlap involving 3 digits occurs between a(1039)=1017 and a(1040)=1101.
%C The first overlap involving 4 digits occurs between a(10584)=10212 and a(10585)=11021.
%H Paul Tek, <a href="/A262323/b262323.txt">Table of n, a(n) for n = 1..10000</a>
%H Paul Tek, <a href="/A262323/a262323.pl.txt">PERL program for this sequence</a>
%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%e The first terms of the sequence are:
%e +----+---------+
%e | n | a(n) |
%e +----+---------+
%e | 1 | 1 |
%e | 2 | 10 |
%e | 3 | 11 |
%e | 4 | 12 |
%e | 5 | 2 |
%e | 6 | 20 |
%e | 7 | 22 |
%e | 8 | 21 |
%e | 9 | 13 |
%e | 10 | 3 |
%e | 11 | 23 |
%e | 12 | 30 |
%e | 13 | 33 |
%e | 14 | 31 |
%e | 15 | 14 |
%e | 16 | 4 |
%e | 17 | 24 |
%e | 18 | 32 |
%e | 19 | 25 |
%e | 20 | 5 |
%e +----+---------+
%o (Perl) See Links section.
%o (Haskell)
%o import Data.List (inits, tails, intersect, delete)
%o a262323 n = a262323_list !! (n-1)
%o a262323_list = 1 : f "1" (map show [2..]) where
%o f xs zss = g zss where
%o g (ys:yss) | null (intersect its $ tail $ inits ys) &&
%o null (intersect tis $ init $ tails ys) = g yss
%o | otherwise = (read ys :: Int) : f ys (delete ys zss)
%o its = init $ tails xs; tis = tail $ inits xs
%o -- _Reinhard Zumkeller_, Sep 21 2015
%o (Python)
%o def overlaps(a, b):
%o s, t = sorted([str(a), str(b)], key = lambda x: len(x))
%o if any(t.startswith(s[i:]) for i in range(len(s))): return True
%o return any(t.endswith(s[:i]) for i in range(1, len(s)+1))
%o def aupto(nn):
%o alst, aset = [1], {1}
%o for n in range(2, nn+1):
%o an = 1
%o while True:
%o while an in aset: an += 1
%o if overlaps(an, alst[-1]): alst.append(an); aset.add(an); break
%o an += 1
%o return alst
%o print(aupto(67)) # _Michael S. Branicky_, Jan 10 2021
%Y Cf. A076654, A262255, A262283.
%Y Cf. A262367 (fixed points), A262411 (ternary version), A262460 (hexadecimal version).
%K nonn,look,base,nice
%O 1,2
%A _Paul Tek_, Sep 19 2015