## Sunday, December 25, 2011

### Digit pick-up

Consider the multiplication table for the number 125. For each product, we will pick up any digits thereof we have not already collected and add them to a growing list. When will we have collected all ten digits?

1  125  +1 +2 +5 => {1,2,5}
2  250        +0 => {0,1,2,5}
3  375     +3 +7 => {0,1,2,3,5,7}
4  500
5  625        +6 => {0,1,2,3,5,6,7}
6  750
7  875        +8 => {0,1,2,3,5,6,7,8}
8 1000
9 1125
10 1250
11 1375
12 1500
13 1625
14 1750
15 1875
16 2000
17 2125
18 2250
19 2375
20 2500
21 2625
22 2750
23 2875
24 3000
25 3125
26 3250
27 3375
28 3500
29 3625
30 3750
31 3875
32 4000        +4 => {0,1,2,3,4,5,6,7,8}
33 4125
34 4250
35 4375
36 4500
37 4625
38 4750
39 4875
40 5000
41 5125
42 5250
43 5375
44 5500
45 5625
46 5750
47 5875
48 6000
49 6125
50 6250
51 6375
52 6500
53 6625
54 6750
55 6875
56 7000
57 7125
58 7250
59 7375
60 7500
61 7625
62 7750
63 7875
64 8000
65 8125
66 8250
67 8375
68 8500
69 8625
70 8750
71 8875
72 9000        +9 => {0,1,2,3,4,5,6,7,8,9}

So, it takes 72 multiplications before we've bagged all ten digits. In base ten, it turns out that 72 is the largest number of multiplications required for any given starting number.

What is the largest number of multiplications required in base b? Tomas Rokicki has worked them out for thousands of bases: It's the second number on each line in his list. I felt that these maxima (k) deserved to be graphed. Noting that in composite bases k is divisible by (b-1), I decided to do another graph of k/(b-1). Then, to explicitly list the k/(b-1) straight-line points, I did the families, with a question at the end.