Page 1 of 1
10408 - Farey sequences
Posted: Mon Nov 18, 2002 5:47 pm
by 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?
some clue
Posted: Mon Nov 18, 2002 8:05 pm
by 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.
Posted: Mon Nov 18, 2002 11:14 pm
by 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.
Posted: Tue Nov 19, 2002 1:06 am
by Christian Schuster
I used something like Larry, but I didn't check the gcd (too slow), I only did
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.
Posted: Sat Dec 14, 2002 9:58 am
by 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.
Posted: Mon Dec 16, 2002 6:33 am
by anupam
Christian Schuster's way for gcd works. but what is the reason before it to use a|b. how does this way work?
Posted: Wed Aug 30, 2006 7:52 am
by 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 !!
Re: some clue
Posted: Tue Sep 12, 2006 6:24 pm
by 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
Posted: Wed Sep 13, 2006 5:23 pm
by 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
Posted: Fri Nov 10, 2006 11:58 pm
by 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.