Sequence: nth number with exactly n divisors: Difference between revisions
Sequence: nth number with exactly n divisors (view source)
Revision as of 00:26, 15 July 2021
, 2 years ago→{{header|Factor}}
Line 263:
A073916(14) = 2752
A073916(15) = 9801</pre>
=={{header|D}}==
{{trans|Java}}
<lang d>import std.bigint;
import std.math;
import std.stdio;
bool isPrime(long test) {
if (test == 2) {
return true;
}
if (test % 2 == 0) {
return false;
}
for (long d = 3 ; d * d <= test; d += 2) {
if (test % d == 0) {
return false;
}
}
return true;
}
int[] calcSmallPrimes(int numPrimes) {
int[] smallPrimes;
smallPrimes ~= 2;
int count = 0;
int n = 3;
while (count < numPrimes) {
if (isPrime(n)) {
smallPrimes ~= n;
count++;
}
n += 2;
}
return smallPrimes;
}
immutable MAX = 45;
immutable smallPrimes = calcSmallPrimes(MAX);
int getDivisorCount(long n) {
int count = 1;
while (n % 2 == 0) {
n /= 2;
count += 1;
}
for (long d = 3; d * d <= n; d += 2) {
long q = n / d;
long r = n % d;
int dc = 0;
while (r == 0) {
dc += count;
n = q;
q = n / d;
r = n % d;
}
count += dc;
}
if (n != 1) {
count *= 2;
}
return count;
}
BigInt OEISA073916(int n) {
if (isPrime(n) ) {
return BigInt(smallPrimes[n-1]) ^^ (n - 1);
}
int count = 0;
int result = 0;
for (int i = 1; count < n; i++) {
if (n % 2 == 1) {
// The solution for an odd (non-prime) term is always a square number
int root = cast(int) sqrt(cast(real) i);
if (root * root != i) {
continue;
}
}
if (getDivisorCount(i) == n) {
count++;
result = i;
}
}
return BigInt(result);
}
void main() {
foreach (n; 1 .. MAX + 1) {
writeln("A073916(", n, ") = ", OEISA073916(n));
}
}</lang>
{{out}}
<pre>A073916(1) = 1
A073916(2) = 3
A073916(3) = 25
A073916(4) = 14
A073916(5) = 14641
A073916(6) = 44
A073916(7) = 24137569
A073916(8) = 70
A073916(9) = 1089
A073916(10) = 405
A073916(11) = 819628286980801
A073916(12) = 160
A073916(13) = 22563490300366186081
A073916(14) = 2752
A073916(15) = 9801
A073916(16) = 462
A073916(17) = 21559177407076402401757871041
A073916(18) = 1044
A073916(19) = 740195513856780056217081017732809
A073916(20) = 1520
A073916(21) = 141376
A073916(22) = 84992
A073916(23) = 1658509762573818415340429240403156732495289
A073916(24) = 1170
A073916(25) = 52200625
A073916(26) = 421888
A073916(27) = 52900
A073916(28) = 9152
A073916(29) = 1116713952456127112240969687448211536647543601817400964721
A073916(30) = 6768
A073916(31) = 1300503809464370725741704158412711229899345159119325157292552449
A073916(32) = 3990
A073916(33) = 12166144
A073916(34) = 9764864
A073916(35) = 446265625
A073916(36) = 5472
A073916(37) = 11282036144040442334289838466416927162302790252609308623697164994458730076798801
A073916(38) = 43778048
A073916(39) = 90935296
A073916(40) = 10416
A073916(41) = 1300532588674810624476094551095787816112173600565095470117230812218524514342511947837104801
A073916(42) = 46400
A073916(43) = 635918448514386699807643535977466343285944704172890141356181792680152445568879925105775366910081
A073916(44) = 240640
A073916(45) = 327184</pre>
=={{header|Factor}}==
| |||