найти положение дроби в последовательном порядке

Question

Чтобы найти положение дроби в последовательности , я попытался реализовать алгоритм, приведенный здесь http://www.math.harvard.edu/~corina/publications/farey.pdf в " исходный алгоритм «но я не могу понять, где я иду не так, я не получаю правильных ответов. Может ли кто-нибудь указать на мою ошибку? например. для порядка n = 7 и фракций 1/7, 1/6 я получаю одинаковые ответы. Вот что я пробовал для данной степени (n) и доли a / b:

sum=0;
int A[100000];
A[1]=a;

for(i=2;i<=n;i++)
  A[i]=i*a-a;

for(i=2;i<=n;i++)
{
  for(j=i+i;j<=n;j+=i)
    A[j]-=A[i];
}

for(i=1;i<=n;i++)
  sum+=A[i];

ans = sum/b;

Спасибо.

Answer 1

Ваш алгоритм не использует какие-либо конкретные свойства a и b.В первой части каждая соответствующая запись массива A кратна a, но коэффициент не зависит от a, b и n.Настройка массива без учета фактора a, т. Е. Начиная с A [1] = 1, A [i] = i-1 для 2 <= i <= n, после вложенных циклов массив содержит <a href="http://en.wikipedia.org/wiki/Euler%27s_totient_function" rel="nofollow"> totients , то есть A [i] = phi (i), независимо от того, что a, b, n.Сумма значений от 1 до n - это количество элементов последовательности Фарея порядка n (плюс или минус 1, в зависимости от того, какие из 0/1 и 1/1 включены в используемое вами определение).Таким образом, ваш ответ всегда является приблизительным (a * количество терминов) / b, что близко, но не точно.

Я еще не смотрел, как ваш относится к алгоритму в статье, проверьте еще разобновления позже.

Приложение: Наконец-то было время посмотреть на бумагу.Ваша инициализация не то, что они дают.В их алгоритме A[q] инициализируется в floor(x*q), для рационального x = a/b правильная инициализация

for(i = 1; i <= n; ++i){
    A[i] = (a*i)/b;
}

в оставшейся части вашего кода, только ans = sum/b; должно быть изменено наans = sum;.

Answer 2

Неалгоритмический способ определения положения t дроби в последовательности Фари порядка n > 1 показан в замечании 7.10 (ii) (a) paper , под m: = n -1, где mu-bar обозначает теоретико-числовую функцию Мёбиуса для натуральных чисел, принимающую значения из набора {-1,0,1}.

Answer 3

Вот мое решение Java, которое работает. Добавьте узлы head (0/1), tail (1/1) в SLL. Затем начните с передачи headNode, tailNode и установки требуемого orderLevel.

public void generateSequence(Node leftNode, Node rightNode){        
    Fraction left = (Fraction) leftNode.getData();
    Fraction right= (Fraction) rightNode.getData();
    FractionNode midNode = null;
    int midNum = left.getNum()+ right.getNum();
    int midDenom = left.getDenom()+ right.getDenom();
    if((midDenom <=getMaxLevel())){
        Fraction middle = new Fraction(midNum,midDenom);
        midNode = new FractionNode(middle);
    }
    if(midNode!= null){
        leftNode.setNext(midNode);
        midNode.setNext(rightNode);
        generateSequence(leftNode, midNode);
        count++;
    }else if(rightNode.next()!=null){
        generateSequence(rightNode, rightNode.next());
    }

}