Project Euler Forum

Hi all,

Sorry for such a basic question but I'm hitting my ceiling of knowledge and not sure how to get better at solving the problems.

For instance, on a recent problem, I got stuck trying to find the answer until I searched and saw someone wrote something like "Of course, this was easy using the Farey sequence..."

It's been a while since Calculus and Discreet Math for me but I never learned the Farey sequence and couldn't solve this problem without it.
I suppose my question is : Where did you learn things like the Farey Sequence (was this in Calculus 2? ) And more importantly, where
can someone like me read/study up on topics to help me with the problems?

The next couple euler problems I have would require days of processing time --- so it's not the programming but more the thought behind
the algorithms and missing math in my knowledge. Where could I go to improve on these?

Thanks!
-D

Quite generally, when one gets to a certain amount of solved problems, there come available more and more solution PDFs and forums. These can be treasures of information if read thoroughly. Most general techniques and algorithms also have a decent Wikipedia page. From there, usually there are also links to PDFs on the web which explore something in-depth. Lastly, Wolfram MathWorld has helped me out quite a bit over time.

Hopefully these suggestions will allow you to progress further in these fascinating subjects.

There's lots of material on the web if you know where to look. Wikipedia has an article on Farey sequences, as does MathWorld.

Of course it's hard to find your way into the literature if you don't know the terminology. You could start at MathWorld's page on fractions and look at the list of related topics in the "see also" section. Another way of finding your way into the literature is to generate a few items of a sequence and look them up in the Online Encyclopedia of Integer Sequences. For example, you might generate a small sequence of reduced fractions, say all the ones with denominator at most 5: 0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1. Take the numerators 0,1,1,1,2,1,3,2,3,4,1 and enter them at OEIS, and you'll find that they are the "Numerators of Farey series". Once you know their name, you can look them up.

It's also a good idea to have a bunch of mathematical and computational ideas at your fingertips, especially in number theory, discrete maths, and algorithms. You say you once did a course in discrete maths; how long since you re-read your textbook?

Do you want book recommendations? When doing Project Euler problems, I often find myself picking up Concrete Mathematics by Graham, Knuth and Patashnik, to look up some technique for solving recurrences, or some combinatorial identity. For number theory, you might find A Pathway Into Number Theory by R. P. Burn interesting. It takes similar approach to Project Euler: it consists entirely of problems! These are carefully graded to introduce modular arithmetic, Fermat's theorem, quadratic reciprocity, continued fractions, Pell's equation and other topics which may come up from time to time here.