I think that Problem 137 of Project Euler is a really fantastic problem since it has so many facets of how it can be solved. I will go through a one of them, and then link to a few other. The problem readsConsider the infinite polynomial series AF(x) = xF1 + x2F2 + x3F3 + ..., where Fk is the kth term in the Fibonacci sequenceWe shall call AF(x) a golden nugget if x is rational. Find the 15th golden nugget.I honestly don't know a whole lot about infinite series, and I am always quite intimidated by them. However, I know enough about them to know that there is something called a generating function which should be the keyword here.

Continue reading...Wednesday, June 13, 2012

Problem 10783 at the UVa Online Judge, also known as Odd Sum, asks us to compute the sum of odd numbers in a given range. The problem is easy, but fun, and can be solved in a similar way to the first Project Euler problem. We start off by creating a straight-forward solution which unfortunately works due to small test cases. We do one minor optimization and then finally finish with a neat closed-form solution.

Continue reading...Saturday, December 3, 2011

Problem 73 of Project Euler is the third problem in a row which treats ordering proper fractions. The problem description readsHow many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d ≤ 12,000?I solved this in two different ways. Due to the small upper bound I attacked it bruteforce and with a somewhat smarter solution using Farey sequences. Something I have heard mentioned in many previous solutions but only just now started reading up on.

Continue reading...Saturday, August 20, 2011

I found Problem 57 of Project Euler to be a rather interesting problem, with more than one solution. The problem description readsIn the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?First thing I will present is a brute force solution, which for all practical purposes are fast enough. The second solution is a closed form approximation to the problem, so it can be solved as fast as you can punch the calculator.

Continue reading...Saturday, June 25, 2011

Problem 49 of Project Euler asks us to find three numbers with the following propertiesThe arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another. There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.Avid readers of the blog knows how fond of prime number lists by now, so I took that approach instead. I took the following approach.Generate a list of primes below between 1000 and 10000. Take two primes i and j with i < jand calculate k = j + (j-i). Check if k< 10000 and check if k is a prime, if not go to 2. Check if i and j are permutations of each other and check if i and k are permutations of each other. If not go to 2. Found the triple, so exit.

Continue reading...
Saturday, February 23, 2013

6 Comments