// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (6 votes, average: 5.00 out of 5)
Loading...

Solutions 151 - 200

Project Euler 179 Solution

Project Euler 179 Solution

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:

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

download arrowUse 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
  3. Your awesome bro I love your site.
    Thanks very much

    Posted by Coder | June 19, 2012, 10:45 AM

Post a comment