0
$\begingroup$

Consider the following alternative of the Look and Say sequence (OEIS A005150):

$u_0=N>0$

$u_{n+1}$ is the number of 1s then the number of 2s then ... then the number of 9s in $u_n$.

Example : $u_0=5,u_1=15,u_2=1115,u_3=3115,u_4=211315,u_5=31121315,u_6=41122315,u_7=3122131415,u_8=41122315,u_9=3132132415,u_{10}=3122331415,u_{11}=3122331415=u_{10},\dots$.

Notice how the sequence starts repeating after $u_{10}$.

Using a little python program, I found the following (see the data below for extra information):

  • for $1\le u_0\le 45$, the sequence repeats itself with a step of one (repetition of one term)

  • for $46\le u_0\le 56$, the sequence repeats itself with a step of two or less (repetition of two terms alternatively maximum)

  • for $57\le u_0\le 5988$, the sequence repeats itself with a step of three or less (repetition of three terms alternatively maximum)

  • I didn't check for higher numbers.

For any $u_0\ge1$, does the sequence have a finite number of images ?


Data for $1\le u_0\le 45$ (format : $u_0$,final number, first step where it repeats):

(1, '21322314', 13)

(2, '21322314', 12)

(3, '21322314', 13)

(4, '21322314', 9)

(5, '3122331415', 11)

(6, '3122331416', 11)

(7, '3122331417', 11)

(8, '3122331418', 11)

(9, '3122331419', 11)

(10, '21322314', 13)

(11, '21322314', 12)

(12, '21322314', 11)

(13, '21322314', 12)

(14, '21322314', 8)

(15, '3122331415', 10

(16, '3122331416', 10

(17, '3122331417', 10

(18, '3122331418', 10

(19, '3122331419', 10

(20, '21322314', 12)

(21, '21322314', 11)

(22, '22', 1)

(23, '21322314', 10)

(24, '31123314', 7)

(25, '31123315', 7)

(26, '31123316', 7)

(27, '31123317', 7)

(28, '31123318', 7)

(29, '31123319', 7)

(30, '21322314', 13)

(31, '21322314', 12)

(32, '21322314', 10)

(33, '21322314', 11)

(34, '21322314', 7)

(35, '3122331415', 9)

(36, '3122331416', 9)

(37, '3122331417', 9)

(38, '3122331418', 9)

(39, '3122331419', 9)

(40, '21322314', 9)

(41, '21322314', 8)

(42, '31123314', 7)

(43, '21322314', 7)

(44, '31123314', 8)

(45, '3122331415', 9)

$\endgroup$
2
$\begingroup$

Yes, the sequence always ends up at a cycle of finite length.

It is fairly easy to see that every number with 22 or more digits becomes strictly shorter by your modified look-and-say rule, so no matter which you start at, sooner or later you will end up below $10^{22}$, and then you will reach a number you have been at before after at most $10^{22}$ more steps.

$\endgroup$
3
  • $\begingroup$ What is the 'sort-and-describe rule'? I can't find anything about it on google. $\endgroup$ – Hippalectryon Apr 9 '15 at 18:42
  • $\begingroup$ @Hippalectryon: Clearer now? $\endgroup$ – hmakholm left over Monica Apr 9 '15 at 19:39
  • $\begingroup$ Yes, thanks a lot. $\endgroup$ – Hippalectryon Apr 9 '15 at 19:49
1
$\begingroup$

If multi-digit numbers are allowed, the game still ends in a cycle every time. This was proven in 1994 apparently: https://www.jstor.org/stable/2975323?seq=1#metadata_info_tab_contents

Interestingly, all the cycles I found by computer search fall into 1 of 7 families: $$1)\quad22$$ $$2)\quad2132231a\quad\text{with }a\ge4$$ $$3)\quad 3112331a\quad\text{with }a\ge4$$ $$4)\quad 3122331a1b\quad\text{with }a,b\ge4\text{ and }a\not=b$$ $$5)\quad 314213241a1b\quad\rightarrow\quad412223241a1b\quad\rightarrow\quad...\quad\text{with }a,b\ge5\text{ and }a\not=b$$ $$6)\quad 51222314251a1b\quad\rightarrow\quad41421314251a1b\quad\rightarrow\quad51221334151a1b\quad\rightarrow\quad...$$ $$\text{with }a,b\ge6\text{ and }a\not=b$$ $$7)\quad (n-1)14213141(n-1)2n1a_1...1a_{n-3}\quad\rightarrow\quad n12213242(n-1)1n1a_1...1a_{n-3}\quad\rightarrow\quad...\quad\text{with distinct }a_i\not\in\{1,2,4,n-1,n\}\text{ and }n\ge 6$$ That last one is pretty ugly so lemme give an example. Choosing $n=7$ and $a_1,a_2,a_3,a_4=3,8,10,384$ for examples gives us a two-cycle: $$61423141627181(10)1(384)$$ $$\downarrow$$ $$712213242617181(10)1(384)$$ $$\downarrow$$ $$...$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.