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.
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
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.