James Pine Has A Blog

Jump to Comments

Problem #12
Find the first triangle number to have over 500 divisors.

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:

def triangleNumber():
 num = 1
 add = 2
 while True:
  yield num
  num += add
  add += 1

I can assign that to a variable and then invoke next() repeatedly to get triangle numbers ad infinitum.

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:

def primeFactorization(num):
 factors = []
 while 2 <= num:
  if num & 1:
   break
  else:
   num = num >> 1
   factors.append(2)
 factor = 3
 while factor <= num:
  if num % factor == 0:
   num /= factor
   factors.append(factor)
  else:
   factor += 2
 return factors

This 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...

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:

def uniqueCounts(l):
 counts = []
 count = 0
 previous = None
 for x in l:
  if x == previous:
   count += 1
  else:
   counts.append(count+1)
   count = 1
   previous = x
 counts.append(count+1)
 return counts

Then the divisor function is simply:

def divisorFunction(factors):
 return reduce(operator.mul,uniqueCounts(factors))

Clearly 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.

Problem #13
Figure out the first 10 digits of the sum of 100 50 digit numbers.

Even though Python supports arbitrary-precision arithmetic, in this particular case there's no need to add every digit of every number. Since we've only been asked to provide the first 10 digits of the sum, we only need to add the first 11 digits of each number since none of the others happen to affect the first 10 digits of the sum.

total = 0
file = open("problem0013.txt","r")
while True:
 temp = file.readline()
 if not temp:
  break
 total += int(temp[0:11])
file.close()
print str(total)[:10]

Problem #14
The following iterative sequence is defined for the set of positive integers:

n -> n/2 (n is even)
n -> 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence of 10 numbers:
13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
Which starting number, under one million, produces the longest sequence?

It seemed like a brute force algorithm with some caching would likely solve this relatively quickly.

cache = dict()
cache[1] = 1
maxCount = [1,1]

def find(n,m):
 newN = 0
 if n in cache:
  return cache[n]
 elif n % 2 == 0:
  newN = n / 2
 else:
  newN = 3 * n +1
 temp = 1 + find(newN,m)
 cache[n] = temp 
 if temp > m[1] and n < 1000000:
  m[0] = n
  m[1] = temp
 return cache[n]

for i in xrange(2,1000000):
 find(i,maxCount)
print maxCount

This solves the problem in about 10 seconds on my EeePC. It's an interesting fact that the cache contains 2,168,611 values even though it's only calculating the counts for numbers < 1,000,000 because any odd number > 333,333 creates a value greater than 1,000,000 in the sequence.