Ruby-ize for loop - counting all the n-digit numbers that contain the digit 5 anywhere

Question

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

\$f(10^n)=9f(10^{n-1})+10^{n-1}\$

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

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

Answer 1

Not that using recursion is wrong, but there is already an abstraction for what this algorithm does: a left fold (Enumerable#reduce):

def number_containing_5(power)
  (1..power).reduce(0) { |acc, n| (9*acc) + (10**n)/10 }
end

Answer 2

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)
end

Answer 3

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)
  (10**power)-(9**power)
end 

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

test_it 20

Answer 4

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' } }