如何編程以檢查數字是否是zeisel號碼？

Question

爲了更多地瞭解zeisel numbers

甲的Zeisel數與至少三個素因子一個正方形 - 自由整數k落入圖案

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

其中a和b是一些整數常數，x是分解中每個素因子的索引號，從最低到最高排序。爲了確定Zeisel數字，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;