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, May 7, 2011

I am currently sitting in a train, and writing this post since I solved problem 40 in Project Euler using pen & paper waiting for my computer to start up and get online. It is not a terribly difficult problem to answer, at least it wasn't for me. The problem readsAn irrational decimal fraction is created by concatenating the positive integers If dn represents the nth digit of the fractional part, find the value of the following expression.d1 x d10 x d100 x d1000 x d10000 x d100000 x d1000000I read the problem description last night and started solving it in my head, but I quickly get lost when I handle numbers, so I knew that I needed a scrap of paper in order to jot down my notes.

Continue reading...Saturday, February 5, 2011

Problem 26 of Project Euler reads Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.How can be possibly approach this problem. Just doing a division and then analysing the double we get out of it is not likely to give us enough digits to find the solution. However, I found one possible approach. Instead of actually calculating the fraction, we analyse the remainder on each position. It has the advantage that we work with integers rather than fractions.

Continue reading...
Saturday, December 3, 2011

8 Comments