Crea sito
COUNTING ONES


Numbers can be written in different ways, called "representations". For instance the number eleven is written "11" in base 10. The word "eleven" is the representation of the number in the english language. Its Roman representation is "XI".

Let's stick to algebraic representation of numbers, ie, representations with a finite alphabet of symbols (digits). The size of this set is the "base" of the representation. Common bases in computer are 10, 2, 16 (hex number). The number eleven is "1011" in base 2, and "B" in base sixteen.

Let G(N,D,B) be the number of times the digit D occurs in the representations base B of all the numbers between 0 and N. For example if B=3, the function G has the values listed in the table below

N 1 2 3 4 5 6 7 8 9 10
Representation 1 2 10 11 12 20 21 22 100 101
G(N,1,3) 1 1 2 4 5 5 6 6 7 9
G(N,2,3) 0 1 1 1 2 3 4 6 6 6

Prove that the numbers for which G(N,1,B) = N are finitely many. More precisely prove that the last one has representation in base B 11...110, with B-1 digits "1".
Definetely not well polished, but here is a proof.

Prove that, for B>2, the numbers for which G(N,B-1,B) = N is B-1, and the number for which G(N,B/2,B) = N is B/2 (here B/2 is rounded down, eg, for B=9, B/2=4).

Is there any other intriguing property in the numbers that satisfy the relation G(N,D,B) = N? And in their number? The table below list their number for the smallest bases (i cannot guarantee the correctness of the values).

Numbers D = 1 2 3 4 5 6 7 8 9
B = 3 5 2 - - - - - - -
4 9 2 3 - - - - - -
5 5 2 18 4 - - - - -
6 22 16 3 28 5 - - - -
7 6 6 3 12 35 6 - - -
8 46 20 30 4 50 114 7 - -
9 50 26 6 4 60 66 273 8 -
10 84 14 36 48 5 72 48 344 9
11 11 8              

As far as i can see every number is a multiple of the digit D. This second table lists these multiples. It seems that this is a general fact. Try to prove it.

Multiples D = 1 2 3 4 5 6 7 8 9
B = 3 5 1 - - - - - - -
4 9 1 1 - - - - - -
5 5 1 6 1 - - - - -
6 22 8 1 7 1 - - - -
7 6 3 1 3 7 1 - - -
8 46 10 10 1 10 19 1 - -
9 50 13 2 1 10 11 39 1 -
10 84 7 12 12 1 12 7 43 1
11 11 4              

Marco Corvi - 2005