Problem #12
\nFind the first triangle number to have over 500 divisors.<\/p>\n
As I’m progressing through these problems, certain types\/sequences of numbers keep popping up. I’ve started a library of functions called eulerLib.py. The first thing I did was add a triangle number generator to my library:<\/p>\n
\r\ndef triangleNumber():\r\n num = 1\r\n add = 2\r\n while True:\r\n yield num\r\n num += add\r\n add += 1\r\n<\/pre>\nI can assign that to a variable and then invoke next() repeatedly to get triangle numbers ad infinitum.<\/p>\n
Then I needed a function that could factor numbers. One way I could go about things would be to figure out all the proper divisors; however, since I didn’t actually care what the divisors were, just the number of them, another thing I could do is figure out the prime factorization and then use the divisor function to calculate the number of proper divisors. I added another function to my library:<\/p>\n
\r\ndef primeFactorization(num):\r\n factors = []\r\n while 2 <= num:\r\n if num & 1:\r\n break\r\n else:\r\n num = num >> 1\r\n factors.append(2)\r\n factor = 3\r\n while factor <= num:\r\n if num % factor == 0:\r\n num \/= factor\r\n factors.append(factor)\r\n else:\r\n factor += 2\r\n return factors\r\n<\/pre>\nThis may not be the fastest algorithm, but it is fast enough. 2 is the smallest and only even prime number, so while num is even, it keeps adding 2 to the list of factors and dividing num. After that it starts with 3 and does the same thing for every subsequent odd number. It's inefficient as it will try to divide num by 9 after it has reduced num such that 3 will no longer divide it. At some point it will probably be useful to create a list of prime numbers so I don't have to keep generating them over and over...<\/p>\n
Once I have the prime factorization, I need to figure out the number of times each factor occurs in the list. Since my list is sorted, I can just loop through:<\/p>\n
\r\ndef uniqueCounts(l):\r\n counts = []\r\n count = 0\r\n previous = None\r\n for x in l:\r\n if x == previous:\r\n count += 1\r\n else:\r\n counts.append(count+1)\r\n count = 1\r\n previous = x\r\n counts.append(count+1)\r\n return counts\r\n<\/pre>\nThen the divisor function is simply:<\/p>\n
\r\ndef divisorFunction(factors):\r\n return reduce(operator.mul,uniqueCounts(factors))\r\n<\/pre>\nClearly I could have kept count while figuring out the prime factorization, but then the function is not as reusable. I suppose I could have passed in a function that operated on the factors as they were discovered, even blending the divisor function in as well, but for understandability, I've kept them separate. At this point, all the pieces are there and it's just a matter of looping through triangle numbers and figuring out the number of divisors. When the number of divisors is > 500, return that triangle number...it's less than 100,000,000.<\/p>\n
Problem #13
\nFigure out the first 10 digits of the sum of 100 50 digit numbers<\/a>.<\/p>\n