A self-referencing number problem

The mathematician Raphael Robinson posed this problem:

This table contains: ... times the digit    0
... times the digit    1
... times the digit    2
... times the digit    3
... times the digit    4
... times the digit    5
... times the digit    6
... times the digit    7
... times the digit    8
... times the digit    9

The numbers on the left have to be filled in so that the sentence in the table is true.

Here i will give:

a generalization of the problem
a recursive approach
an exhaustive research
a program in C
all the solutions

Generalization of the problem

The general table that will be examined here is:

This table contains: x₀ times the digit 0

...

x_b-1 times the digit b-1

in base b.

A recursive approach

An intuitive approach to find solutions is, to fill the left side of the table with an arbitrary b-plet of numbers ( x₀ , x₁ , ... x_b-1 ) , and then count the numbers of digit zeros, ones, ... - giving new numbers ( x'₀ , x'₁ , ... x'_b-1 ) .
If the numbers x' and x are the same, we have a solution; otherwise we repeat the process with ( x'₀ , x'₁ , ... )

Sometimes, this process will lead after several iterations to a solution; but it may also cycle without giving a solution, for example (1,7,4,1,1,1,1,1,2,1) - (1,8,2,1,2,1,1,2,1,1) is one cycle in base 10 .

An exhaustive research

The recursive method may provide all the solutions when applied to many random starting points, but then other considerations must be used to know when all the solutions have been found.

Therefore, i will use another exhaustive method: starting with every possible (sufficient) p-plet (x₀ ,...), and check wether it is a solution, but NOT applying an iterative process on these numbers.

First, it is necessary to delimit the numbers, finding a maximum value for each of the x_i. Such a limit must exist, because even if the number x_i is very large, and i count the different zeros, ones, ... in the b-cimal representation of x_i , these frequences are much smaller numbers than x_i itself.
1. length (number of digits) of a number n in base b:
[ log_b(n) ] where [ ] is the integer part
2. if x₀ , x₁ , ... , x_b-1 <= M, the x_i have together at most
b . [ log_b(M) ] digits
3. in the extreme case, when all these digits are the same, then this digit appears
1 + b . [ log_b(M) ] times in the table
4. now choose M such that
M >= 1 + b . ( 1+ log_b (M) )
( because [ log_b(M) ] <= 1 + log_b (M) , this assures, if all the x_i <= M, then x'_i <= M)
5. to solve this inequality, study the function
f(x) = x - 1 - b . (1 + log_b (x))
when x goes from 0+ to +oo , f goes from -oo to +oo
So, it is possible to pick M as the first integer for which f(M)>0.

Here is the table of results:

b 2 3 4 5 6 7 8 9 10 11 12 16 20 36 100 1000 10000

M 10 11 13 15 17 19 21 23 25 28 30 38 47 82 218 2110 20796

Another reflection allows to reduce the b-plets, by requiring
0 < x₀ <= x₁ <= ... <= x_b-1
and calculating x'₀, x'₁, ... ,
then rearrange the x'_i in ascending order and compare with x₀, x₁, ...
When they match, then the initial x'₀, x'₁, ... is a solution.

The program

selfref.c is a program to find the solutions in base b = 4, 5, 6, 7, 8, 9, 10. It can be adapted for other cases.
It is written in C, was compiled with gcc and run under Linux.

Solutions found

All the results are given in base 10.

base 2: (3,4)
base 3: (1,4,2), (2,2,3), (3,3,2)
base 4: (1,5,2,1), (1,3,1,3), (1,2,3,2)
base 5: (1,6,2,1,1), (1,3,2,3,1)
base 6: (1,7,2,1,1,1)
base 7: (1,8,2,1,1,1,1), (1,4,3,2,2,1,1)
base 8: (1,9,2,1,1,1,1,1), (1,5,3,2,1,2,1,1)
base 9: (1,10,2,1,1,1,1,1,1), (1,6,3,2,1,1,2,1,1)
base 10:(1,11,2,1,1,1,1,1,1,1), (1,7,3,2,1,1,1,2,1,1)

Notes
1. A brief consideration of the curious base 1:
In base 1, each number n writes as | | | ... | , a series of n strokes. The problem in base 1 announces as:

This table contains:
... times the stroke |

If there are n strokes on the left side (n=0, 1, ...), then with the stroke on the right side, the table has in total (n+1) strokes, which always contradicts with the statement.
Thus, in base 1, the problem has no solution!

2. Both solutions for base 7, 8, 9, 10 can be written in a general form and apply for each base b:
if b >= 3: (1,b+1,2,1,1, ...,1) (the last b-3 numbers are ones)
if b >= 7: (1,b-3,3,2,1*,1*, ...,1*) (* the last b-4 numbers are all ones, except x_b-3 = 2 )

Link:
Le jeu de Robinson is another discussion in French about this problem.

Homepage: www2.vo.lu/homepages/phahn
Patrick Hahn - 23.06.2003

b	2	3	4	5	6	7	8	9	10	11	12	16	20	36	100	1000	10000
M	10	11	13	15	17	19	21	23	25	28	30	38	47	82	218	2110	20796