Project Euler : 71–75

• Problem 71 ( Click to Read )

I had already seen a problem of such kind on SPOJ here. So I knew this is called ‘Farey Sequence’. You can easily find neighbor of any fraction in Farey sequence, read this Wikipedia page.

In the problem statement 2/5 is the neighbor of 3/5 in Farey sequence of order 8, so it is easy to guess that neighbor in order >8 would lie between 2/5 and 3/7. You have found your a, b, c, d according to wikipedia link :) start coding.

#include <stdio.h>
int main()
{
  long int a, b, c, d, order, pre;
  
  order = 0;
  c=3, d=7;
  a=2, b=5;
  while (order <= 1000000)
  {
    a += c;
    b += d;
    order = b;
    if (order > 1000000)
      printf("%ld\n", a-c);
  }
  return 0;
}

• Problem 73 ( Click to Read )

I would advise to read the Farey Sequence link of wikipedia that I posted in solution of problem 71 to understand what my code is doing.

I am recursively calculating fractions between 1/2 and 1/3, the first iteration would divide my interval in two parts (1/2, 2/5) and (2/5, 1/3). Now again run the recursive function on both these intervals and increment counter for each fraction calculated TILL the denominator is less than equal to 12000 in reduced form meaning HCF( n,d)=1

Here is my C code, the depth of recursion made it little slow to give answer in 4–5 seconds.

#include <stdio.h>
long int total;
int gcd (int x, int y)
{
  if (!(x%y))
    return y;
  else
    return gcd(y, x%y);
}
int func( int a, int b, int c, int d)
{
  int p, q, g;
 
  p = a + c;
  q = b + d;
  
  g = gcd(q, p);
  
  p /= g;
  q /= g;
  if (q <= 12000)
    return 1 + func(a, b, p, q) + func(p, q, c, d);
  else
    return 0;
}
int main()
{
  total = func(1, 3, 1, 2);
  printf(“%ld\n”, total);
  return 0;
}

You can find more Project Euler solutions on my Project Euler Publication.