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,
É.
__________