[seqfan] A Skolem-like seq with no terms repeated.

[Eric Angelini]

Hello SeqFans,
Here is a Skolem-like seq with no terms repeated.

Sk= 1,2,10,3,20,4,5,30,6,7,40,8,50,9,11,60,12,70,21,41,80,22,31,90,42,51,32,61,71,81,91,52,23,33,62,24,72,34,82,13,92,14,43,53,63,73,83,44,93,54,15,64,16,74,25,84,35,26,94,45,36,55,65,75,46,85,95,56,17,66,18,76,27,37,86,28,96,38,47,57,67,77,87,48,97,58,19,68,100,78,29,88,39,200,98,49,300,59,69,79,400,89,99,500,101,600,102,700,...

The idea: 	
The successive pairs of terms that start with the digit k enclose k terms.

Example:
Sk=1,2,10,... There is 1 term enclosed by 1 and 10: the term “2”;
Sk= 1,2,10,3,20,... There are 2 terms enclosed by 2 and 20: “10” and “3”;
Sk= 1,2,10,3,20,4,5,30,... There are 3 terms enclosed by 3 and 30: “20”, “4” and “5”;
... and if you look at the present end of Sk, you will see that there are indeed 5 terms between 59 and 500: [59,69,79,400,89,99,500]

Sk is the lexico-first permutation of the integers >0 having this property. 

How was Sk extended after the term “9”?
To avoid unwanted “collisions”, the best way to extend Sk is to use the “smallest pair unused so far that fits”.

Example (we slow down the building process to be clear):

Sk=1,..,10   (pair #1 is used – the ordered pairs list stands below)
Sk=1,2,10,..,20   (pair #2 is used)
Sk=1,2,10,3,20,..,..,30   (pair #3 is used)
Sk=1,2,10,3,20,4,..,30,..,..,40   (pair #4 is used)
Sk=1,2,10,3,20,4,5,30,..,..,40,..,50   (pair #5 is used)
... (fast forward to the “9-90” pair)
Sk=1,2,10,3,20,4,5,30,6,7,40,8,50,9,..,60,..,70,..,..,80,..,..,90

What now?

The next pair in the list is “11-12” which is easy to insert:
Sk=1,2,10,3,20,4,5,30,6,7,40,8,50,9,11,60,12,70,..,..,80,..,..,90

Next? As we have decided to always fill the next “hole” first, we will use the pair “21-22”:

Sk=1,2,10,3,20,4,5,30,6,7,40,8,50,9,11,60,12,70,21,..,80,22,..,90

Collision coming!

The next pair _will not be_ “23-24”, as we would have:
Sk=1,2,10,3,20,4,5,30,6,7,40,8,50,9,11,60,12,70,21,23,80,22,24,90

... where this portion of Sk is now ambiguous: [21,23,80,22,24].

We will rather explore the pair “31-32” (which doesn’t fit) and the next one, “41-42” (which fits):

Sk=1,2,10,3,20,4,5,30,6,7,40,8,50,9,11,60,12,70,21,41,80,22,..,90,42

Etc.

The pair-list is here (remember, “to fill a hole in Sk, try always to insert the unused pair that stands closer to the top of the list”):

1-10
2-20
3-30
4-40
5-50
6-60
7-70
8-80
9-90
11-12
21-22
31-32
41-42
51-52
61-62
71-72
81-82
91-92
13-14
23-24
33-34
43-44
53-54
63-64
73-74
83-84
93-94
...
87-88
97-98
19-100
29-200
39-300
...
99-900
101-102
201-202
301-302
...
901-902
103-104
203-204
303-304
...

I guess the graph will look more or less fractal.
Best,
É.