Runs of integers sharing the same digit-length

(a sequence dedicated to Lotta Hannerz)

Hello SeqFans,

The hereunder sequence S deals with runs of terms having the same “length”.

The length of an integer is its quantity of digits:

1, 7 and 9       have a length of 1;

22, 57 and 94    have a length of 2;

101, 102 and 999 have a length of 3, etc.

A run of terms sharing the same length is called R.

The r-size of R is the amount of terms belonging to R. For example, with the finite sequence E, we have:

E = 1,7,9,22,57,94,5,101,102,103,104,1,7,9,8,8,8.

R(1) = 1,7,9           --> r-size = 3

R(2) = 22,57,94        --> r-size = 3

R(3) = 5               --> r-size = 1

R(4) = 101,102,103,104 --> r-size = 4

R(5) = 1,7,9,8,8,8     --> r-size = 5

We want here to build S such that:

(1) S is a permutation of N

(2) S is lexicographically the first sequence describing its own succession of r-sizes.

S = 3,1,2,10,4,5,11,12,13,14,15,16,17,18,19,20,6,7,8,9,21,22,23,24,25,100->110,26->37,111->123,38->51,

Rs =  3   1   2               10                  4          5           11      12      13      14

124->138,52->67,139->155,68->85,156->174,1000->1019,86->91,175->181,92->99,182->190,1020->1040,...

15      16      17      18      19        20       6       7       8       9         21

We see that Rs reproduces S.

__________

In building the sequence we must always take the “smallest available integer not yet present in S and not leading to a contradiction”.

“Not leading to a contradiction” may be tricky. Look at the sequence T which doesn’t start exactly like S:

T = 3,2,1,10,11,4,12,13,14,15,16,17,18,19,20,21,100,101,102,103,104,105,106,107,108,109,110,5,6,7,8,22->33, ...

Rs =  3     2   1              10                                    11                        4      12

... if the 6th term of T is “4”, the number “9” will never show... So we have to put “5” instead – see sequence U here:

U = 3,2,1,10,11,5,12,13,14,15,16,17,18,19,20,21,100,101,102,103,104,105,106,107,108,109,110,4,6,7,8,9, 22->33, ...

Rs =  3     2   1              10                                    11                         5        12

You might think that U is ok now – but wait! We will encounter another problem later in the sequence, due to the modified

run which now shows “9”: 4,6,7,8,9.

5

... yes, in order to “get rid” as soon as possible of the 2-digit integers, we will have to modify again this last modified run!

It will now look like this: 4,7,6,9,8 (this is because we will be left with 18 2-digit integers, going from 82 to 99, which we will be lucky to be able to split into runs of size 4 + 6 + 8). The true beginning of T is thus V:

V = 3,2,1,10,11,5,12,13,14,15,16,17,18,19,20,21,100,101,102,103,104,105,106,107,108,109,110,4,7,6,9,8,22->33, ...

Rs =  3     2   1              10                                    11                         5       12

What if we hadn’t been lucky? This is, what if we weren’t able to split 18 into alternate runs like 4 + 6 + 8? The only solution would then have consisted in merging those 18 integers with the integers belonging to the last sound 2-digit run. In our example with U, the last sound run had a size of 18 (integers 64->81); merging the integers 82->99 would have produced the run 64->99 of size 36. This means that we have to modify the beginning of U into W – look and compare the two sequences here:

U = 3,2,1,10,11,5,12,13,14,15,16,17,18,19,20,21,100,101,102,103,104,105,106,107,108,109,110,4,6,7,8,9, 22->33, ...

Rs =  3     2   1              10                                    11                         5        12

W = 3,2,1,10,11,5,12,13,14,15,16,17,36,18,19,20,100,101,102,103,104,105,106,107,108,109,110,4,6,7,8,9, 21->32, ...

Rs =  3     2   1              10                                    11                         5        12

We see here how S is delicate to build: a simple change in its 6th term generates chaos...

I hope that the terms above are ok...

Best,

É.

__________