Sequence: nth number with exactly n divisors: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) (→{{header|Perl 6}}: Expand a bit, add an online link) |
(→{{header|REXX}}: added the REXX computer programming language for this task.) |
||
| Line 49: | Line 49: | ||
<pre>First 20 terms of OEIS:A073916 |
<pre>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</pre> |
1 3 25 14 14641 44 24137569 70 1089 405 819628286980801 160 22563490300366186081 2752 9801 462 21559177407076402401757871041 1044 740195513856780056217081017732809 1520</pre> |
||
=={{header|REXX}}== |
|||
Programming note: this REXX version can't compute the 11<sup>th</sup> or 13<sup>th</sup> term in this sequence in a reasonable time. |
|||
<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= 10 /*Not specified? Then use the default.*/ |
|||
say '──divisors── ──Nth number with exactly N divisors──' /*display title for numbers.*/ |
|||
@.= /*the @ array is used for memoization*/ |
|||
do i=1 for N /*step through a number of divisors. */ |
|||
#= 0 /*the number of occurrances for #div. */ |
|||
do j=1 /*now, search for a number that ≡ #divs*/ |
|||
if @.j==. then iterate /*has this number already been found? */ |
|||
d= #divs(j); if d\==i then iterate /*get # divisors; Is not equal? Skip.*/ |
|||
@.j=. /*mark as having found #divs for this J*/ |
|||
#= # + 1 /*bump number of occurrances for #div. */ |
|||
if #\==i then iterate /*Not correct occurrance? Keep looking.*/ |
|||
say center(i, 12) right(commas(j), 29) /*display the 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 _ |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
#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".*/</lang> |
|||
{{out|output|text= when using the default input:}} |
|||
<pre> |
|||
──divisors── ──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 |
|||
</pre> |
|||
Revision as of 18:22, 11 April 2019
Sequence: nth number with exactly n divisors is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
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
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 version can't compute the 11th or 13th term in this sequence in a reasonable time. <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= 10 /*Not specified? Then use the default.*/ say '──divisors── ──Nth number with exactly N divisors──' /*display title for numbers.*/ @.= /*the @ array is used for memoization*/
do i=1 for N /*step through a number of divisors. */
#= 0 /*the number of occurrances for #div. */
do j=1 /*now, search for a number that ≡ #divs*/
if @.j==. then iterate /*has this number already been found? */
d= #divs(j); if d\==i then iterate /*get # divisors; Is not equal? Skip.*/
@.j=. /*mark as having found #divs for this J*/
#= # + 1 /*bump number of occurrances for #div. */
if #\==i then iterate /*Not correct occurrance? Keep looking.*/
say center(i, 12) right(commas(j), 29) /*display the 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 _ /*──────────────────────────────────────────────────────────────────────────────────────*/
- 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".*/</lang>
- output when using the default input:
──divisors── ──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