Find numbers with same number of divisors

Question

I tried to resolve this task:

The integers 14 and 15, are contiguous (1 the difference between them, noticeable) and have the same number of divisors.

14 ----> 1, 2, 7, 14 (4 divisors)
15 ----> 1, 3, 5, 15 (4 divisors)

The next pair of contiguous integers with this property is 21 and 22.

21 -----> 1, 3, 7, 21 (4 divisors)
22 -----> 1, 2, 11, 22 (4 divisors)

We have 8 pairs of integers below 50 having this property, they are:

[[2, 3], [14, 15], [21, 22], [26, 27], [33, 34], [34, 35], [38, 39], [44, 45]]

Let's see now the integers that have a difference of 3 between them. There are seven pairs below 100:

[[2, 5], [35, 38], [55, 58], [62, 65], [74, 77], [82, 85], [91, 94]]

Let's name, diff, the difference between two integers, next and prev, (diff = next - prev) and nMax, an upper bound of the range.

We need a particular function, count_pairsInt(), that receives two arguments, diff, and nMax and outputs the amount of pairs of integers that fulfill this property, all of them being smaller (not less or equal) than nMax.

Let's see it more clearly with examples.

count_pairs_int(1, 50) -----> 8 (See case above)
count_pairs_int(3, 100) -----> 7 (See case above)

Source: codewars.com

My code:

def count_pairs_int(diff, n_max)
  (1..n_max - diff).select { |n| getDivisors(n) == getDivisors(n + diff) }.count
end

def getDivisors(num)
  (1..num).select { |n| (num % n).zero? }.count
end

There is a problem with time of execution code:

The process terminated. It took longer than 8000ms to complete

Initial tests are passed (first 10). Any ideas on how I can optimize the code?

Answer 1

You are not interested in the divisors themselves, only how many there are. This can be calculated if the prime factors are known. For example, 12 has two 2' s and one 3 (12 = 2*2*3). The divisors are the product of 0,1 or 2 2's and 0 or 1 3's. So six divisors. The primes themselves are irrelevant, what matters is how many of each there are.

If only Ruby shipped with a method to do this prime division...

require 'prime' # delivers the prime_division method

class Integer
  def tau
    self.prime_division.map(&:last).inject(1){|prod,i| prod *= i+1}
  end
end

def count_pairsInt(diff,  nMax )
  (1..nMax-diff).count{|n| n.tau == (n+diff).tau}
end

Note: Probably this can be faster by memoizing (storing) the last diff tau (divisor count) calculations, to avoid calculating them twice.

Answer 2

A glaring performance issue I see is the use of count for both methods. Count will enumerate over each element in the array to return the final count and should be avoided if possible. Instead, you could use size. This alone is a simple change that should greatly improve your execution time.

Your updated code should look like this:

def count_pairs_int(diff, n_max)
  (1..n_max - diff).select { |n| getDivisors(n) == getDivisors(n + diff) }.size
end

def getDivisors(num)
  (1..num).select { |n| (num % n).zero? }.size
end