Skip to content

Instantly share code, notes, and snippets.

@gkucmierz
Created July 26, 2023 07:16
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save gkucmierz/58b16f17914acbc6d26c233e83e05c53 to your computer and use it in GitHub Desktop.
Save gkucmierz/58b16f17914acbc6d26c233e83e05c53 to your computer and use it in GitHub Desktop.
function factors(n) {
let max = Math.floor(Math.sqrt(n));
let res = [];
for (let i = 2; i <= max; ++i) {
if (n % i === 0) {
res.push(i);
n /= i;
max = Math.floor(Math.sqrt(n));
i = (Math.min(...res) || 2) - 1;
}
}
res.push(n);
return res;
}
const groupToMap = (array, cb = el => el) => {
const map = new Map();
array.map((el, i) => {
const key = cb(el, i);
if (map.has(key)) {
map.get(key).push(el);
} else {
map.set(key, [el]);
}
});
return map;
};
function gcd(a, b) {
if (a < 0) a = -a;
if (b < 0) b = -b;
if (b > a) {
[a, b] = [b, a];
}
while (1) {
if (b == 0) return a;
a %= b;
if (a == 0) return b;
b %= a;
}
}
const isAchilles = n => {
const f = factors(n);
const grouped = groupToMap(f);
const values = [...grouped.values()];
const gcdLen = values.map(arr => arr.length).reduce(gcd);
if (gcdLen !== 1) return false;
return values.length > 1 && values.every(arr => arr.length > 1);
};
// https://oeis.org/A052486
for (let i = 0; i < 1e4; ++i) {
console.log(i, isAchilles(i));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment