How many numbers less than ten thousand contain a five?

My fiance is taking what amounts to an Intro to Number Theory course this term. She was struggling with a question and asked me to look at it. The truth be told, I struggled with this one for a long while before I got it. It turned out to be a pretty interesting problem.

How many numbers less than 10000 contain a “5”?

In other words, how many numbers contain the string “5”, as in 5, 105, 500, etc.

At first I tried to count it up on paper. 1 to 100 had 11 5’s.

• 5
• 15
• 25
• 35
• 45
• 50
• 55
• 65
• 75
• 85
• 95

Which gave me 11, but wait a minute… That’s not quite right. I missed all of the numbers in the 50’s. That means, in 1 to 100, there are 10 5’s in the 50’s and 9 5’s elsewhere. This totals to 19 fives from 1 to 100. Ok, now I need to add up all of the fives from 1 to 1000…. Hold up. I’m a programmer. I can code this!! Why am I doing this by hand?

The first obvious solution is to loop through each number from 1 to 10,000 and see if it contains a five. It was late and I didn’t feel like getting my laptop out, so I decided to use the ruby program I have on my iPhone. (It’s free in the app store.  For Ruby  by tayutec.com if anyone’s interested.)  I came up with the brute force method below, but my iPhone would crash every time I tried to run more than 1000 loops through the method.  The old iPhone just doesn’t have enough memory to brute its way through. There has to be a better way.

#brute force method to find how many numbers contain a five in a given range
arr = Array.new
for n in 1..1000
    #cast n to string and check to see if any of the characters is a "5"
    if n.to_s.include?5 then
        arr.push n
    end
end
#the length of the array is the count of numbers that contain a "5"
puts arr.length

I got the results below from this method.

• [1-10] = 1 five
• [1-100] = 19 fives
• [1-1000] = 271 fives

Like I said, my phone would crash if I tried many more than 1000. That’s ok though. This was enough for me to perceive a pattern. It took me a little while to get it, but once I wrote it down this way, it was pretty apparent. Let’s rewrite this a little bit and see if we can’t figure out what’s going on here.

• 1 to 10 = 1
• 1 to 100 = 19 = (1*9) + 10 [If you recall, earlier I discovered that there were 10 from 50, and 9 elsewhere.]
• 1 to 1000=271 = (19 * 9) + 100 [So this means we that we have 9 instances of 19, and another 100 from the 500’s.]

From here we can generalize the algorithm.

f(x) = (y*9) = (x/10)

Where y is the previous result and x is the end number of the range.

i.e. y = 1 and x = 100, or y = 19 and x = 1000

Finally, armed with our new algorithm, we’re ready to write a more elegant solution.

#the classy way to do it
def nc5(pwr)
# prints on screen the count of numbers containing a "5"
# pwr = the power of ten you wish to calculate to

    prev = 0
    for in in 1..pwr
        prev = (prev*9) + (10**i)/10 # x**y is ruby's syntax for "x to the power of y"
        puts prev
    end
end

#call function
nc5(4) # 10^4 = 10000

This outputs:

1
19
271
3439

The best part is that I can run this code with my phone’s limited memory resources. No more crashing. I was actually able to run this out to 10^100 and suspect I could go much further. It was actually really nice to face a memory issue. In today’s age, we take it for granted that we have enough processing power and memory to brute force our way through, and typically, we’re right. I, for one, am a little jealous of those old timers out there that had to write better code because of such limitations. If I had busted out my laptop and visual studio, I would have never been forced to find a much more elegant and efficient solution to the problem.

Excel SQLConcat Function Revisited

My original post on my SQLConcat function has received some traffic, but the code had a pretty serious error in it. This was due to my previous lack of understanding about VBA’s IsMissing() function.  I’ve also added some extra functionality to the code to allow for adding parenthesis along with quotes. The added functionality makes it easier to adhoc insert statements like this.

Insert into [tbl] ([col1],[col2])
Values (1,'hello'),(2,'world')