## 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* < 10^{7}, 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*< 10^{5}: 10585 - 1 <
*n*< 10^{6}: 102093 - 1 <
*n*< 10^{8}: 9593611

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

I ran your code exactly as written in Shell…it yielded 986262

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.

Your awesome bro I love your site.

Thanks very much