Skip to content

Instantly share code, notes, and snippets.

@marcin-chwedczuk
Created May 1, 2019 11:36
Show Gist options
  • Save marcin-chwedczuk/229ce1d30ad5b652fb87a539b0a7efbf to your computer and use it in GitHub Desktop.
Save marcin-chwedczuk/229ce1d30ad5b652fb87a539b0a7efbf to your computer and use it in GitHub Desktop.
Minimal integer n > 0 that for each prime if (p-1) | n then p | n
// Problem:
// Find minimal integer number n > 0 that
// for any prime p:
// if (p - 1) | n then p | n
// where `|` means divide.
//
function gen_primes() {
var N = 1000;
var primes = Array(N);
var i;
for (i = 0; i < N; i++) {
primes[i] = i;
}
primes[0] = primes[1] = -1;
var step = 1;
while (step < primes.length) {
step++;
if (primes[step] === -1) continue;
for (i = step*2; i < primes.length; i += step) {
primes[i] = -1;
}
}
return primes.filter(function(x) { return x !== -1; });
}
var ps = [];
var n = 1;
var P = gen_primes()
var curr = 0;
while (curr < P.length) {
var pp = P[curr++];
if ( (n % pp) === 0 ) continue;
if ( (n % (pp-1)) === 0 ) {
n *= pp;
ps.push(pp);
}
}
console.log(ps);
console.log('n = ', n);
// ans: 1806
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment