144 lines
3.9 KiB
JavaScript
144 lines
3.9 KiB
JavaScript
class SegmentedPrimeIterator {
|
|
constructor(limit) {
|
|
this.squareRoot = Math.floor(Math.sqrt(limit));
|
|
this.low = 0;
|
|
this.high = this.squareRoot;
|
|
this.index = 0;
|
|
this.primes = [];
|
|
this.smallPrimes = [];
|
|
this.smallSieve(this.squareRoot);
|
|
}
|
|
|
|
next() {
|
|
if (this.index === this.primes.length) {
|
|
this.index = 0;
|
|
this.segmentedSieve();
|
|
}
|
|
return this.primes[this.index++];
|
|
}
|
|
|
|
segmentedSieve() {
|
|
this.low += this.squareRoot;
|
|
this.high += this.squareRoot;
|
|
|
|
const markedPrime = new Array(this.squareRoot).fill(true);
|
|
|
|
for (let i = 0; i < this.smallPrimes.length; i++) {
|
|
let lowLimit = Math.floor(this.low / this.smallPrimes[i]) * this.smallPrimes[i];
|
|
if (lowLimit < this.low) {
|
|
lowLimit += this.smallPrimes[i];
|
|
}
|
|
|
|
for (let j = lowLimit; j < this.high; j += this.smallPrimes[i]) {
|
|
markedPrime[j - this.low] = false;
|
|
}
|
|
}
|
|
|
|
this.primes = [];
|
|
for (let i = this.low; i < this.high; i++) {
|
|
if (markedPrime[i - this.low]) {
|
|
this.primes.push(i);
|
|
}
|
|
}
|
|
}
|
|
|
|
smallSieve(squareRoot) {
|
|
const markedPrime = new Array(squareRoot + 1).fill(true);
|
|
|
|
for (let p = 2; p * p <= squareRoot; p++) {
|
|
if (markedPrime[p]) {
|
|
for (let i = p * p; i <= squareRoot; i += p) {
|
|
markedPrime[i] = false;
|
|
}
|
|
}
|
|
}
|
|
|
|
for (let p = 2; p <= squareRoot; p++) {
|
|
if (markedPrime[p]) {
|
|
this.primes.push(p);
|
|
}
|
|
}
|
|
this.smallPrimes = [...this.primes];
|
|
}
|
|
}
|
|
|
|
class SisyphusIterator {
|
|
constructor(limit) {
|
|
this.previous = 2;
|
|
this.prime = 0;
|
|
this.primeIterator = new SegmentedPrimeIterator(limit);
|
|
}
|
|
|
|
next() {
|
|
if ((this.previous & 1) === 0) {
|
|
this.previous >>= 1;
|
|
} else {
|
|
this.prime = this.primeIterator.next();
|
|
this.previous += this.prime;
|
|
}
|
|
return this.previous;
|
|
}
|
|
|
|
getPrime() {
|
|
return this.prime;
|
|
}
|
|
}
|
|
|
|
function display(found, search, target, prefix, suffix) {
|
|
console.log();
|
|
console.log(prefix + target + " terms:");
|
|
const results = [];
|
|
for (let i = 1; i < found.length; i++) {
|
|
if (found[i] === search) {
|
|
results.push(i);
|
|
}
|
|
}
|
|
console.log(results.join(" ") + (suffix ? " " + suffix : ""));
|
|
}
|
|
|
|
function main() {
|
|
const limit = 100_000_000;
|
|
const iterator = new SisyphusIterator(1_000_000_000_000);
|
|
|
|
console.log("The first 100 members of the Sisyphus sequence are:");
|
|
const found = new Array(250).fill(0);
|
|
let next = 0;
|
|
let count = 0;
|
|
let target = 1_000;
|
|
|
|
while (target <= limit) {
|
|
count += 1;
|
|
next = iterator.next();
|
|
|
|
if (next < 250) {
|
|
found[next]++;
|
|
}
|
|
|
|
if (count <= 100) {
|
|
process.stdout.write(next.toString().padStart(3) + (count % 10 === 0 ? "\n" : " "));
|
|
if (count === 100) {
|
|
console.log();
|
|
}
|
|
} else if (count === target) {
|
|
target *= 10;
|
|
console.log(`${target.toString().padStart(11)}th member is ${next.toString().padStart(11)} and highest prime needed is ${iterator.getPrime().toString().padStart(10)}`);
|
|
}
|
|
}
|
|
|
|
display(found, 0, target, "These numbers under 250 occur the most in the first ", "");
|
|
|
|
const max = Math.max(...found);
|
|
display(found, max, target,
|
|
"These numbers under 250 occur the most in the first ",
|
|
"all occur " + max + " times");
|
|
|
|
while (next !== 36) {
|
|
count += 1;
|
|
next = iterator.next();
|
|
}
|
|
|
|
console.log();
|
|
console.log(count + "th member is " + next + " and highest prime needed is " + iterator.getPrime());
|
|
}
|
|
|
|
main();
|