Self-Referential Puzzles - Solutions

Solutions were received from Denis Borris, Kirk Bresniker, Dave Ellis, Bert Sevenhant, and Phillipe Fondanaiche. The solutions are included with the puzzle descriptions below.
Update 4/22/03: Mark Moyer pointed out there are more "answers" to the initial puzzle "How many letters are in the answer to this question?":

Eight plus five.
Exactly twenty-four letters.
Roughly twelve.
At least ten.
If you're counting letter tokens, then eighty-one, but if you're counting letter types, then eighteen.
Just one more than are in the question to this answer!

Spelling puzzles

From Philippe Fondanaiche:
Digit Puzzles (fill the blanks with digits 0-9, or possibly multi-digit numbers): From Philippe Fondanaiche:
Self-Referential Numbers
213 can be described as having "One 1, One 2, One 3", or 111213. In a successive list, with each line describing the previous, we get:
11 12 13
41 12 13
31 12 13 14
41 12 23 14
31 22 13 24
21 32 23 14
... and the last number (21322314) describes itself.
Update 10/3/00 - Ulrich Schimke sent several more analyses to add to the self-referential numbers:
I found your article about self referential numbers in 980608 and I have some 
facts to supplement. 
To shorten things I denote with T the describing operator for integers, so 
T(1334) = 112314, T(22) = 22 and so on. 

1) There are exactly 109 fixed-points (= self-refential numbers), i.e. n with 
T(n) = n. I examined this topic about a year ago and sent this sequence to 
Neil Sloane. They are sequence A047841, see 
The reason I found your page was my search about this topic using some of 
these fixed-points as input for a search engine e.g. 21322314.     

2) You ask if the list always ends in fixed-point or a cycle. The answer is 
Yes. This is a consequence from 2 facts: A) For every n with more than 21 
digits T(n) < n is valid and B) For every n with not more than 21 digits, 
T(n) has also not more than 21 digits. As a consequence the sequence n, T(n), 
T(T(n)) ... enters and than remains in the bounded area from 1 to 10^21, so 
it must end in a cycle (see a fixed-point as a 1-cycle) 
To show A) and B) consider that T(n) has a maximum nuber of digits if the 
digits in n are distributed as equal as possible. If you have for example 
already 100 '2's in n you need another 900 '2's to "generate" a new digit in 
T(n). But if you have just 10 '2's in n you need only 90 other '2's to get a 
new digit in T(n). If n has k digits, T(n) reaches the maximum number of 
digits if eyery digit occurs at least int(k/10)-times. This leads to A) and 

3) You ask if the number of steps until a list with a certain integer as 
start can have a length > 21. The answer is the list can be abitrarly large. 
For every a(1) > 22 not ending with a zero, there is a a(2) > a(1) with 
T(a(2)) = a(1) and a(2) not ending with a zero as well. Iterating this 
process you find a sequence of numbers a(1) < a(2) < a(3) < a(4) < .. with 
T(a(2)) = a(1), T(T(a(3)) = a(1), T(T(T(a(4))) = a(1) and so on. So the 
"pre"-phase before reaching the cycle can be abitrarly large, because the 
cycle doesn't start until a(1). Finding a(2), a(3), ...  is easy: Let's start 
e.g. with a(1) = 41.  Then a(2) is of course 1111. a(3) is 11111......111111 
(the number consisting of 111 '1's). a(4) is the integer consisting of 
(10^111-1)/9 '1's and so on. 

4) I don't know if there are any terminating cycles with lengths other than 1 
or 3. One has "only" to examine all numbers smaller than 22 digits. But this 
is too much for a progam. But if you start examining all numbers beginning 
with 1 you can stop examining a number n if T(n) < n cause T(n) has already 
be checked. This reduces the nessecary run time for the program, but I think 
this is still too much.

If you find other puzzles of this sort, feel free to submit them. I'll add them when I can.

Source: Unless noted, these are original.

Mail to Ken