Leading Zeros (Updated)

Earlier this year I was helping a student with a decimal problem where he was struggling with the idea of dropping a trailing zero. I mentioned that after any decimal you could write an infinite number of zeros without changing the meaning of the number. I then blurted out that you could also add an infinite amount of zeros before any number greater than one* without changing the meaning of that number. I am not sure I had ever thought of this before. I call this lazy knowledge: you don't actually know it but it is so obvious that you will figure it out as soon as you bother to think about it.

* Obviously this can be applied to numbers less than -1 as well.


This realisation stood to me recently when I was trying to figure out the number of times a digit would have appeared between 0 and n. My first step was to calculate how many digits there are in total between 0 and 99: 10 * 1 + 90 * 2 = 190. That would mean that each digit appears 19 times. When I calculated this for a specific digit though I realised that it should be twenty. Each number appears 10 times in the unit column and ten times in the tens column - for two that would be the ten numbers from 20-29. I had forgotten the leading 0. 0-9 should have been 00-99 - or if I was working with a three-digit number 000-009.

Once I made this observation a pattern began to emerge:


I will work with 11x22 where x is some digit. Left is the number to the left of the x and right is the number to the right of x. Since we are working with the hundred column we will be working in hundreds - I will call this the score. Let us say we are searching for the total occurrences of 5.

The important thing to note is that the the third column will not have a five until we reach five hundred and then its total will increase by 1 for every number until 599. The total will stay at 100 until we reach 1599, where the process will repeat again.

Therefore, where x is less than five, for example 11022 we can calculate the number of times x has occurred in that column using left * score = 1100.

Where x is greater than five, for example 11622, we have gone through the 500's one extra time so our total is (left + 1) * score = 1200.

Finally, when the digit is equal to five, for example 11522, we have the total for less than but need to add in from 11500 to 11522. This last part is given by 'right + 1' so the total is given by left * score + right + 1 = 1123.

Here is some sample output (the last two numbers are the total for this method and a brute force method):


Searching for total occurrences of 5 in numbers up to 14527

Order: 1 New Target: 14527
Digit: 7 Left: 1452 Right: 0
calculate greater than 1453

Order: 10 New Target: 1452
Digit: 2 Left: 145 Right: 7
calculate less than 1450

Order: 100 New Target: 145
Digit: 5 Left: 14 Right: 27
calculate equal 1428

Order: 1000 New Target: 14
Digit: 4 Left: 1 Right: 527
calculate less than 1000

Order: 10000 New Target: 1
Digit: 1 Left: 0 Right: 4527
calculate less than 0

5331 5331