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

Question

Чтобы узнать больше о zeisel numbers

Zeisel номер является бесквадратно целого числа к с по меньшей мере, три главными факторами, которые попадают в шаблон

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

, где А и В некоторые integer константы и 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; 
} 

Answer 1

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

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

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

p2 - p1 = a * (p1 - 1) 

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

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

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;