login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A135472 Shortest and lexicographically earliest string of decimal digits with property that when made into cycle every pair of digits from 0,0 to 9,9 can be seen exactly once. 1
0, 0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8, 0, 9, 1, 1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 9, 2, 2, 3, 2, 4, 2, 5, 2, 6, 2, 7, 2, 8, 2, 9, 3, 3, 4, 3, 5, 3, 6, 3, 7, 3, 8, 3, 9, 4, 4, 5, 4, 6, 4, 7, 4, 8, 4, 9, 5, 5, 6, 5, 7, 5, 8, 5, 9, 6, 6, 7, 6, 8, 6, 9, 7, 7, 8, 7, 9, 8, 8, 9, 9 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

Comments from Max Alekseyev, Feb 14 2008: (Start) It is easy to prove that such a string exists and, moreover, it can be closed into a circle of length 100.

Namely, let us construct a (directed) de Bruijn graph G on vertices V={0,1,2,3,4,5,6,7,8,9}, where every vertex is connected to every other vertex (including itself - so there is a self-loop at every vertex) by a directed arc. The arcs in G "encode" all possible 2-digit strings.

Any string over the alphabet V can be viewed as a path in G. If the string contains all 2-digit strings as substrings, then the corresponding path passes through every arc in G. The shortest such path is an Eulerian one (if it exists) and it indeed exists in G.

The indegree of every vertex in G equals its outdegree, implying that there exists an Eulerian cycle. Such a cycle has length 100 and visit every vertex 10 times.

So we want to find an Eulerian cycle resulting in the lexicographically earliest string. Such a cycle can be easily found by traversing G in a greedy manner. (End)

LINKS

Table of n, a(n) for n=1..100.

CROSSREFS

Cf. A102167.

Sequence in context: A276457 A171181 A034948 * A008723 A263397 A008803

Adjacent sequences:  A135469 A135470 A135471 * A135473 A135474 A135475

KEYWORD

nonn,fini,full,base,nice

AUTHOR

Patrick A. Kirol (sunwukong(AT)povn.com), Feb 08 2008

EXTENSIONS

Confirmed by Max Alekseyev, Joshua Zucker and Joerg Arndt, Feb 14 2008

Edited by N. J. A. Sloane, Feb 18 2008

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 20 14:13 EST 2019. Contains 319333 sequences. (Running on oeis4.)