The First Digit

must be added to the previous term

Hello Seqfans,

let a(n) be the sum of a(n-1) and a(n)'s first digit.

Example : a(n-1) = 597

a(n) = 603 (as 597 + 6 = 603)

This doesn't work sometimes:

Example : a(n-1) = 991

a(n) = ?

Is there an infinite such sequence?

If you start the sequence with 0,9,... you might be stuck: ..., 68, 75, 83, 92, ?

But there is a way to jump over 100: simply select this branch:

0,9,10,11,12,13,14,15,16,17,18,20,22,...

instead of:

0,9,10,11,12,13,14,15,16,17,18,19,21,...

The first branch leads to ..., 68, 75, 83, 92.

The second one to ... 54, 60, 66, 73, 81, 90, 99, 100, 101, ...

Best,

É.

__________

[Lars Blomberg]

Hello Eric,

This sequence obviously requires a backtracking algorithm. At a point where backing must take place, the sequence is saved and printed, provided it is longer than the previously saved sequence.

The sequences are presented in a compressed format so that:

> 0,9-19,21(5*2)29,32(3*3)38,42,46(3*5)56,62,68,75,83,92

... means:

> 0, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 21, 23, 25, 27, 29, 32, 35, 38, 42, 46, ...

The first column is the length of the sequence: 29, 311, 3139, 31428, 314324, 3143291.

The next term is the number of items in the sequence when it is compressed: 11, 17, 26, 35, 44, 53.

This gives:

29 11:

0, 9-19, 21(5*2)29, 32(3*3)38, 42, 46(3*5)56, 62, 68, 75, 83, 92.

311 17:

0, 9-18, 20(5*2)28, 31(3*3)37, 41(3*4)49, 54(3*6)66, 73, 81(3*9)99, 100-199, 201(50*2)299, 302(33*3)398, 402(25*4)498, 503(20*5)598, 604(16*6)694, 701(15*7)799, 807(12*8)895, 904(11*9)994.

3139 26:

31428 35:

314324 44:

0, 9-18, 20(5*2)28, 31(3*3)37, 41(3*4)49, 54(3*6)66, 73, 81(3*9)99, 100-199, 201(49*2)297, 300(34*3)399, 403(24*4)495, 500(20*5)595, 601(17*6)697, 704(14*7)795, 803(12*8)891, 900(12*9)999, 1000-1999, 2001(499*2)2997, 3000(333*3)3996, 4000(250*4)4996, 5001(200*5)5996, 6002(167*6)6998, 7005(143*7)7999, 8007(124*8)8991, 9000(112*9)9999, 10000-19999, 20001(4999*2)29997, 30000(3334*3)39999, 40003(2500*4)49999, 50004(1999*5)59994, 60000(1667*6)69996, 70003(1429*7)79999, 80007(1249*8)89991, 90000(1112*9)99999, 100000-199999, 200001(50000*2)299999, 300002(33333*3)399998, 400002(25000*4)499998, 500003(20000*5)599998, 600004(16666*6)699994, 700001(14286*7)799996, 800004(12500*8)899996, 900005(11111*9)999995

3143291 53:

0, 9-18, 20(5*2)28, 31(3*3)37, 41(3*4)49, 54(3*6)66, 73, 81(3*9)99, 100-199, 201(49*2)297, 300(34*3)399, 403(24*4)495, 500(20*5)595, 601(17*6)697, 704(14*7)795, 803(12*8)891, 900(12*9)999, 1000-1999, 2001(499*2)2997, 3000(333*3)3996, 4000(250*4)4996, 5001(200*5)5996, 6002(167*6)6998, 7005(143*7)7999, 8007(124*8)8991, 9000(112*9)9999, 10000-19999, 20001(4999*2)29997, 30000(3334*3)39999, 40003(2500*4)49999, 50004(1999*5)59994, 60000(1667*6)69996, 70003(1429*7)79999, 80007(1249*8)89991, 90000(1112*9)99999, 100000-199999, 200001(49999*2)299997, 300000(33334*3)399999, 400003(24999*4)499995, 500000(20000*5)599995, 600001(16667*6)699997, 700004(14286*7)799999, 800007(12499*8)899991, 900000(11112*9)999999, 1000000-1999999, 2000001(500000*2)2999999, 3000002(333333*3)3999998, 4000002(250000*4)4999998, 5000003(200000*5)5999998, 6000004(166666*6)6999994, 7000001(142857*7)7999993, 8000001(125000*8)8999993, 9000002(111111*9)9999992

After this, I ran out of memory.

By comparing the previous longest sequence to the current one, we get:

n A B C D

1 29

2 311 11 19 20

3 3139 178 299 300

4 31428 1810 2999 3000

5 314324 18138 29999 30000

6 3143291 181427 299999 300000

... where

n is just a count

A is the length of the sequence

B is the first index where they differ

C is the value of the previous sequence at B

D is the value of the current sequence at B

Apart from n=2 we have the same pattern, one must change 2999... to 3000... in order to make progress.

