なぞなぞは次のとおりです。
k
ジョンは連続する奇数を書き留めました: n{1}, n{2}, ..., n{k-1}, n{k}
(どこn{2} = n{1} + 2
など)。私達はことを知っています:
- 最初の 4 つの数値の合計は、ある素数の 4 乗です (したがって
n{1} + n{2} + n{3} + n{4} = p{1}
、p{1}^4
は素数です。 - 最後の 5 つの数値の合計は、ある素数の 4 乗です (したがって
n{k} + n{k-1} + n{k-2} + n{k-3} + n{k-4}= p{2}^4
、p{1}
は素数です。
問題は、何個の数字が書き留められているかです ( k=?
)。
以下は、Javaでそれを解決しようとする私の試みです:
import java.math.BigInteger;
import java.util.Set;
//precalculate prime numbers
public class PrimeSieve {
public static boolean[] calculateIntegers(int N) {
// initially assume all integers are prime
boolean[] isPrime = new boolean[N + 1];
for (int i = 2; i <= N; i++) {
isPrime[i] = true;
}
// mark non-primes <= N using Sieve of Eratosthenes
for (int i = 2; i*i <= N; i++) {
// if i is prime, then mark multiples of i as nonprime
// suffices to consider mutiples i, i+1, ..., N/i
if (isPrime[i]) {
for (int j = i; i*j <= N; j++) {
isPrime[i*j] = false;
}
}
}
return isPrime;
}
}
解決クラス:
public class Solver {
static boolean[] isPrime = PrimeSieve.calculateIntegers(100000);
public static void main(String[] args) {
int minNumberCount = 5;
int maxNumberCount = 2000;
int startInt = 2;
int endInt = 1000000;
for (int numberCount = minNumberCount; numberCount < maxNumberCount+1; numberCount++) {
System.out.println("Analyzing for " + numberCount + " numbers");
int[] numbers = new int[numberCount];
//loop through number sets
for (int firstNum = startInt; firstNum < endInt; firstNum+=2) {
//populate numbers array
for(int j=0; j<numberCount; j++){
numbers[j] = firstNum + j*2;
}
long bottomSum=0;
long topSum=0;
//calculate bottom sum
for(int iter=0; iter<4; iter++){
bottomSum+=numbers[iter];
}
//calculate top sum
for(int iter=numberCount-1; iter>numberCount-6; iter--){
topSum+=numbers[iter];
}
//check if the sums match the sulution criteria
if(checkPrime(quadRoot(bottomSum)) && checkPrime(quadRoot(topSum))){
System.out.println("SOLUTION!");
for (int i = 0; i < numbers.length; i++) {
System.out.print(numbers[i] + " ");
}
System.exit(0);
}
}
}
}
private static boolean checkPrime(int i){
return isPrime[i];
}
private static boolean checkPrime(double i){
return ((i % 1) == 0) && checkPrime((int) i);
}
private static double quadRoot(long n){
return Math.sqrt(Math.sqrt(n));
}
}
このアルゴリズムを想定パラメータ ( max k=2000
、 max n{1}=100000
) で使用すると、解決策が見つかりませんでした。私の質問は次のとおりです。パラメーターの仮定が間違っていますか (この範囲の解決策はありません)、またはアルゴリズム/数値エラーがあり、それが解決策を見つけられなかった理由ですか?
編集: 申し訳ありません - 私の間違い - EVEN ではなく ODD にする必要があります。