Как я могу запрограммировать, чтобы проверить, является ли число числом zeisel или нет?

Чтобы узнать больше о числах Zeisel

Число Цейзеля — это бесквадратное целое число k с не менее чем тремя простыми множителями, которые попадают в шаблон

p[x] = a*p[x-1] + b

где a и b — некоторые целочисленные константы, а x — порядковый номер каждого простого множителя в факторизации, отсортированный от меньшего к большему. Для определения чисел Цейзеля p[0] = 1.

Я написал этот код ниже в java. Эта функция проверяет положительное значение b, но не отрицательное значение b. Как я могу это сделать?

// function to caluculate zeisel number
public static boolean zeisel(int num) {
    // returning false if not squarefree
    if (Math.sqrt(num) == (int) Math.sqrt(num))
        return false;
    int fac = 2, count = 0, str = num;
    // arrray to store prime factors
    int[] fact;
    int a = 1, b = 0, i = 0;
    // counting number of factors
    while (num != 1) {
        if(num % fac == 0) {
            count++;
            num /= fac;
        }
        else 
            fac++;
    }
    num = str;
    fac = 2;
    // storing factors in array
    fact = new int[count]; 
    while (num != 1) {
        if(num % fac == 0) { 
            fact[i] = fac;
            i++;
            num /= fac;
        } else
            fac++;
    }
    if(i < 3)
        return false;
    // checking for zeisel equation
    while(a < fact[0]) {
        b = fact[0] - a;
        for(i = 1; i < count; i++) {
            if(fact[i] != a*fact[i -1] + b) {
                break;
            }
        }
        if(i == count) {
            return true;
        }
        a++;
    }
    return false;
}

java functional-programming number-theory
person Shubhraneel Pal    schedule 16.06.2016    source источник
comment
Преобразование отрицательного в положительное.   -  person Krythic    schedule 16.06.2016
comment
a не может быть отрицательным, верно? википедия ничего не говорит об этом, если a может быть отрицательным, то могут быть бесконечные решения для a и b !!!   -  person niceman    schedule 16.06.2016
comment
Math.sqrt(num) == (int) Mat.sqrt(num) не является подходящим тестом на отсутствие квадратов. 10 — число без квадратов, а 18 — нет, потому что его можно без остатка разделить на квадрат (3^2).   -  person AJNeufeld    schedule 17.06.2016
comment
a=8, b=-3 генерирует коэффициенты 5, 37, 293, что дает число Цейзеля 54205. Следовательно, допускаются отрицательные значения b. Таким образом, остановка цикла с помощью a < fact[0] не допускается.   -  person AJNeufeld    schedule 17.06.2016
comment
На oeis.org/A051015 есть код и еще несколько обсуждений из Интернет-энциклопедии целочисленных последовательностей, на которые вам следует ссылаться. перепроверить свою работу.   -  person vielmetti    schedule 18.06.2016

Ответы (1)


arrow_upward
0
arrow_downward

Нет необходимости в каком-либо цикле для определения факторов a и b. У вас есть два уравнения с двумя неизвестными:

p1 = a * (1) + b
p2 = a * p1  + b

Вычитание первого из второго дает:

p2 - p1 = a * (p1 - 1)

Который вы можете использовать для непосредственного решения для a = (p2 - p1) / (p1 - 1), и предполагая, что это целое число, затем решите для b = p1 - a.

Итак, после того, как вы сгенерировали свои коэффициенты в fact[] (с исправленным условием квадратного свободного ), ваш тест может выглядеть примерно так:

if ((fact[1] - fact[0]) % (fact[0] - 1) != 0)
    return false;

int a = (fact[1] - fact[0]) / (fact[0] - 1);
int b = fact[0] - a;

for(int i=2; i<count; i++) {
    if (fact[i] != a*fact[i-1] + b) {
        return false;
    }
}
return true;
person AJNeufeld    schedule 17.06.2016