(6 votes, average: 5.00 out of 5)

## Project Euler 179: Find the number of consecutive integers pairs that have the same number of positive divisors.

#### Problem Description

Find the number of integers 1 < n < 107, for which n and n + 1 have the same number of positive divisors. For example, 14 has the positive divisors 1, 2, 7, 14 while 15 has 1, 3, 5, 15.

#### Analysis

Let’s take a subset of this problem and define the range to include the integers 1 < n ≤ 25. A simple way to find the number of divisors is to increment an array element for every n integers by one for each multiple of the divisors, not including 1 or itself. We need only check divisors from 2 to int(n/2).

That is, add 1 to each multiple of 2: 4, 6, 8, … then 3: 6, 9, 12, … then 4: 8, 12, 16, … and so on until we reach 12. Here’s a table to show the results:

 n 2 3 4 5 6 7 8 9 10 11 12 # Divisors 2 0 3 0 4 1 1 5 0 6 1 1 2 7 0 8 1 1 2 9 1 1 10 1 1 2 11 0 12 1 1 1 1 4 13 0 14 1 1 2 15 1 1 2 16 1 1 1 3 17 0 18 1 1 1 1 4 19 0 20 1 1 1 1 4 21 1 1 2 22 1 1 2 23 0 24 1 1 1 1 1 1 6 25 1 1

Note how you can identify the prime numbers as those with zero divisors (ignoring 1 and itself).

Now, check adjacent array elements for equality and you’ll have your answer. In this simple case of L=25, the answer would be 3. We’ve highlighted the results above.

#### Project Euler 179 Solution

Runs < 3 seconds in pypy.

Use this link to get the Project Euler 179 Solution pypy source.

#### Afterthoughts

• 1 < n < 105: 10585
• 1 < n < 106: 102093
• 1 < n < 108: 9593611

## Discussion

### 4 Responses to “Project Euler 179 Solution”

1. You miss a significant optimization. You only need to check divisors in the range 2..sqrt(n). For ever divisor you find, there are actually 2 divisors j and i//j. There is a special case though, if j is sqrt(i), there is only 1 divisor since j = i//j

Posted by Gary Walker | March 6, 2014, 9:30 AM
2. I ran your code exactly as written in Shell…it yielded 986262

Posted by Paul | January 16, 2014, 10:25 AM
• Because that’s the answer to the problem. The one I show in the comments is for 10^8. The problem only asks for a limit of 10^7.

Posted by Mike | January 16, 2014, 7:22 PM