// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (3 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.
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))
download arrowUse 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.
|986262|

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