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