About one math puzzle...

If you feel your algorithm is too complex - you are right. Find another one, more simple.
If you feel your algorithm is too ugly - you are right. Find another one,more beautiful solution exists.

Project Euler, Problem 73

Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8 (*)

It can be seen that there are 3 fractions between 1/3 and 1/2.

How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d ≤ 10,000?

Why was this task interesting for me? Only because using mathematical knowledge I come to wrong solution...

So... Sequence (*) is so called Farey Sequence. One of the characteristics of this sequence:

let p/q, p'/q', and p''/q'' be three successive terms in a Farey series.
then p'/q'==(p+p'')/(q+q'')

It comes from that characteristics that if you have two terms in a Farey series you can produce p'/q', such as p/q<p'/q'<p''/q'' and
p'=p+p''
q'=q+q''
And then normalize p' and q' so HCF(p',q')=1

So we come to simple algorithm - take border elements (p/q=1/3,p''/q''=1/2), produce one more element from the sequence p'\q', then look how may more elements between (p/q,p'/q') and between (p'/q',p''/q'').
The only question - when we should stop? The first answer come to mind - when q'>limit.

So here is first solution:

LONGLONG fractions_between(int a,int c,int b,int d,int limit)
{
 int _a1 = a+b;
 int _c1 = c+d;
 normalize(_a1,_c1);
 LONGLONG result=0;
 if(_c1>limit)
  return 0;
 return 1+fractions_between(a,c,_a1,_c1,limit)+fractions_between(_a1,_c1,b,d,limit);
}

LONGLONG euler_73()
{
 return fractions_between(1,3,1,2,10000);
}

I run it for (1/3,1/2) and 8 as a limit and got 3, just as expected.

fractions_between(1,3,1,2,8)==3

So I run it for 10000 and got...stack overflow :).

Ok, some optimization to get rid of stack overflow...but when I check my result I got only "Sorry, but the answer you gave appears to be incorrect". I start to study the logic of my code and found that the logic was fine...

So if my answer is wrong the problem is in algorithm...but it so simple! I check again my assumption about algorithm - we should stop when q'>limit... Is it really true? Let's check sequence (1/8, 1/7, 1/6, 1/5) with limit 8. Elements 1/8 and 1/5 produce 2/13, so we should stop? No, because 1/8 and 2/13 produce 1/7, and 1/7 is tolerated fraction. So...when we should stop?

Ok, better assumption - we should stop when p/q and p''/q'' can't produce such p'/q' (and all other nested elements) such as q'limit...

Sounds logical...but... at this moment I have a filling that something is really wrong. The solution became too complex. It takes too long to produce the result. There must be a more simple solution.

And I usually trust myself...so I delete my solution and start to think about another one. Few minutes later it come to my mind:)

This leads me to common principle I write at the beginning.