An
ugly self-describing sequence.
[Please
forgive my bad English]
Let us define the
terms of the (monotonically
increasing) sequence S;
--> a(n) is the sum of the first a(n) digits of S:
S = 1, 10, 11, 12,
20, 111, 112, 120, ...
Building rule:
Start with 1; this
1 says: I represent the sum of the first digit of S -- which is true as 1 =
1;
S = 1, ...
The next term cannot be 2:
S = 1, 2, ...
... as this 2 would say: I represent the sum of the first 2
digits of S -- which is false as 2 <> 3;
Similarly, the next
term after 1 cannot be 3, 4, 5, ... or 9.
Are we stuck? No
here comes 10:
S = 1, 10, ...
10 says something
about the future of the sequence because the rest of the sequence is not
written yet; 10 says: I represent the sum of the first 10 digits of S; we will keep this in mind and try, nonetheless, to
prolong S, adding always the smallest integer available not leading immediately to a
contradiction:
S = 1, 10, 11, 12, ...
What now? We have
seven digits adding up to 7; in order to obey to the integer 10 of S, we have to put the
smallest integer available not leading immediately to a contradiction; is
13 this integer? No, 13 would push the <Digit Sum> beyond the 10 limit
(to 11, exactly); we then try 14
but this is worse; same with 15, etc. The first integer not leading to a
contradiction is 20, which keeps both the <Digit Sum> and the <Digit
Quantity> alive:
S = 1, 10, 11, 12, 20, ...
The first 9 digits of
S sum up to 9; thus the next term of S must:
- must start with a
1,
- be greater than 20.
S will look like this:
S = 1, 10, 11, 12, 20,
1..,
... where 1.. is a 3-digit number.
Which one? Now that we have obeyed to the 10 command, we must read the next
integer of S, which is 11; this means that our 3-digit
integer must look like this:
S = 1, 10, 11, 12, 20,
11.,
The 12 integer of S gives the answer: the
integer we are looking for is 111:
S = 1, 10, 11, 12, 20,
111,
Lets check if we
have obeyed to the first statements of S:
- Is 1 the sum of the first digit of
S? (yes:
1=1)
- Is 10 the sum of
the first 10 digits of S? (yes: 1+1+0+1+1+1+2+2+0+1=10)
- Is 11 the sum of
the first 11 digits of S? (yes: 1+1+0+1+1+1+2+2+0+1+1=11)
- Is 12 the sum of
the first 12 digits of S? (yes: 1+1+0+1+1+1+2+2+0+1+1+1=12)
The next command we
must obey is now 20, which says: the first 20 digits of S must
sum up to 20, exactly; this leaves us with a certain freedom to prolong S until the next check, lead by 111, which will say, as
usual: I represent the sum of the first 111 digits of S:
The next command we
must obey is now 111, which says: the first 111 digits of S must sum up to 111, exactly; this leaves us with a
certain freedom to prolong S until the next
check, lead by 111, which will say, as usual: I represent the sum of the first
111 digits of S:
The first 73 terms of
S appear to be (thanks
to Maximilian Hasler):
S = 1, 10, 11, 12, 20, 111, 112, 120, 1000, 1001, 1002, 1003,
1004, 1005, 1006, 1007, 1008, 1009, 1010, 1011, 1012, 1013, 1014, 1015, 1016,
10000, 10000000000000000000, 10000000800000000000, 10000000800000000001,
10000000800000000002, 10000000800000000003, 10000000800000000004,
10000000800000000005, 10000000800000000006, 10000000800000000007,
10000000800000000008, 10000000800000000009, 10000000800000000010,
10000000800000000011, 10000000800000000012, 10000000800000000013,
10000000800000000014, 10000000800000000015, 10000000800000000016,
10000000800000000017, 10000000800000000018, 10000000800000000019,
10000000800000000020, 10000000800000000021, 10000000800000000022,
10000000800000000023, 10000000800000000024, 10000000800000000025,
10000000800000000026, 10000000800000000027, 10000000800000000028,
10000000800000000029, 10000000800000000030, 10000000800000000031,
10000000800000000032, 10000000800000000033, 10000000800000000034,
10000000800000000035, 10000000800000000036, 10000000800000000037,
10000000800000000038, 10000000800000000039, 10000000800000000040,
10000000800000000041, 10000000800000000042, 13999999999999999999,
99999999911111111111, 111110000000000000000, ...
As a first
verification, let us insert S in a table; the
first column is S; the second column is the DigitSum reached _at the end of the considered integer of S_; the third column in the quantity of digits (DigitQuant) used so far (computed _at the end of the same integer of S_); the
fourth column (InRed) is the
rank, in S, of the 1st, 10th, 11th,
12th, 111th, 112th, 113th, etc.,
digit of S until the 1000th (they are highlighted in red in the first column):
S DigSum DigQuant InRed
1 1 1 1st
10
2 3
11 4 5
12 7 7
20 9 9
111 12
12
10th, 11th and 12th
112 16 15
120 19 18
1000 20
22 20th
1001 22 26
1002 25 30
1003 29 34
1004 34
38
1005 40 42
1006 47 46
1007 55 50
1008 64
54
1009 74 58
1010 76 62
1011 79 66
1012 83 70
1013 88 74
1014 94 78
1015
101 82
1016 109 86
10000 110 91
10000000000000000000 111
111
111th
10000000800000000000 120
131 120th
10000000800000000001 130 151
10000000800000000002 141 171
10000000800000000003 153 191
10000000800000000004 166 211
10000000800000000005 180 231
10000000800000000006 195 251
10000000800000000007 211 271
10000000800000000008 228 291
10000000800000000009 246 311
10000000800000000010 256 331
10000000800000000011 267
351
10000000800000000012 279 371
10000000800000000013 292 391
10000000800000000014 306 411
10000000800000000015 321
431
10000000800000000016 337 451
10000000800000000017 354 471
10000000800000000018 372 491
10000000800000000019 391 511
10000000800000000020 402 531
10000000800000000021 414 551
10000000800000000022 427 571
10000000800000000023 441 591
10000000800000000024 456 611
10000000800000000025 472 631
10000000800000000026 489
651
10000000800000000027 507 671
10000000800000000028 526 691
10000000800000000029 546 711
10000000800000000030 558
731
10000000800000000031 571 751
10000000800000000032 585 771
10000000800000000033 600 791
10000000800000000034 616 811
10000000800000000035 633 831
10000000800000000036 651 851
10000000800000000037 670 871
10000000800000000038 690 891
10000000800000000039 711 911
10000000800000000040 724 931
10000000800000000041 738
951
10000000800000000042 753 971
13999999999999999999 919 991
99999999911111111111 1011
1011
1000th to 1011th
111110000000000000000
1016 1032 1012th to 1016th
...
To build S:
- start with 1
- a(n) = a(n)+1, but:
- if
[a(n) = a(n)+1] produces
immediately a contradiction, try a(n) = a(n)+2.
- if
[a(n) = a(n)+2] also produces
a contradiction, try a(n) = a(n)+3.
- if
[a(n) = a(n)+3] still
produces a contradiction, try a(n) = a(n)+4.
... etc.
There will always be
an integer a(n)+k
which will not produce immediately a contradiction; we will always use the
smallest a(n)+k to prolong the
sequence. Thus, S is unique.
Could someone insane
please (double) check the above monstrosities?
Best,
Ι.
__________
Paolo Lava
suggests an interesting variant:
Another possible sequence on the subject: delete the
"monotonically increasing" condition and consider, at any step, the
minimum possible number to be inserted, without repetition. It should be:
S2 = 1, 10, 2, 4, 100, 101, 11, 12, 13, 14, 30, 1000,
10000, 40, 41, 100000, 102, 43, 60, 110, 1000000001, 70, 1000001, 103, 69, ...
Thanks
to all, again and especially to Maximilian Hasler; here is his last post on the subject:
(Kind of Maple notation, I
hope it's understandable):
1,10,11,12,20,111,112,120,
seq( 1000+i, i=0..16
),
10 000,10^19,
seq( 10^19+10^11*8+i , i=0..42 ),
10^19+4*10^18-1, 10^20-10^11+(10^11-1)/9,
seq( (10^21-10^16)/9+i , i=0..413 ),
(10^21-10^16)/9+3*10^15-1,
seq( 10^(20+i)-1, i=1..10 ),
seq( 10^31-10^12 +i, i=0..10^12-1)...
On a second thought, the last limit might
be extended to something around 10^17: namely, we simply put all numbers up to
somewhere before the 10^19-th digit; since we have 30 digits/number (at the
beginning, and they won't exceed 31 digits), we can write more than 3*10^17 of these
numbers before reaching the 10^19-th digit.
Maximilian.
__________
Update
of January 13th, 2009: this is now A154328 in the
OEIS
Back to main page, here.