Project Euler Problem 12 Triangular Numbers

"""Mark-Jason Dominus provides a useful result from number theory which we can use to solve this problem using a method other than pure brute force. He writes:

http://blog.plover.com/oops/triangular-phi.html

Abhijit Menon-Sen wrote to me to ask for advice in finding the smallest triangular number that has at least 500 divisors. (That is, he wants the smallest n such that both n = (k2 + k)/2 for some integer k and also ν(n) ≥ 500, where ν(n) is the number of integers that divide n.) He said in his note that he believed that brute-force search would take too long, and asked how I might trim down the search.

The first thing that occurred to me was that ν is a multiplicative function, which means that ν(ab) = ν(a)ν(b) whenever a and b are relatively prime. Since n and n-1 are relatively prime, we have that ν(n(n-1)) = ν(n)·ν(n-1), and so if T is triangular, it should be easy to calculate ν(T). In particular, either n is even, and ν(T) = ν(n/2)·ν(n+1), or n is odd, and ν(T) = ν(n)·ν((n+1)/2).

Dominus states that his own solution using these formulas took 90 seconds using python. If the solution takes more than 60 seconds then first try it on faster machines.

Based on http://www.mindstab.net/wordpress/archives/tag/primes there is reason to think that Python is extremely slow when it comes to calculating prime numbers and is much slower than C#. Therefore Boo is also faster than Python. So if Python is still too slow then convert to Boo and try.

As it happens, my solution takes 40 seconds on my iMac but 2.:45 minutes on my Asus EEE and 1:05 minutes on my generic Intel server.

========================================================================
http://wj32.wordpress.com/2007/10/08/factor-for-python/
# """
# Factor a number
#
# Wj.
# """
#
# # Simple factoring
# def factor(n, noduplicates = False):
# intn = int(n)
# factors = {}
# lastfactor = n
# i = 0
#
# # 1 is a special case
# if n == 1:
# return {1: 1}
#
# while 1:
# i += 1
#
# # avoid duplicates like {1: 3, 3: 1}
# if noduplicates and lastfactor <= i:
# break
#
# # stop when i is bigger than n
# if i > n:
# break
#
# if n % i == 0:
# factors[i] = n / i
# lastfactor = n / i
#
# return factors
#
# if __name__ == "__main__":
# import sys
#
# print "Enter an integer:"
# number = sys.stdin.readline()
# print "Factors: " + str(factor(int(number), True))

========================================================

And here is my solution, which is based upon Dominus's method and factor.py

new-host-2:~ gayelynntaxey$ python factor.py
sys:1: DeprecationWarning: Non-ASCII character '\xce' in file factor.py on line 36, but no encoding declared; see http://www.python.org/peps/pep-0263.html for details
Tue Sep 2 21:10:15 2008
76576500
Tue Sep 2 21:10:55 2008
new-host-2:~ gayelynntaxey$ cat factor.py


def factor(n, noduplicates = False):
intn = int(n)
factors = {}
lastfactor = n
i = 0

# 1 is a special case
if n == 1:
return {1: 1}

while 1:
i += 1

# avoid duplicates like {1: 3, 3: 1}
if noduplicates and lastfactor <= i:
break

# stop when i is bigger than n
if i > n:
break

if n % i == 0:
factors[i] = n / i
lastfactor = n / i

return factors

def factorCount(n):
return len(factor(n))

def T(k):
return (k*k + k)/2

# either n is even, and ν(T) = ν(n/2)·ν(n+1), or n is odd, and ν(T) = ν(n)·ν((n+1)/2).
def vT(n):
if n % 2 == 0:
return factorCount(n/2) * factorCount(n+1)
else:
return factorCount(n)*factorCount((n+1)/2)

import time
print time.asctime()
n = 2
while vT(n) < 500:
n += 1
print T(n)
print time.asctime()
new-host-2:~ gayelynntaxey$