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

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

-

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

-

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

-
I never even considered recursion. Nice call. Are the underscores a Ruby convention? Should I not use camel case? –  RubberDuck Jun 4 '14 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 '14 at 14:23
Thank you for the clarification. I'll read up on the style conventions. –  RubberDuck Jun 4 '14 at 14:26
I suggest changing the base case to return 0 if pwr == 0. –  200_success Jun 4 '14 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 '14 at 19:25

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

-
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 '14 at 18:32
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 '14 at 3:12

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

-
That is absolutely more ruby, but it's also brute force isn't it? –  RubberDuck Jun 4 '14 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 '14 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. –  RubberDuck Jun 4 '14 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 '14 at 18:56