76 lines
2.6 KiB
Java
76 lines
2.6 KiB
Java
|
import java.util.Arrays;
|
|||
|
|
|
|||
|
|
public class MianChowlaSequence {
|
|||
|
|
|
|||
|
|
public static void main(String[] args) {
|
|||
|
|
long start = System.currentTimeMillis();
|
|||
|
|
System.out.println("First 30 terms of the Mian–Chowla sequence.");
|
|||
|
|
mianChowla(1, 30);
|
|||
|
|
System.out.println("Terms 91 through 100 of the Mian–Chowla sequence.");
|
|||
|
|
mianChowla(91, 100);
|
|||
|
|
long end = System.currentTimeMillis();
|
|||
|
|
System.out.printf("Elapsed = %d ms%n", (end-start));
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
private static void mianChowla(int minIndex, int maxIndex) {
|
|||
|
|
int [] sums = new int[1];
|
|||
|
|
int [] chowla = new int[maxIndex+1];
|
|||
|
|
sums[0] = 2;
|
|||
|
|
chowla[0] = 0;
|
|||
|
|
chowla[1] = 1;
|
|||
|
|
if ( minIndex == 1 ) {
|
|||
|
|
System.out.printf("%d ", 1);
|
|||
|
|
}
|
|||
|
|
int chowlaLength = 1;
|
|||
|
|
for ( int n = 2 ; n <= maxIndex ; n++ ) {
|
|||
|
|
|
|||
|
|
// Sequence is strictly increasing.
|
|||
|
|
int test = chowla[n - 1];
|
|||
|
|
// Bookkeeping. Generate only new sums.
|
|||
|
|
int[] sumsNew = Arrays.copyOf(sums, sums.length + n);
|
|||
|
|
int sumNewLength = sums.length;
|
|||
|
|
int savedsSumNewLength = sumNewLength;
|
|||
|
|
|
|||
|
|
// Generate test candidates for the next value of the sequence.
|
|||
|
|
boolean found = false;
|
|||
|
|
while ( ! found ) {
|
|||
|
|
test++;
|
|||
|
|
found = true;
|
|||
|
|
sumNewLength = savedsSumNewLength;
|
|||
|
|
// Generate test sums
|
|||
|
|
for ( int j = 0 ; j <= chowlaLength ; j++ ) {
|
|||
|
|
int testSum = (j == 0 ? test : chowla[j]) + test;
|
|||
|
|
boolean duplicate = false;
|
|||
|
|
|
|||
|
|
// Check if test Sum in array
|
|||
|
|
for ( int k = 0 ; k < sumNewLength ; k++ ) {
|
|||
|
|
if ( sumsNew[k] == testSum ) {
|
|||
|
|
duplicate = true;
|
|||
|
|
break;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
if ( ! duplicate ) {
|
|||
|
|
// Add to array
|
|||
|
|
sumsNew[sumNewLength] = testSum;
|
|||
|
|
sumNewLength++;
|
|||
|
|
}
|
|||
|
|
else {
|
|||
|
|
// Duplicate found. Therefore, test candidate of the next value of the sequence is not OK.
|
|||
|
|
found = false;
|
|||
|
|
break;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// Bingo! Now update bookkeeping.
|
|||
|
|
chowla[n] = test;
|
|||
|
|
chowlaLength++;
|
|||
|
|
sums = sumsNew;
|
|||
|
|
if ( n >= minIndex ) {
|
|||
|
|
System.out.printf("%d %s", chowla[n], (n==maxIndex ? "\n" : ""));
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
}
|