Anonymous user
Mian-Chowla sequence: Difference between revisions
→{{header|J}}
(Add Factor) |
|||
Line 744:
22526 23291 23564 23881 24596 24768 25631 26037 26255 27219
0 1 0 0 0 0 0 0 0 0
</pre>
=={{header|Java}}==
<lang 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" : ""));
}
}
}
}
</lang>
{{out}}
<pre>
First 30 terms of the Mian–Chowla sequence.
1 2 4 8 13 21 31 45 66 81 97 123 148 182 204 252 290 361 401 475 565 593 662 775 822 916 970 1016 1159 1312
Terms 91 through 100 of the Mian–Chowla sequence.
22526 23291 23564 23881 24596 24768 25631 26037 26255 27219
Elapsed = 220 ms
</pre>
| |||