## 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.```
L = 10**7
n = [0]*(L)
for i in range(2, L//2):
for j in range(i*2, L, i):
n[j] += 1
print "Consecutive divisors =", sum(n[i] == n[i - 1] for i in range(3, L))
```

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

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose*define*to reveal the answer.

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