I went about counting divisors of a number by looking at the prime factorization of . If , then has divisors, because any divisor has a sort of “sub”-factorization, which is to say the same primes just to smaller (or possibly the same) powers (or 0, that’s why the “1+” is in each term in the product).

So, to determine the number of factors, we first find the prime factorization, and then do a quick product. Suppose we have a method “factor” which takes an integer , and returns a list of tuples of the form (prime, power). So, for example, “factor(12)” would return “[ (2,2), (3,1) ]”. We can then pass such an object to the following function to calculate the number of divisors:

def numberDivisors(f): """ take a factorization and return the number of divisors """ return reduce(lambda x,y:x*y, map(lambda t:t[1]+1,f), 1)

Now, I want to use this to find the number of divisors for triangular numbers. We could just loop over the triangular numbers, factoring each in turn. However, that’s pretty redundant. The -th triangular number (let’s denote that by ) is . Exactly one of or is even, so , where is even and is odd. If we factor and separately, we can multiply the factorizations together by simply adding powers. While we’re at it, if we store the factorization of and , and , we’ll be able to use those factorizations to factor later triangular numbers. Probably if we thought about it for a while, we could get away with only storing the factorization of and , because the factorization of won’t be used again (I think).

Here’s my implementation of these ideas:

def solve(goal): """ Find the first triangle number with more than 'goal' divisors Return the number and the time taken to find it Assumption: goal is a positive integer """ t = time.time() # lets store some factorizations to kick things off factorization = { 2:[[2,1]], 3:[[3,1]], 4:[[2,2]], \ 5:[[5,1]], 6:[[2,1],[3,1]] } # since goal is a positive integer, by assumption, we are looking # for a triangle number with >=2 divisors divs, n, tri, epsilon = 2, 2, 3, 0 # loop invariant: T_n=tri has divs divisors, epsilon = 0 or 1 # and n+epsilon is even while(divs <= goal): n, epsilon = n+1, 1-epsilon tri = n * (n+1) // 2 lesser, greater = (n+epsilon)//2, n+1-epsilon if not (lesser in factorization): factorization[lesser] = factor(lesser) if not (greater in factorization): factorization[greater] = factor(greater) # concatenate the lists of factors combfact = factorization[lesser] + factorization[greater] # we know how to factor the product factproddict = {} for p,e in combfact: if not (p in factproddict): factproddict[p] = e else: factproddict[p] += e factorization[tri] = factproddict.items() # convert dictionary => list divs = divisors(factorization[tri]) t = time.time() - t return (tri,t)

I guess things could possibly be simplified a little if the “factor” function that I use there returned a dictionary instead of a list, but currently I’ve got it set up to return a list. By the way, the factorization loop I’m using is the “factorAndSieve” code from Numerical Recipes, slightly modified to return a list of tuples, instead of just a (possibly repeating) list of primes. If I’d been paying slightly more attention, he’s got a lengthy post about computing the number of divisors for an integer as well.

I decided to compare the two methods of solving this problem, as I am one to do (the graphs are just so much fun). The first method just factors every triangle number in turn until you have enough divisors (called “Basic” in the following graph). The second is the one with the code above, where we store factorizations (called “Store”). In the following graph, the -axis indicates the number of divisors that you are hoping for (tickmark labelled corresponding to divisors), and the -axis is some scaled “ln(time)”.

Just for some sort of definite idea about timing, the last tickmark, corresponding to 500 divisors (the stated problem) takes my computer around 10 seconds for the Basic script, and less than 1 second for the Store script.

Of course, the Store script uses more storage space. I think we could remove factors as we went to save some space. At the -th triangular number, I think we never need factorizations of anything less than , so we could remove those as we went. Just as a side note, when you look for the first triangular number with more than 500 divisors, the Store script above has 21524 stored factorizations, with numbers ranging from 2 to the answer (which I got to be up in the 76 million range). If anybody can point me in the right direction to learn about how to test the space usage of my scripts, I’d love to hear about it. Something similar to the built in time module, but for space, would be awesome.

The function taking to the number of divisors of is probably a vaguely interesting function. I plotted it with inputs up to 100:

and with inputs up to 300:

That first big spike in the second graph is at input 224, indicating has 90 divisors. Apparently.

Tags: comparison, nah, prob12, python

September 29, 2013 at 3:49 am |

There’s a good bit of info for python memory profiling here: http://stackoverflow.com/questions/110259/which-python-memory-profiler-is-recommended

October 14, 2013 at 6:26 pm |

stupid Question but why not just brute force. this example is perl. I’ll work out an erlang example … executes on a crappy netbook in 42 seconds.

#!/usr/bin/perl

while(1) {

$y += $x++; $r=0;

for $z (1 .. sqrt($y)) {

$y % $z == 0 and $r+=2;

}

if ($r>499) {print “$x $y\n”;die}

}

This example is also ripped, I just can’t remember from whom!

Thanks for the article!