An ugly self-describing sequence.

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:

- 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,

Lets 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:

- 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.