10408 - Farey sequences

[htl]

I solve the problem by building a table storing fractions. But I got memory limit exceed. Is there any way of reducing the use of memory?

[kmhasan]

For each Farey series think of it starting with only two numbers 0/1 and 1/1. You can add "mediants" [(numerator of leftnum+numerator of right num)/(denominator of leftnum+denominator of rightnum)] in between the numbers as long as the denominator is <= N.

For example a series can be generated as follows:
0/1,1/1
0/1,1/2,1/1
0/1,1/3,1/2,1/1
0/1,1/3,1/2,2/3,1/1
and so on....

I used linked list and recursion to generate the series for Fn, and did a linear search to find the Kth number. While this is certainly not the best way to do it, it does work.

[Larry]

Not the most efficient in the world, but it ran in a little over a second, so here's how I did it:

Code: Select all

for ( i = 1; i < 1000; i++ )
for ( j = i + 1; j < 1000; j++ )
if ( gcd( i, j ) == 1 )
store( i, j )

Then I quicksort and did a linearly search. Not fast, but easy to code.

[Christian Schuster]

I used something like Larry, but I didn't check the gcd (too slow), I only did

Code: Select all

if ((i|j)&1)
  store(i,j)

this excludes pairs where both numbers are divisible by two. Afterwards I sorted the result with qsort and threw the duplicates away. The linear search remained the same.

I reviewed my code and found an iterative method to create the linked list of numbers kmhasan wrote about. That's somewhat faster.

[Spike]

Start with an array of n numbers:
1/n, 1/(n-1), 1/(n-2).... 1/1

This is the start of what will be your minHeap.

Remove the smallest item from the minHeap. We'll call this item x/y.

Check x+1 and y...
if x+1 >= y, add 1 to the heap
if no common factors, add (x+1) / y to heap
if common factors, check x+1 and y

Doing this k times gives you your solution.


This means you're storing a max of n fractions and you're performing a heap function k times. Heap updates are O( lg n ), so your total time complexity is approximately k * lg n.

[anupam]

Christian Schuster's way for gcd works. but what is the reason before it to use a|b. how does this way work?

[sakhassan]

Hello Spike,
Would u pls explain the algorithm pls.I am not actually clear ..
Like u said : " if x+1 >= y, add 1 to the heap " ... I didnt get the actual idea !!

[altaf hussain(sust_2002)]

as kmhasan written,

You can add "mediants" [(numerator of leftnum+numerator of right num)/(denominator of leftnum+denominator of rightnum)] in between the numbers as long as the denominator is <= N.

0/1,1/1
0/1,1/2,1/1
0/1,1/3,1/2,1/1
0/1,1/3,1/2,2/3,1/1
and so on....

i understood the approch, but i am confused about that:
the last line in the given seqence of kmhasan is for N=4,
as i understood frm kmhasan approach it should be

0/1,1/4,1/3,1/2,2/3,1/1
will some one explain why this did not occour.

altaf

[sakhassan]

HERE's MA CODE ?? I DONT HAVE ANY IDEA WHY IT IS SUFFERING FROM RTE??? CAN ANYBUDDY HELP ME?

Code: Select all

#include<stdio.h>
#include<string.h>

#define N 10000

int a[N][3];
int indx;


int gcd(int b, int c)
{
	if(c==0)
	 return b;
	else
	 return gcd(c,b%c);
}




void swap(int i, int j)
{
	int temp1,temp2;

	temp1=a[i][0];
	temp2=a[i][1];
	a[i][0]=a[j][0];
	a[i][1]=a[j][1];
	a[j][0]=temp1;
	a[j][1]=temp2;
}

void qsort(int left, int right)
{
	int i, last;
	double m,n;

	if(left>=right)return;
	swap(left, (left+right)/2);
		last=left;
	for(i=left+1;i<=right;i++)
	{
		m = (double)a[i][0]/(double)a[i][1];
		n = (double)a[left][0]/(double)a[left][1];
		if(m<n)
		 swap(++last, i);

	}
	swap(left,last);

	qsort(left, last-1);
	qsort(last+1, right);
}





int main()
{

   int f,k;
   int i,j;
   memset(a,0,sizeof(a));


   while(scanf("%d%d",&f,&k)==2)
   {

	indx=0;
	memset(a,0,sizeof(a));
	a[indx][0]=0;
	a[indx][1]=1;
	indx++;
	a[indx][0]=1;
	a[indx][1]=1;
	indx++;
	
	for(i=1;i<=f;i++)
	{
		for(j=f;j>i;j--)
		{
			if(gcd(i,j)==1)
			{
			    a[indx][0]=i;
			    a[indx][1]=j;
			    indx++;

			}
		}
	}
	qsort(0,indx-1);
	printf("%d/%d\n",a[k][0],a[k][1]);
   }

   return 0;
}

Thanks in Advance

[Jan]

Increase your array size. Your complexity is O(n^2), and n can be 1000. So, you need an array of size at least (1000*(1000+1))/2. Hope it helps.