5
$\begingroup$

There is a famous puzzle that asks for the next line (and the rule) for the following pattern:

1
11
21
1211
111221
...

The solution to this puzzle is:

312211, because each line describes the line before it. The first line has one '1', and so the second line is 11 (one '1'). The second line has two '1's (21) and so the third line is 21.

Now, the question is:

Is there a starting point, which would come back to itself? In other words, can you find a starting point and then run this rule over and over again and come back to the starting point (so it forms a closed cycle)?

Some clarifications. Usually, the numbers (after the first) will have an even number of digits. But not always. For example, 11111111111 -> 111.

There is at least one solution to this puzzle. But are there more?

$\endgroup$
  • $\begingroup$ I don't think 11111111111 -> 111 is a usual convention for this sequence. If I recall correctly, the sequence is normally defined completely independent of the used number base, by treating each "digit" really as its own natural number. So then, 11111111111 -> (11)1 -> 1(11)11 and so on (which is really just a shorthand for 1,1,..,1 -> 11,1 -> 1,11,1,1). If you explicitely want the effects of treating everything as base 10, then you should probably clarify that. $\endgroup$ – ManfP Sep 26 at 11:12
  • $\begingroup$ @ManfP: Perhaps the sequence could be expressed in "base 1", with a delimiter, so it would start 1; 1.1; 11.1; 1.11.1.1; 1.1.1.11.11.1; 111.1.11.11.1.1; 1.111.1.1.11.11.11.1; 1.1.1.111.11.1.111.11.1.1. That would introduce the question of what sequences would shrink. 1.1.1.1->1111.1 would go from seven characters to six, but most sequences would stay the same size or grow. $\endgroup$ – supercat Sep 26 at 17:47
  • $\begingroup$ @supercat What you are doing is just another notation for the same "standard" way of doing it: The individual terms are basically just finite integer sequences, so where you write 111.1.11.11.1.1 I would just write (3,1,2,2,1,1). 312211 is just a shorthand for that, although a shorthand that only works if all elements are 9 or less. And your notion of "length" is just "length+sum" in the standard notation. $\endgroup$ – ManfP Sep 26 at 17:53
  • $\begingroup$ The issue with the question (and current answers) is however that OP apparently wants to treat "eleven" the same as "two ones", which is not just a notational issue but leads to different sequences than the "standard results" are valid for. I don't expect different results, but it's still something one would technically have to proof. $\endgroup$ – ManfP Sep 26 at 17:58
  • $\begingroup$ @ManfP: The question of what bases would allow additional looping sequences might be a little more interesting. In base 2, without delimiters, 111->111 is a looping sequence, and a 111 which is preceded and followed by zeroes will expand to something starting with 1111, which is of length greater than three. I don't think there are any other non-trivial loops in base 2, or any other loops other than 22 in higher basis, but I think a somewhat different (albeit perhaps simpler) proof would be needed for base 2. $\endgroup$ – supercat Sep 26 at 18:42
7
$\begingroup$

The answer is

Yes, and its a very short loop. Only one such number exists, as proved here.

The starting number:

22.

The next number is then 2 twos = 22, so we already have a closed loop of just length one.

| improve this answer | |
$\endgroup$
7
$\begingroup$

The kinda-famous

"cosmological theorem", proved by J H Conway and then re-proved by Ekhad and Zeilberger (note: "Ekhad" is Shalosh B Ekhad, Zeilberger's computer, so-called because the first computer he named as a collaborator in one of his computational mathematics papers was a 3b1 and in Hebrew 3 is shalosh and 1 is ekhad)

tells us that

any starting configuration, after enough iterations, yields a concatenation of substrings chosen from 92 "common elements" (what a nice coincidence that the number is 92!) whose digits are all 1,2,3, and 12 "transuranic elements" with digits bigger than 3 (there are two for each such digit, each consisting of a certain lengthy string of 123-digits followed by the digit in question)

where

each of those "elements" then turns into some concatenation of elements -- and in every case other than 22 ("hydrogen") which maps to itself, it maps to something strictly longer than itself

and therefore

any starting point other than 22 (or, I guess, the empty string) will grow indefinitely and hence cannot repeat.

So

22 and the empty string are the only starting-points that lead to loops, and in each case the loop is trivial.

| improve this answer | |
$\endgroup$
2
$\begingroup$

Allowing for inefficiency in the descriptions of digits, here are 12 digit sequences that describe themselves and cannot be decomposed into smaller solutions.

22, 333000, 33311110, 33311111, 33311112, 33311113, 33311114, 33311115, 33311116, 33311117, 33311118 and 33311119

Allowing for infinitely long periodically repeating sequences as well, here are 8 trivial indecomposable periodically repeating infinite solutions until more interesting ones crop up.

111..., (222... is decomposable into repeats of the solution 22,) 333..., 444..., 555..., 666..., 777..., 888... and 999...

All of these digit sequences describe themselves in just one iteration and were readily derived after realizing that a self-describing solution must repeat its first digit when that digit is not 0.

The search continues for inefficient solutions that begin with 0 and/or that return to themselves after multiple iterations of description.

| improve this answer | |
$\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.