Whether this pattern continues, I don't know. But the fact that the sequences can be heavily compressed suggests a better algorithm where the compressed parts are not explicitly stored. Maybe a rainy day...

Regards

Lars B

__________

[Lars Blomberg] – Nov. 6^th, 2013

Hi again Eric,

As I hinted previously, there is a more memory-efficient way of computing this sequence, which I implemented using multiple-precision integers.

The result is in the attached text file.

Explanation of the columns:

Full count -- The full length of the sequence at the times explained previously. (Note that it is not the actual value, but the number of digits in it)

Compressed count -- The number of items in the sequence when it is compressed.

First difference at -- Index where the first difference occurs when comparing the previous and the current sequence. (Also number of digits)

Leading digit -- For example if there is 2999 in the previous sequence and 3000 in the current one, then a 3 is entered. All differences found have this form, with varying leading digits.

FullCount[n]-10*FullCount[n-1] -- Each collected sequence is approximately 10 times longer than the previous one.

Difference of previous -- Just the differences of the "FullCount[n]-10*FullCount[n-1] " data.

It turns out that these differences show a repeating pattern (apart from a few values in the beginning): 12, 5, 3, 9, 6, 7, ...

Furthermore there is a correspondence between this cycle and the "Leading digit" value so that Leading digit = 2, occurs for 12, 3 for 5, 6, 7, 9 and 9 for 3.

This pattern is the same up to a "Full count" of:

31432,980599,647266,313932,980599,647266,313932,980599,647266,

313932,980599,647266,313932,980599,647266,313932,980599,647266,

313932,980599,647266,313932,979820(1001)

When I divided the lines for readability, a remarkable pattern becomes apparent in the digits in this number. I have not investigated, but it must have to do with the repeating cycle discussed above.

Anyway, given the repeating cycle, it would seem that there is no limit to how long the sequence could be.

It is also fascinating to see the intricate properties and problems generated by rather simple rules (not implying that they are simple to invent!)

I guess someone with sufficient mathematical skills can find proof of the properties that I have found by numerical calculations.

Regards

Lars B

__________

[Lars Blomberg – complement] Nov. 7^th, 2013

Some more investigations:

Note that the transition from a number starting with 9 to a number starting with 1 is only possible when the first number is all 9's, that is one less than a power of 10, and by adding 1 we obtain that power of 10.

Starting with a number containing n 9's and working towards the beginning of the sequence, the terms are uniquely determined.

For example, starting with 9999, we subtract 111 9's to get 9000 and one more 9 to get 8991. Going forwards, both 8 and 9 are possible to add according to the rules, but in this case we must use 9, the larger of the two.

Working downwards, we eventually reach 1000, which we must, since as soon as the first digit is 1 we can subtract a number of 1's. And subtracting 1 once more we reach 999. So the process can be repeated with the number of digits decreased by 1.

For each transition from a lower to a higher leading digit we note if there is just one number possible (denote it by 0), or, if there are 2 numbers possible, which one must be used (denote them 1 or 2). Concatenating these digits for the 9 possible transitions we get a kind of signature.

Collecting all the signatures and the values of n that generate them for n=2,... 100 gives the following table:

1 200000000 16: 9,15,21,27,33,39,45,51,57,63,69,75,81,87,93,99

2 200000200 16: 8,14,20,26,32,38,44,50,56,62,68,74,80,86,92,98

3 200002200 17: 4,10,16,22,28,34,40,46,52,58,64,70,76,82,88,94,100

4 200020200 17: 3,6,12,18,24,30,36,42,48,54,60,66,72,78,84,90,96

5 200200020 1: 2

6 200200200 16: 5,11,17,23,29,35,41,47,53,59,65,71,77,83,89,95

7 202000020 16: 7,13,19,25,31,37,43,49,55,61,67,73,79,85,91,97

We see that when 2 choices are possible, the second, larger one must always be chosen, otherwise we will eventually get stuck.

Apart from n=2,3 there is a repeating cycle of 6 signatures, with n increasing by 6 for each of them.

By the same algorithm we can also calculate the number of terms in the sequence that have a specific number of digits.

1 2

2 27

3 282

4 2828

5 2828 9

6 2828 96

7 2828 967

8 2828 9682

9 2828 96825

10 2828 968253

11 2828 968253 9

12 2828 968253 96

13 2828 968253 967

14 2828 968253 9682

15 2828 968253 96825

16 2828 968253 968253

17 2828 968253 968253 9

18 2828 968253 968253 96

19 2828 968253 968253 967

20 2828 968253 968253 9682

21 2828 968253 968253 96825

22 2828 968253 968253 968253

23 2828 968253 968253 968253 9

24 2828 968253 968253 968253 96

25 2828 968253 968253 968253 967

26 2828 968253 968253 968253 9682

27 2828 968253 968253 968253 96825

28 2828 968253 968253 968253 968253

29 2828 968253 968253 968253 968253 9

30 2828 968253 968253 968253 968253 96

... which also shows some regularity.

From this it is evident that the sequence is infinite provided we always choose to add the larger of 2 possible numbers.

__________

Fascinating patterns & cycles, indeed, Lars, many thanks!

Best,