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
Posted by Gary Walker | March 6, 2014, 9:30 AMI ran your code exactly as written in Shell…it yielded 986262
Posted by Paul | January 16, 2014, 10:25 AMBecause 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 PMYour awesome bro I love your site.
Thanks very much
Posted by Coder | June 19, 2012, 10:45 AM