Sequence: nth number with exactly n divisors: Difference between revisions
(→{{header|zkl}}: added code) |
m (→{{header|REXX}}: updated the output.) |
||
| Line 436: | Line 436: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
Programming note: this REXX program automatically right justifies the output (for alignment). |
Programming note: this REXX program automatically right justifies the output (for alignment). |
||
<br>If the output is wider than |
<br>If the output is wider than 127 decimal digits (with commas), it is left justified (without truncation). |
||
<lang rexx>/*REXX program finds and displays the Nth number with exactly N divisors. */ |
<lang rexx>/*REXX program finds and displays the Nth number with exactly N divisors. */ |
||
parse arg N . /*obtain optional argument from the CL.*/ |
parse arg N . /*obtain optional argument from the CL.*/ |
||
if N=='' | N=="," then N= 15 /*Not specified? Then use the default.*/ |
if N=='' | N=="," then N= 15 /*Not specified? Then use the default.*/ |
||
w= |
w= 127 /*W: width of the 2nd column of output*/ |
||
say '─divisors─' center("the Nth number with exactly N divisors", w, '─') /*title.*/ |
say '─divisors─' center("the Nth number with exactly N divisors", w, '─') /*title.*/ |
||
@.1= 2; Ps= 1 /*1st prime; number of primes (so far)*/ |
@.1= 2; Ps= 1 /*1st prime; number of primes (so far)*/ |
||
| Line 496: | Line 496: | ||
tell: parse arg _; say center(i, 10) right(_, max(w, length(_) ) ) |
tell: parse arg _; say center(i, 10) right(_, max(w, length(_) ) ) |
||
if i//5==0 then say; return /*display a separator for the eyeballs.*/</lang> |
if i//5==0 then say; return /*display a separator for the eyeballs.*/</lang> |
||
{{out|output|text= when using the input: <tt> |
{{out|output|text= when using the input: <tt> 45 </tt>}} |
||
<pre style="font-size:89%"> |
|||
<pre> |
|||
─divisors─ ───────────────────────────────────────────the Nth number with exactly N divisors────────────────────────────────────────────── |
|||
─divisors─ ─────────────────────────────────the Nth number with exactly N divisors────────────────────────────────── |
|||
1 1 |
1 1 |
||
2 3 |
2 3 |
||
3 25 |
3 25 |
||
4 14 |
4 14 |
||
5 14,641 |
5 14,641 |
||
| ⚫ | |||
7 24,137,569 |
|||
8 70 |
|||
9 1,089 |
|||
10 405 |
|||
11 819,628,286,980,801 |
|||
| ⚫ | |||
13 22,563,490,300,366,186,081 |
|||
14 2,752 |
|||
15 9,801 |
|||
16 462 |
|||
17 21,559,177,407,076,402,401,757,871,041 |
|||
18 1,044 |
|||
19 740,195,513,856,780,056,217,081,017,732,809 |
|||
20 1,520 |
|||
21 141,376 |
|||
22 84,992 |
|||
23 1,658,509,762,573,818,415,340,429,240,403,156,732,495,289 |
|||
24 1,170 |
|||
25 52,200,625 |
|||
26 421,888 |
|||
27 52,900 |
|||
28 9,152 |
|||
29 1,116,713,952,456,127,112,240,969,687,448,211,536,647,543,601,817,400,964,721 |
|||
30 6,768 |
|||
31 1,300,503,809,464,370,725,741,704,158,412,711,229,899,345,159,119,325,157,292,552,449 |
|||
32 3,990 |
|||
33 12,166,144 |
|||
34 9,764,864 |
|||
35 446,265,625 |
|||
36 5,472 |
|||
37 11,282,036,144,040,442,334,289,838,466,416,927,162,302,790,252,609,308,623,697,164,994,458,730,076,798,801 |
|||
38 43,778,048 |
|||
39 90,935,296 |
|||
40 10,416 |
|||
41 1,300,532,588,674,810,624,476,094,551,095,787,816,112,173,600,565,095,470,117,230,812,218,524,514,342,511,947,837,104,801 |
|||
| ⚫ | |||
42 46,400 |
|||
43 635,918,448,514,386,699,807,643,535,977,466,343,285,944,704,172,890,141,356,181,792,680,152,445,568,879,925,105,775,366,910,081 |
|||
| ⚫ | |||
44 240,640 |
|||
37 11,282,036,144,040,442,334,289,838,466,416,927,162,302,790,252,609,308,623,697,164,994,458,730,076,798,801 |
|||
45 327,184 |
|||
</pre> |
</pre> |
||
Revision as of 18:16, 14 April 2019
Calculate the sequence where each term an is the nth that has n divisors.
- Task
Show here, on this page, at least the first 15 terms of the sequence.
- See also
- Related tasks
Go
This makes use of the relationship: a[p] = prime[p]^(p-1) if p is prime, mentioned in the blurb for A073916 (and also on the talk page) to calculate the larger terms, some of which require big.Int in Go. It also makes use of another hint on the talk page that all odd terms are square numbers.
The remaining terms (up to the 33rd) are not particularly large and so are calculated by brute force. <lang go>package main
import (
"fmt" "math" "math/big"
)
var bi = new(big.Int)
func isPrime(n int) bool {
bi.SetUint64(uint64(n)) return bi.ProbablyPrime(0)
}
func generateSmallPrimes(n int) []int {
primes := make([]int, n)
primes[0] = 2
for i, count := 3, 1; count < n; i += 2 {
if isPrime(i) {
primes[count] = i
count++
}
}
return primes
}
func countDivisors(n int) int {
count := 1
for n%2 == 0 {
n >>= 1
count++
}
for d := 3; d*d <= n; d += 2 {
q, r := n/d, n%d
if r == 0 {
dc := 0
for r == 0 {
dc += count
n = q
q, r = n/d, n%d
}
count += dc
}
}
if n != 1 {
count *= 2
}
return count
}
func main() {
const max = 33
primes := generateSmallPrimes(max)
z := new(big.Int)
p := new(big.Int)
fmt.Println("The first", max, "terms in the sequence are:")
for i := 1; i <= max; i++ {
if isPrime(i) {
z.SetUint64(uint64(primes[i-1]))
p.SetUint64(uint64(i - 1))
z.Exp(z, p, nil)
fmt.Printf("%2d : %d\n", i, z)
} else {
count := 0
for j := 1; ; j++ {
if i%2 == 1 {
sq := int(math.Sqrt(float64(j)))
if sq*sq != j {
continue
}
}
if countDivisors(j) == i {
count++
if count == i {
fmt.Printf("%2d : %d\n", i, j)
break
}
}
}
}
}
}</lang>
- Output:
The first 33 terms in the sequence are: 1 : 1 2 : 3 3 : 25 4 : 14 5 : 14641 6 : 44 7 : 24137569 8 : 70 9 : 1089 10 : 405 11 : 819628286980801 12 : 160 13 : 22563490300366186081 14 : 2752 15 : 9801 16 : 462 17 : 21559177407076402401757871041 18 : 1044 19 : 740195513856780056217081017732809 20 : 1520 21 : 141376 22 : 84992 23 : 1658509762573818415340429240403156732495289 24 : 1170 25 : 52200625 26 : 421888 27 : 52900 28 : 9152 29 : 1116713952456127112240969687448211536647543601817400964721 30 : 6768 31 : 1300503809464370725741704158412711229899345159119325157292552449 32 : 3990 33 : 12166144
Java
<lang java>import java.util.ArrayList; import java.math.BigInteger; import static java.lang.Math.sqrt;
public class OEIS_A073916 {
static boolean is_prime(int n) {
return BigInteger.valueOf(n).isProbablePrime(10);
}
static ArrayList<Integer> generate_small_primes(int n) {
ArrayList<Integer> primes = new ArrayList<Integer>();
primes.add(2);
for (int i = 3; primes.size() < n; i += 2) {
if (is_prime(i)) primes.add(i);
}
return primes;
}
static int count_divisors(int n) {
int count = 1;
while (n % 2 == 0) {
n >>= 1;
++count;
}
for (int d = 3; d * d <= n; d += 2) {
int q = n / d;
int r = n % d;
if (r == 0) {
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;
}
public static void main(String[] args) {
final int max = 33;
ArrayList<Integer> primes = generate_small_primes(max);
System.out.printf("The first %d terms of the sequence are:\n", max);
for (int i = 1; i <= max; ++i) {
if (is_prime(i)) {
BigInteger z = BigInteger.valueOf(primes.get(i - 1));
z = z.pow(i - 1);
System.out.printf("%2d : %d\n", i, z);
} else {
for (int j = 1, count = 0; ; ++j) {
if (i % 2 == 1) {
int sq = (int)sqrt(j);
if (sq * sq != j) continue;
}
if (count_divisors(j) == i) {
if (++count == i) {
System.out.printf("%2d : %d\n", i, j);
break;
}
}
}
}
}
}
}</lang>
- Output:
The first 33 terms of the sequence are: 1 : 1 2 : 3 3 : 25 4 : 14 5 : 14641 6 : 44 7 : 24137569 8 : 70 9 : 1089 10 : 405 11 : 819628286980801 12 : 160 13 : 22563490300366186081 14 : 2752 15 : 9801 16 : 462 17 : 21559177407076402401757871041 18 : 1044 19 : 740195513856780056217081017732809 20 : 1520 21 : 141376 22 : 84992 23 : 1658509762573818415340429240403156732495289 24 : 1170 25 : 52200625 26 : 421888 27 : 52900 28 : 9152 29 : 1116713952456127112240969687448211536647543601817400964721 30 : 6768 31 : 1300503809464370725741704158412711229899345159119325157292552449 32 : 3990 33 : 12166144
Kotlin
<lang scala>// Version 1.3.21
import java.math.BigInteger import kotlin.math.sqrt
const val MAX = 33
fun isPrime(n: Int) = BigInteger.valueOf(n.toLong()).isProbablePrime(10)
fun generateSmallPrimes(n: Int): List<Int> {
val primes = mutableListOf<Int>()
primes.add(2)
var i = 3
while (primes.size < n) {
if (isPrime(i)) {
primes.add(i)
}
i += 2
}
return primes
}
fun countDivisors(n: Int): Int {
var nn = n
var count = 1
while (nn % 2 == 0) {
nn = nn shr 1
count++
}
var d = 3
while (d * d <= nn) {
var q = nn / d
var r = nn % d
if (r == 0) {
var dc = 0
while (r == 0) {
dc += count
nn = q
q = nn / d
r = nn % d
}
count += dc
}
d += 2
}
if (nn != 1) count *= 2
return count
}
fun main() {
var primes = generateSmallPrimes(MAX)
println("The first $MAX terms in the sequence are:")
for (i in 1..MAX) {
if (isPrime(i)) {
var z = BigInteger.valueOf(primes[i - 1].toLong())
z = z.pow(i - 1)
System.out.printf("%2d : %d\n", i, z)
} else {
var count = 0
var j = 1
while (true) {
if (i % 2 == 1) {
val sq = sqrt(j.toDouble()).toInt()
if (sq * sq != j) {
j++
continue
}
}
if (countDivisors(j) == i) {
if (++count == i) {
System.out.printf("%2d : %d\n", i, j)
break
}
}
j++
}
}
}
}</lang>
- Output:
The first 33 terms in the sequence are: 1 : 1 2 : 3 3 : 25 4 : 14 5 : 14641 6 : 44 7 : 24137569 8 : 70 9 : 1089 10 : 405 11 : 819628286980801 12 : 160 13 : 22563490300366186081 14 : 2752 15 : 9801 16 : 462 17 : 21559177407076402401757871041 18 : 1044 19 : 740195513856780056217081017732809 20 : 1520 21 : 141376 22 : 84992 23 : 1658509762573818415340429240403156732495289 24 : 1170 25 : 52200625 26 : 421888 27 : 52900 28 : 9152 29 : 1116713952456127112240969687448211536647543601817400964721 30 : 6768 31 : 1300503809464370725741704158412711229899345159119325157292552449 32 : 3990 33 : 12166144
Perl
<lang perl>use strict; use warnings; use bigint; use ntheory <nth_prime is_prime divisors>;
my $limit = 20;
print "First $limit terms of OEIS:A073916\n";
for my $n (1..$limit) {
if ($n > 4 and is_prime($n)) {
print nth_prime($n)**($n-1) . ' ';
} else {
my $i = my $x = 0;
while (1) {
my $nn = $n%2 ? ++$x**2 : ++$x;
next unless $n == divisors($nn) and ++$i == $n;
print "$nn " and last;
}
}
}</lang>
- Output:
First 20 terms of OEIS:A073916 1 3 25 14 14641 44 24137569 70 1089 405 819628286980801 160 22563490300366186081 2752 9801 462 21559177407076402401757871041 1044 740195513856780056217081017732809 1520
Perl 6
<lang perl6>sub div-count (\x) {
return 2 if x.is-prime;
+flat (1 .. x.sqrt.floor).map: -> \d {
unless x % d { my \y = x div d; y == d ?? y !! (y, d) }
}
}
my $limit = 20;
my @primes = grep { .is-prime }, 1..*; @primes[$limit]; # prime the array. SCNR
put "First $limit terms of OEIS:A073916"; put (1..$limit).hyper(:2batch).map: -> $n {
($n > 4 and $n.is-prime) ??
exp($n - 1, @primes[$n - 1]) !!
do {
my $i = 0;
my $iterator = $n %% 2 ?? (1..*) !! (1..*).map: *²;
$iterator.first: {
next unless $n == .&div-count;
next unless ++$i == $n;
$_
}
}
};</lang>
First 20 terms of OEIS:A073916 1 3 25 14 14641 44 24137569 70 1089 405 819628286980801 160 22563490300366186081 2752 9801 462 21559177407076402401757871041 1044 740195513856780056217081017732809 1520
REXX
Programming note: this REXX program automatically right justifies the output (for alignment).
If the output is wider than 127 decimal digits (with commas), it is left justified (without truncation).
<lang rexx>/*REXX program finds and displays the Nth number with exactly N divisors. */
parse arg N . /*obtain optional argument from the CL.*/
if N== | N=="," then N= 15 /*Not specified? Then use the default.*/
w= 127 /*W: width of the 2nd column of output*/
say '─divisors─' center("the Nth number with exactly N divisors", w, '─') /*title.*/
@.1= 2; Ps= 1 /*1st prime; number of primes (so far)*/
do p=3 until Ps==N /* [↓] gen N primes, store in @ array.*/
if \isPrime(p) then iterate; Ps= Ps + 1; @.Ps= p
end /*gp*/
!.= /*the ! array is used for memoization*/
do i=1 for N; odd= i//2 /*step through a number of divisors. */
if odd then if isPrime(i) then do; call tell commas( pPow() ); iterate
end
#= 0 /*the number of occurrences for #div. */
do j=1; jj= j /*now, search for a number that ≡ #divs*/
if odd then jj= j*j /*Odd and non-prime? Calculate square.*/
if !.jj==. then iterate /*has this number already been found? */
d= #divs(jj); if d\==i then iterate /*get # divisors; Is not equal? Skip.*/
!.jj=. /*mark as having found #divs for this J*/
#= # + 1 /*bump number of occurrences for #div. */
if #\==i then iterate /*Not correct occurrence? Keep looking.*/
call tell commas(jj) /*display Nth number with #divs*/
leave /*found a number, so now get the next I*/
end /*j*/
end /*i*/
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg _; do j=length(_)-3 to 1 by -3; _=insert(',', _, j); end; return _ pPow: numeric digits 1000; return @.i**(i-1) /*temporarily increase decimal digits. */ /*──────────────────────────────────────────────────────────────────────────────────────*/
- divs: procedure; parse arg x 1 y /*X and Y: both set from 1st argument.*/
if x<7 then do /*handle special cases for numbers < 7.*/
if x<3 then return x /* " " " " one and two.*/
if x<5 then return x - 1 /* " " " " three & four*/
if x==5 then return 2 /* " " " " five. */
if x==6 then return 4 /* " " " " six. */
end
odd= x // 2 /*check if X is odd or not. */
if odd then do; #= 1; end /*Odd? Assume Pdivisors count of 1.*/
else do; #= 3; y= x%2; end /*Even? " " " " 3.*/
/* [↑] start with known num of Pdivs.*/
do k=3 for x%2-3 by 1+odd while k<y /*for odd numbers, skip evens.*/
if x//k==0 then do /*if no remainder, then found a divisor*/
#=#+2; y=x%k /*bump # Pdivs, calculate limit Y. */
if k>=y then do; #= #-1; leave; end /*limit?*/
end /* ___ */
else if k*k>x then leave /*only divide up to √ x */
end /*k*/ /* [↑] this form of DO loop is faster.*/
return #+1 /*bump "proper divisors" to "divisors".*/
/*──────────────────────────────────────────────────────────────────────────────────────*/ isPrime: procedure; parse arg #; if wordpos(#, '2 3 5 7 11 13')\==0 then return 1
if #<2 then return 0; if #//2==0 | #//3==0 | #//5==0 | #//7==0 then return 0
if # // 2==0 | # // 3 ==0 then return 0
do j=11 by 6 until j*j>#; if # // j==0 | # // (J+2)==0 then return 0
end /*j*/ /* ___ */
return 1 /*Exceeded √ # ? Then # is prime. */
/*──────────────────────────────────────────────────────────────────────────────────────*/ tell: parse arg _; say center(i, 10) right(_, max(w, length(_) ) )
if i//5==0 then say; return /*display a separator for the eyeballs.*/</lang>
- output when using the input: 45
─divisors─ ───────────────────────────────────────────the Nth number with exactly N divisors──────────────────────────────────────────────
1 1
2 3
3 25
4 14
5 14,641
6 44
7 24,137,569
8 70
9 1,089
10 405
11 819,628,286,980,801
12 160
13 22,563,490,300,366,186,081
14 2,752
15 9,801
16 462
17 21,559,177,407,076,402,401,757,871,041
18 1,044
19 740,195,513,856,780,056,217,081,017,732,809
20 1,520
21 141,376
22 84,992
23 1,658,509,762,573,818,415,340,429,240,403,156,732,495,289
24 1,170
25 52,200,625
26 421,888
27 52,900
28 9,152
29 1,116,713,952,456,127,112,240,969,687,448,211,536,647,543,601,817,400,964,721
30 6,768
31 1,300,503,809,464,370,725,741,704,158,412,711,229,899,345,159,119,325,157,292,552,449
32 3,990
33 12,166,144
34 9,764,864
35 446,265,625
36 5,472
37 11,282,036,144,040,442,334,289,838,466,416,927,162,302,790,252,609,308,623,697,164,994,458,730,076,798,801
38 43,778,048
39 90,935,296
40 10,416
41 1,300,532,588,674,810,624,476,094,551,095,787,816,112,173,600,565,095,470,117,230,812,218,524,514,342,511,947,837,104,801
42 46,400
43 635,918,448,514,386,699,807,643,535,977,466,343,285,944,704,172,890,141,356,181,792,680,152,445,568,879,925,105,775,366,910,081
44 240,640
45 327,184
Sidef
<lang ruby>func f(n {.is_prime}) {
n.prime**(n-1)
}
func f(n) {
n.th { .sigma0 == n }
}
say 20.of { f(_+1) }</lang>
- Output:
[1, 3, 25, 14, 14641, 44, 24137569, 70, 1089, 405, 819628286980801, 160, 22563490300366186081, 2752, 9801, 462, 21559177407076402401757871041, 1044, 740195513856780056217081017732809, 1520]
zkl
Using GMP (GNU Multiple Precision Arithmetic Library, probabilistic primes), because it is easy and fast to generate primes.
Extensible prime generator#zkl could be used instead. <lang zkl>var [const] BI=Import("zklBigNum"), pmax=25; // libGMP p:=BI(1); primes:=pmax.pump(List(0), p.nextPrime, "copy"); //-->(0,3,5,7,11,13,17,19,...)
fcn countDivisors(n){
count:=1;
while(n%2==0){ n/=2; count+=1; }
foreach d in ([3..*,2]){
q,r := n/d, n%d;
if(r==0){
dc:=0; while(r==0){ dc+=count; n,q,r = q, n/d, n%d; } count+=dc;
}
if(d*d > n) break;
}
if(n!=1) count*=2;
count
}
println("The first ", pmax, " terms in the sequence are:"); foreach i in ([1..pmax]){
if(BI(i).probablyPrime()) println("%2d : %,d".fmt(i,primes[i].pow(i-1)));
else{
count:=0;
foreach j in ([1..*]){
if(i%2==1 and j != j.toFloat().sqrt().toInt().pow(2)) continue;
if(countDivisors(j) == i){ count+=1; if(count==i){ println("%2d : %,d".fmt(i,j)); break; } }
} }
}</lang>
- Output:
The first 25 terms in the sequence are: 1 : 1 2 : 3 3 : 25 4 : 14 5 : 14,641 6 : 44 7 : 24,137,569 8 : 70 9 : 1,089 10 : 405 11 : 819,628,286,980,801 12 : 160 13 : 22,563,490,300,366,186,081 14 : 2,752 15 : 9,801 16 : 462 17 : 21,559,177,407,076,402,401,757,871,041 18 : 1,044 19 : 740,195,513,856,780,056,217,081,017,732,809 20 : 1,520 21 : 141,376 22 : 84,992 23 : 1,658,509,762,573,818,415,340,429,240,403,156,732,495,289 24 : 1,170 25 : 52,200,625