79 lines
2 KiB
JavaScript
79 lines
2 KiB
JavaScript
// Chowla function: calculates sum of proper divisors of n (excluding n itself)
|
|
function chowla(n) {
|
|
let sum = 0;
|
|
for (let i = 2; i * i <= n; i++) {
|
|
if (n % i === 0) {
|
|
const j = n / i;
|
|
sum += i + (i === j ? 0 : j);
|
|
}
|
|
}
|
|
return sum;
|
|
}
|
|
|
|
// Sieve function: returns array where true denotes composite, false denotes prime
|
|
// Only interested in odd numbers >= 3
|
|
function sieve(limit) {
|
|
// True denotes composite, false denotes prime
|
|
const c = new Array(limit).fill(false);
|
|
|
|
for (let i = 3; i * 3 < limit; i += 2) {
|
|
if (!c[i] && chowla(i) === 0) {
|
|
for (let j = 3 * i; j < limit; j += 2 * i) {
|
|
c[j] = true;
|
|
}
|
|
}
|
|
}
|
|
return c;
|
|
}
|
|
|
|
// Main execution
|
|
function main() {
|
|
// Part 1: Print chowla values for 1-37
|
|
console.log("Chowla function values for 1-37:");
|
|
for (let i = 1; i <= 37; i++) {
|
|
console.log(`chowla(${i}) = ${chowla(i)}`);
|
|
}
|
|
console.log("\n");
|
|
|
|
// Part 2: Count primes up to powers of 10
|
|
console.log("Prime counting using Chowla's sieve:");
|
|
let count = 1;
|
|
const limit = 10000000; // 1e7
|
|
let power = 100;
|
|
|
|
const c = sieve(limit);
|
|
|
|
for (let i = 3; i < limit; i += 2) {
|
|
if (!c[i]) count++;
|
|
|
|
if (i === power - 1) {
|
|
console.log(`Count of primes up to ${power.toLocaleString()} = ${count.toLocaleString()}`);
|
|
power *= 10;
|
|
}
|
|
}
|
|
console.log("\n");
|
|
|
|
// Part 3: Find perfect numbers
|
|
console.log("Perfect numbers <= 35,000,000:");
|
|
count = 0;
|
|
const perfectLimit = 35000000;
|
|
|
|
let k = 2, kk = 3, p;
|
|
for (let i = 2; ; i++) {
|
|
p = k * kk;
|
|
if (p > perfectLimit) break;
|
|
|
|
if (chowla(p) === p - 1) {
|
|
console.log(`${p.toLocaleString()} is a perfect number`);
|
|
count++;
|
|
}
|
|
|
|
k = kk + 1;
|
|
kk += k;
|
|
}
|
|
|
|
console.log(`\nThere are ${count} perfect numbers <= 35,000,000`);
|
|
}
|
|
|
|
// Execute the main function
|
|
main();
|