Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I wrote this a while back when my fiance was taking a Number Theory class. I wrote about it here and it recently came back to my attention. Anytime I write a for loop in Ruby I feel kind of dirty. I would like to "Ruby-ize" this routine if there is a more Ruby way to do it. Also, is this the most efficient algorithm for this?

Original Problem:

How many numbers less than 10000 that contain the digit 5 anywhere?

(Even thought the original problem was for < 10000, I've run this much farther out)

The algorithm:

\$f(x) = 9y + \dfrac{x}{10}\$

Where \$y\$ is the previous result and \$x\$ is the power of 10 we're checking against.

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

or, for the more mathematically inclined


The code:

def numbersContaining5(pwr)
# Prints on screen the count of numbers containing a "5"
#    for each power of ten up and including the one passed in.
# pwr = the power of ten you wish to calculate to

    prev = 0
    for i in 1..pwr
        prev = (prev*9) + (10**i)/10 
        puts prev

#call function
numbersContaining5(4) # 10^4 = 10000
share|improve this question
add comment

4 Answers 4

up vote 7 down vote accepted

I would use recurence in place of the loop - it is easier to understand the logic behind it then:

def number_containing_5(pwr)
  return 0 if pwr == 0
  number_containing_5(pwr-1) * 9 + 10**(pwr-1)
share|improve this answer
I never even considered recursion. Nice call. Are the underscores a Ruby convention? Should I not use camel case? –  ckuhn203 Jun 4 at 13:41
@ckuhn203 - That's correct. There is no lower camelCase in ruby, upper CamelCase is used for constants. Some developers like dividing constants from classes, by using UPPERCASE_NOTATION for constants and CamelCase for classes and modules (this is however quite artificial, as classes are just constants). –  BroiSatse Jun 4 at 14:23
Thank you for the clarification. I'll read up on the style conventions. –  ckuhn203 Jun 4 at 14:26
I suggest changing the base case to return 0 if pwr == 0. –  200_success Jun 4 at 18:07
For those that prefer pure expressions to imperative returns: pwr == 0 ? 0 : number_containing_5(pwr-1) * 9 + 10**(pwr-1) (or with if/else) –  tokland Jun 4 at 19:25
add comment

Not that using recursion is wrong, but there is an abstraction for what the algorithm does, a left fold with Enumerable#reduce:

def number_containing_5(power)
  (1..power).reduce(0) { |acc, n| (9*acc) + (10**n)/10 }
share|improve this answer
I should have waited to accept! That's exactly what I was looking for. I always forget about the reduce method. –  ckuhn203 Jun 4 at 19:53
add comment

So it turns out there is a better algorithm for this. The algorithm is \$10^n - 9^n\$ and you can find an explanation of it over on Mathematics Exchange. The improved algorithm completely removed my need for a loop, so I separated the test (printing) logic from the actual function and "ruby-ized" that loop instead.

def count_of_numbers_containing_5(power)

def test_it(pwr)
  (1..pwr).each {|i| puts count_of_numbers_containing_5(i)}

test_it 20
share|improve this answer
10 ** n - 9 ** n is a good solution for Ruby, where integers are unbounded. Be careful, though, with languages where ints can overflow, where the recursive solution may be better. –  200_success Jun 4 at 18:32
Good call @MarnenLaibow-Koser. –  ckuhn203 Jun 6 at 15:34
The reason this works is straightforward: there are 10^n numbers with n or fewer digits when the digits are drawn from the 10 digits 0-9, whereas there are 9^n numbers with n or fewer digits when the digits are drawn from the 9 digits 0,1,2,3,4,6,7,8,9. The difference is therefore the number of numbers with n or fewer digits that contain one or more 5's. –  Cary Swoveland Jun 7 at 3:12
add comment

this isn't exactly using your algorithm, but I think this does the trick.

(1..10000).select { |number| number.to_s.split('').any?{ |s| s == '5' } }
share|improve this answer
That is absolutely more ruby, but it's also brute force isn't it? –  ckuhn203 Jun 4 at 16:25
Benchmark it vs your algorithm. If the difference isn't that much, then I'd argue that more clear code is a better solution. But if you need to optimize, I fully understand. But yeah benchmark it and find out. I would use github.com/evanphx/benchmark-ips rather than the stdlib benchmark as it provides a bit more information. –  Sean Jun 4 at 16:29
Benchmarking is kind of moot. For 10^4 (10,000) I loop 4 times. This will roughly loop (10^4)*(5!) times. Nice answer though. –  ckuhn203 Jun 4 at 16:37
Oh Somehow I misread the question, I thought you wanted all numbers with the 5 in it, not just how many there were. Yeah definitely use the above algorithms for that. this is if you actually want to do something with all those numbers. –  Sean Jun 4 at 18:56
That was my fault. I mis-worded the question a bit. –  ckuhn203 Jun 4 at 18:57
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.