CODEWITHSUNDEEP
pythonalgorithmmath
Alex Coplan
Alex Coplan

Reputation: 13371

What's wrong with my python solution to Project Euler #12?

Possible Spoiler Warning

I've spent ages trying to improve this algorithm and work out what's going wrong, but I can't seem to work out why the outputted answer is incorrect.

I'm trying to solve Project Euler #12, to get the lowest triangular number to have over 500 divisors, but it says my answer is incorrect.

Here is my Python code:

import time

# function to get the number of divisors
def div(n):
    d=2
    for i in range(2,int(n**.5)+2):
        if (n % i) == 0:
            d += 1
    return d

start = time.time()

w = True
n=m=1
while w:
    n += 1
    s = (n*(n+1))/2 # nth triangle number
    r = div(s)
    if r > m:
        m = r
        print s,"has",r,"divisors"
        if r > 500:
            w = False

print "Solved in",((time.time()-start)*1000),"milliseconds"

And the output for that code is this (in 66 seconds):

3 has 2 divisors
6 has 4 divisors
36 has 6 divisors
120 has 9 divisors

...

76576500 has 289 divisors
103672800 has 325 divisors
236215980 has 385 divisors
842161320 has 513 divisors
Solved in 65505.5799484 milliseconds

However, if I input 842161320 into the Project Euler problem, it says it's incorrect.

What am I doing wrong?

Upvotes: 1

Views: 1745

Answers (3)

Alex Coplan
Alex Coplan

Reputation: 13371

Solved

With the help of Niklas, and changing my div method, I've got the answer. Also, it's now only takes 8% of the time my previous algorithm took.

The algorithm now looks like this:

import time
import itertools

def div(n):
    d=0
    for i in range(1,int(n**.5)+1):
        if (n % i) == 0:
            d += 1
    return 2*d

start = time.time()

s = m = 0
for i in itertools.count(1):
    s += i
    r = div(s)
    if r > m:
        m = r
        print s,"has",r,"factors"
        if div(s) > 500:
            break

print "Solved in",((time.time()-start)*1000),"milliseconds"

Upvotes: 0

Niklas B.
Niklas B.

Reputation: 95358

I see two bugs:

  • Your div function is broken: div(24) == 5, while it should be 8
  • Your 1st triangular number would be 3, although it should be 1

You could implement a working div like this:

import math
def divisors(n):
  return sum(1 for x in range(1, n+1) if n % x == 0)

Also, that code is inefficient as hell, some suggestions to improve it are:

Instead of calculating the nth triangular number using your formula, use a rolling sum:

import itertools

s = 0
for i in itertools.count(1):
  s += i
  if div(s) > 500:
    print s
    break

Also, Use prime factors to calculate the number of divisors. You can create a prime factor cache for maximum performance.

Upvotes: 5

chepner
chepner

Reputation: 532333

You are undercounting the total number of divisors. 36, for example, has 9 divisors: 1,2,3,4,6,9,12,18,36. It's true the algorithm only needs to test numbers smaller than sqrt(n) to find all divisors, but you still need to include the implied "large" divisors in your count.

Upvotes: 2

Related Questions