Surely the leading (= left-most) digit of a positive integer is an obvious thing? Just stare at the integer (e.g. 7823) and observe the left-most digit (7, and in this example)?

Suppose, clinic however, that you wanted to find the leading digit of a very large list of positive integers, a list so large it was hard to impossible to peruse by eye? How could you write an algorithm to compute the leading digits? Even more, suppose you wanted to come up with a mathematical argument that involved determining the leading digit of an otherwise unspecified positive integer?

In a short and lovely mathematical argument, Dave Radcliffe (@daveinstpaul) proves that there are exactly 18266 distinct ordered lists of values

(leading digit of 2^{n}, … , leading digit of 9^{n})

as n ranges over the infinite set of positive integers.

A key part of his argument is that the leading digit of a^{n} is completely determined by the fractional part of n×log_{10}(a).

How might we see this?

Let’s make a table of values and see if something pops out:

k | fractional part of log_{10}(k) |

1 | 0. |

2 | 0.30103 |

3 | 0.477121 |

4 | 0.60206 |

5 | 0.69897 |

6 | 0.778151 |

7 | 0.845098 |

8 | 0.90309 |

9 | 0.954243 |

10 | 0. |

11 | 0.0413927 |

12 | 0.0791812 |

13 | 0.113943 |

14 | 0.146128 |

15 | 0.176091 |

16 | 0.20412 |

17 | 0.230449 |

18 | 0.255273 |

19 | 0.278754 |

20 | 0.30103 |

Nothing obvious, so what does Dave Radcliffe mean by “the leading digit of a_{n} is completely determined by the fractional part of n×log_{10}(a)”?

Let’s think about how we can algorithmically determine the leading digit of an integer written base 10.

Suppose k is a positive integer that is of the form a_{p}a_{p-1}…a_{1}a_{0} base 10.

That is, the a_{i} are digits base 10 (i.e. one of 0, 1, 2, 3, 4, 5, 6, 7, 8, 9) and a_{p} is not 0, because it is the leading digit.

What every school child does not immediately recall is that this means

k = a_{p}10^{p }+ a_{p-1}10^{p-1} +… + a_{1}10 + a_{0}

So 10^{p }is no bigger than k, which in turn is less than 10^{p+1 }:

10^{p }≤ k < 10^{p+1}

Therefore,

log_{10}(10^{p }) ≤ log_{10}(k) < log_{10}(10^{p+1})

because the logarithm is an increasing function.

In other words,

p ≤ log_{10}(k) < p+1

which means that p is the greatest integer less than or equal to log_{10}(k) – that is the floor of log_{10}(k): p=Floor[log_{10}(k)].

Now if we divide k by 10^{p }we get:

k/10^{p} = a_{p} + 0.a_{p-}…a_{1}a_{0} (base 10)

which means a_{p} = Floor[k/10^{p}] = Floor[k/10 ^{Floor[log}_{10}^{(k)]} ]

We can express Floor[log_{10}(k)] in terms of the fractional part { log_{10}(k)} of log_{10}(k) simply as

Floor[log_{10}(k)] = log_{10}(k) – { log_{10}(k)}

So,

10 ^{Floor[log}_{10}^{(k)]} = 10^{log}_{10}^{(k) – {log}_{10}^{(k}}} = k/10^{{log}_{10}^{(k}}}

which, upon substituting into the expression above for a_{p}, gives:

a_{p} =Floor[10^{{log}_{10}^{(k}}}]

This is the precise sense in which the leading digit, a_{p}, of k is determined by the fractional part {log_{10}(k} of log_{10}(k).

When k= a^{n}, this is just the fractional part of n×log_{10}(a).

Going back to the table above, and including a third column of Floor[10^{{log}_{10}^{(k}}}], we get:

k | fractional part of log_{10}(k) |
Floor[10^{{log}_{10}^{(k}}}] |

1 | 0. | 1 |

2 | 0.30103 | 2 |

3 | 0.477121 | 3 |

4 | 0.60206 | 4 |

5 | 0.69897 | 5 |

6 | 0.778151 | 6 |

7 | 0.845098 | 7 |

8 | 0.90309 | 8 |

9 | 0.954243 | 9 |

10 | 0. | 1 |

11 | 0.0413927 | 1 |

12 | 0.0791812 | 1 |

13 | 0.113943 | 1 |

14 | 0.146128 | 1 |

15 | 0.176091 | 1 |

16 | 0.20412 | 1 |

17 | 0.230449 | 1 |

18 | 0.255273 | 1 |

19 | 0.278754 | 1 |

20 | 0.30103 | 2 |

Or, if we should do this for k = 2^{n} for varying n, we get a table that begins as follows:

n | 2^{n} |
fractional part of n ×log_{10}(2) |
Floor[10^{{n}^{×log}_{10}^{(2}}}] |

1 | 2 | 0.30103 | 2 |

2 | 4 | 0.60206 | 4 |

3 | 8 | 0.90309 | 8 |

4 | 16 | 0.20412 | 1 |

5 | 32 | 0.50515 | 3 |

6 | 64 | 0.80618 | 6 |

7 | 128 | 0.10721 | 1 |

8 | 256 | 0.40824 | 2 |

9 | 512 | 0.70927 | 5 |

10 | 1024 | 0.0103 | 1 |

11 | 2048 | 0.31133 | 2 |

12 | 4096 | 0.61236 | 4 |

13 | 8192 | 0.91339 | 8 |

14 | 16384 | 0.21442 | 1 |

15 | 32768 | 0.51545 | 3 |

16 | 65536 | 0.81648 | 6 |

17 | 131072 | 0.11751 | 1 |

18 | 262144 | 0.41854 | 2 |

19 | 524288 | 0.71957 | 5 |

20 | 1048576 | 0.0205999 | 1 |

in precise agreement with Dave Radcliffe’s assertion.

## Speak Your Mind