Monday, February 3, 2014

Project Euler 51 - 60

Project Euler Solutions to Questions 51 - 55
Project Euler Solutions to Questions 56 - 60

With some of the problems, I'm starting to run up against the one-minute execution time guideline.

From a computational perspective, I feel as if I'm still reasonably well equipped to handle the problems. Various parts of my Coursera and Udacity education have come in handy, including dynamic programming, basic cryptography, and the general approach to breaking down problems as presented in Peter Norvig's class.

From a number theoretical perspective, though, I'm running into some trouble.  In Problem 60, for example, the naive brute-force approach runs in O(n^5), where n is on the order of 10,000 (and possibly much larger). There are surely ways to cut down the search space, but I need to do some more reading on primes.

On the subject of primes, I need to find a better primality test.  So far I've been able to get by with a combined approach of:
  • generating all primes that are less than 10,000,000 via the Sieve of Erastothenes
  • checking primality of larger numbers by prime factoring and counting the number of factors
Maybe the next step is to implement a faster sieve or something like the Miller-Rabin test.

Saturday, February 1, 2014

Project Euler 36 - 50

Project Euler Solutions to Questions 36 - 40
Project Euler Solutions to Questions 41 - 45
Project Euler Solutions to Questions 46 - 50

Problem 46 is about one of Goldbachs' conjectures that turns out to be false.

The original Goldbach conjecture is an interesting problem.  Following Wikipedia's example, I tried creating a graph that shows the number of ways to represent even integers as the sum of two primes (the number of "Goldbach partitions").  From the small dataset, it looks like the number of Goldbach partitions increases with integer size, and moreover there is some periodicity to the number of partitions. But of course, such observations are meaningless in the context of mathematical proofs.