Digit chaos in a window

Hello SeqFans,

a(n) is the size of the largest possible window which includes a(n) itself and a(n) non-repeated digits.

S = 1 2 3 4 5 6 7 8 9 10 6 5 7 4 8 3 9 6 5 7 4 3 2 8 6 5 7 4 3 2 6 5 4 3 2 1 7 8 9 6 ...

| | | | | | | | |  | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |

1 1 1 1 1 1 1 1 1  2 7 9 8 6 9 4 1 7 8 4 6 7 3 9 7 3 4 6 7 3 5 4 2 5 3 1 6 6 6 2

2 2 2 2 2 2 2 2  3 8 1 9 5 1 8 0 4 3 8 5 4 2 6 4 2 3 5 4 2 7 3 6 4 2   5 5 5 1

3 3 3 3 3 3 3  4 9 0 1 7 0 3 6 8 9 3 7 3   5 3 8 2 7 3   4 2 5 3     4 4 4 7

4 4 4 4 4 4  5 1 6 0 4 6   5 3 6 9 4     7 2 6 8 4     3 6 4       3 3 3 8

5 5 5 5 5  6 0 5 6   5   7 9 5 6       4 8 5 6       2 5         2 2 2 9

6 6 6 6  7 6   5   7   4 6   5       3 6   5       6           1 1 1 6

7 7 7  8     7   4   8     7       2     7                   7 7 7

8 8  9         8   3             8                           8 8

9  1             9                                           9

0

Unless I’ve made errors in computing this, I don’t see any pattern yet: when will it arise?

Best,

É.

[18th of August, 2010]

----------

Alex M. quickly replied:

> Would you please elaborate? From what I see, each column is generated by taking the previous column and adding a number to the end of it... the number of digits taken is equal to the number appended to the end of the column ("window"?), and the number in the final S is equal to the size of the window.

I do not see, however, ...

Oh wait! I think I understand. Let me ask if I have this correct:

The "6" window is a "6" because after appending a 5 to the end, the longest window with no repeated digits would be "6 7 8 9 1 0 5", which is 7 digits long. It doesn't work, because it has to include at least 5 digits.

Similarly, it cannot be 7, because that would result in "8 9 1 0 7", which is 5 digits long. It doesn't work either, because using a size-6 window will produce more digits. 6, however, has exactly 5 digits before it that are not 6's, so it works... okay... I think I get it now...

I think this sequence will have to repeat eventually; considering that all numbers will be less than 11, each new number can only depend on the 10 previous, maximum. This leaves a maximum of 10^10 states to cycle through. So, eventually, it will have to reach a cycle.

Thanks, Alex!

A simple (?) way to describe this sequence would be:

 Every a(n) says: “The a(n) digits on my left (mine included) are all different”.

Example with 10: “The 10 digits on my left, including mine, are different”;

this is true, the “window” being [2 3 4 5 6 7 8 9 1 0].

Example with 6, immediately after 10: “The 6 digits on my left, including mine, are different”;

this is true, the “window” being [7 8 9 1 0 6].

The difficulty in building S step by step [starting from a(1)=1] is that we have always to maximize the next a(n).

Then came David S.:

>If I understand it correctly, after a(24) = 8, a(25) should be 10 not 6?

>The digit chaos algorithm seems to sort the digits into descending order.

>Dave

Gee, you have a point, Dave! Back to the drawing board!

... and after many hesitations/corrections, we got this; S enters in a loop at a(39); the size of the loop is 10:

n = 1 2 3 4 5 6 7 8 9  1  1 1 1 1 1 1 1 1 1 2 2 2 2 2  2  2 2 2 2 3 3 3 3  3  3 3 3 3 3 4 4 4  4  4 4 4 4 4 4 5 5  5  5 5 5 5 5 5 5

0  1 2 3 4 5 6 7 8 9 0 1 2 3 4  5  6 7 8 9 0 1 2 3  4  5 6 7 8 9 0 1 2  3  4 5 6 7 8 9 0 1  2  3 4 5 6 7 8 9

S = 1 2 3 4 5 6 7 8 9 10 6 5 7 4 8 3 9 6 5 7 4 3 2 8 10 9 7 6 5 4 8 3 2 10 9 7 6 8 5 4 3 2 10 9 8 7 6 5 4 3 2 10 9 8 7 6 5 4 3 ...

| | | | | | | | |  | | | | | | | | | | | | | | |  | | | | | | | | |  | | | | | | | | |  | | | | | | | | |  | | | | | | | |

1 1 1 1 1 1 1 1 1  2 7 9 8 6 9 4 1 7 8 4 6 7 3 9  9 5 3 8 0 7 1 4 3  9 6 8 2 3 9 6 5 3  9 6 5 3 1 9 7 5 3  9 7 5 3 1 9 7 5

2 2 2 2 2 2 2 2  3 8 1 9 5 1 8 0 4 3 8 5 4 2 6  6 7 2 1 9 6 0 8 2  7 5 3 1 2 7 8 4 2  7 8 4 2 0 8 6 4 2  8 6 4 2 0 8 6 4

3 3 3 3 3 3 3  4 9 0 1 7 0 3 6 8 9 3 7 3   5  5 4 8 0 7 5 9 3    6 4 2 0 1 6 5 3    6 5 3 1 9 7 5 3    7 5 3 1 9 7 5 3

4 4 4 4 4 4  5 1 6 0 4 6   5 3 6 9 4     7  7 3 1 9 6 4 7      5 8 1 9 0 8 4      8 4 2 0 8 6 4      6 4 2 0 8 6 4

5 5 5 5 5  6 0 5 6   5   7 9 5 6       4  4 2 0 7 5   6      4 3 0 7 9 5        5 3 1 9 7 5        5 3 1 9 7 5

6 6 6 6  7 6   5   7   4 6   5       3  3 8 9 6     5      8 2 9 6 7          4 2 0 8 6          4 2 0 8 6

7 7 7  8     7   4   8     7       2  2 1 7       4      3 1 7   6          3 1 9 7            3 1 9 7

8 8  9         8   3             8  8 0         8      2 0     8          2 0 8              2 0 8

9  1             9                1 9                1 9                1 9                1 9

0                              0                  0                  0                  0

Are there other such loops?

Many thanks to all contributors!

Best,

É.