Sequence: smallest number greater than previous term with exactly n divisors: Difference between revisions
m (→{{header|Pascal}}: typo) |
Thundergnat (talk | contribs) (→{{header|Perl 6}}: various tweaks, expand last sequence to 15 terms) |
||
| Line 383: | Line 383: | ||
This task could be interpreted in a few ways. |
This task could be interpreted in a few ways. |
||
Could be the sequence of the '''smallest natural numbers''' such that each <strong>a<sub>n</sub></strong> has '''n''' divisors: [[oeis:A005179|OEIS: |
Could be the sequence of the '''smallest natural numbers''' such that each <strong>a<sub>n</sub></strong> has '''n''' divisors: [[oeis:A005179|OEIS:A005179]]. |
||
Or, could be the sequence where each term <strong>a<sub>n</sub></strong> is the <strong>smallest natural number > a<sub>n-1</sub></strong> that has '''n''' divisors: [[oeis:A069654|OEIS: |
Or, could be the sequence where each term <strong>a<sub>n</sub></strong> is the <strong>smallest natural number > a<sub>n-1</sub></strong> that has '''n''' divisors: [[oeis:A069654|OEIS:A069654]]. |
||
Or, it could be something else entirely. |
Or, it could be something else entirely. |
||
| Line 398: | Line 398: | ||
} |
} |
||
my $limit = 15; |
|||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
my $m = 1; |
my $m = 1; |
||
put "\nFirst |
put "\nFirst $limit terms of OEIS:A069654"; |
||
put (1.. |
put (1..$limit).map: -> $n { my $ = $m = first { $n == .&div-count }, $m..Inf }; |
||
# Actually, since there is no verbiage in the task description about |
# Actually, since there is no verbiage in the task description about |
||
# choosing the _smallest_ integer for each term, this complies with |
# choosing the _smallest_ integer, for each term, this complies with |
||
# a strict interpretation of the requirements. |
# a strict interpretation of the requirements. |
||
| ⚫ | |||
my $antipp = (1..5000).race.classify: { .&div-count }; |
my $antipp = (1..5000).race.classify: { .&div-count }; |
||
| ⚫ | |||
put (1.. |
put (1..$limit).map: { $antipp{$_}.pick }; |
||
# Oooo! Here's a good one. Each term is the nth occurrence of an integer with |
# Oooo! Here's a good one. Each term is the nth occurrence of an integer with |
||
# n divisors. Limit to 10 terms as this gets pretty intensive pretty quickly. |
# n divisors. Limit to 10 terms as this gets pretty intensive pretty quickly. |
||
my @primes = grep { .is-prime }, 1..*; |
|||
@primes[$limit]; # prime the array. SCNR |
|||
put "\nNth occurrence of an integer with n divisors:"; |
put "\nNth occurrence of an integer with n divisors:"; |
||
put (1.. |
put (1..$limit).hyper(:2batch).map: -> $n { |
||
($n > 4 and $n.is-prime) ?? |
|||
exp($n - 1, @primes[$n - 1]) !! |
|||
do { |
|||
my $i = 0; |
|||
(1..*).first: { |
|||
$ |
next unless $n == .&div-count; |
||
next unless ++$i == $n; |
|||
$_ |
|||
} |
|||
} |
} |
||
};</lang> |
};</lang> |
||
{{out}} |
{{out}} |
||
<pre>First 15 terms of OEIS: |
<pre>First 15 terms of OEIS:A005179 |
||
1 2 4 6 16 12 64 24 36 48 1024 60 4096 192 144 |
1 2 4 6 16 12 64 24 36 48 1024 60 4096 192 144 |
||
First 15 terms of OEIS: |
First 15 terms of OEIS:A069654 |
||
1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624 |
1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624 |
||
Technically correct is the best kind of correct: |
Technically correct is the best kind of correct: |
||
1 |
1 1777 9 989 625 4527 64 1270 1444 4208 1024 1694 4096 3776 144 |
||
Nth occurrence of an integer with n divisors: |
Nth occurrence of an integer with n divisors: |
||
1 3 25 14 14641 44 24137569 70 1089 405</pre> |
1 3 25 14 14641 44 24137569 70 1089 405 819628286980801 160 22563490300366186081 2752 9801</pre> |
||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
Revision as of 17:55, 10 April 2019
The Anti-primes Plus sequence are the natural numbers in which each nth term has n divisors, including 1 and itself.
Task
Show the first 15 terms of this sequence.
C
<lang c>#include <stdio.h>
- define MAX 15
int count_divisors(int n) {
int i, count = 0;
for (i = 1; i * i <= n; ++i) {
if (!(n % i)) {
if (i == n / i)
count++;
else
count += 2;
}
}
return count;
}
int main() {
int i, next = 1;
printf("The first %d anti-primes plus are:\n", MAX);
for (i = 1; next <= MAX; ++i) {
if (next == count_divisors(i)) {
printf("%d ", i);
next++;
}
}
printf("\n");
return 0;
}</lang>
- Output:
The first 15 anti-primes plus are: 1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624
C++
<lang cpp>#include <iostream>
- define MAX 15
using namespace std;
int count_divisors(int n) {
int count = 0;
for (int i = 1; i * i <= n; ++i) {
if (!(n % i)) {
if (i == n / i)
count++;
else
count += 2;
}
}
return count;
}
int main() {
cout << "The first " << MAX << " anti-primes plus are:" << endl;
for (int i = 1, next = 1; next <= MAX; ++i) {
if (next == count_divisors(i)) {
cout << i << " ";
next++;
}
}
cout << endl;
return 0;
}</lang>
- Output:
The first 15 anti-primes plus are: 1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624
F#
This task uses Extensible Prime Generator (F#) <lang fsharp> // Find Antı-Primes plus. Nigel Galloway: April 9th., 2019 // Increasing the value 14 will increase the number of anti-primes plus found let fI=primes|>Seq.take 14|>Seq.map bigint|>List.ofSeq let N=Seq.reduce(*) fI let fG g=Seq.unfold(fun ((n,i,e) as z)->Some(z,(n+1,i+1,(e*g)))) (1,2,g) let fE n i=n|>Seq.collect(fun(n,e,g)->Seq.map(fun(a,c,b)->(a,c*e,g*b)) (i|>Seq.takeWhile(fun(g,_,_)->g<=n))|> Seq.takeWhile(fun(_,_,n)->n<N)) let fL=let mutable g=0 in (fun n->g<-g+1; n=g) let n=Seq.concat(Seq.scan(fun n g->fE n (fG g)) (seq[(2147483647,1,1I)]) fI)|>List.ofSeq|>List.groupBy(fun(_,n,_)->n)|>List.sortBy(fun(n,_)->n)|>List.takeWhile(fun(n,_)->fL n) for n,g in n do printfn "%d->%A" n (g|>List.map(fun(_,_,n)->n)|>List.min) </lang>
- Output:
1->1 2->2 3->4 4->6 5->16 6->12 7->64 8->24 9->36 10->48 11->1024 12->60 13->4096 14->192 15->144 16->120 17->65536 18->180 19->262144 20->240 21->576 22->3072 23->4194304 24->360 25->1296 26->12288 27->900 28->960 29->268435456 30->720 31->1073741824 32->840 33->9216 34->196608 35->5184 36->1260 37->68719476736 38->786432 39->36864 40->1680 41->1099511627776 42->2880 43->4398046511104 44->15360 45->3600 46->12582912 47->70368744177664 48->2520 49->46656 50->6480 51->589824 52->61440 53->4503599627370496 54->6300 55->82944 56->6720 57->2359296 58->805306368 Real: 00:00:01.079, CPU: 00:00:01.080, GC gen0: 47, gen1: 0
Go
<lang go>package main
import "fmt"
func countDivisors(n int) int {
count := 0
for i := 1; i*i <= n; i++ {
if n%i == 0 {
if i == n/i {
count++
} else {
count += 2
}
}
}
return count
}
func main() {
const max = 15
fmt.Println("The first", max, "anti-primes plus are:")
for i, next := 1, 1; next <= max; i++ {
if next == countDivisors(i) {
fmt.Printf("%d ", i)
next++
}
}
fmt.Println()
}</lang>
- Output:
The first 15 anti-primes plus are: 1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624
Java
<lang java>public class AntiPrimesPlus {
static int count_divisors(int n) {
int count = 0;
for (int i = 1; i * i <= n; ++i) {
if (n % i == 0) {
if (i == n / i)
count++;
else
count += 2;
}
}
return count;
}
public static void main(String[] args) {
final int max = 15;
System.out.printf("The first %d anti-primes plus are:\n", max);
for (int i = 1, next = 1; next <= max; ++i) {
if (next == count_divisors(i)) {
System.out.printf("%d ", i);
next++;
}
}
System.out.println();
}
}</lang>
- Output:
The first 15 anti-primes plus are: 1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624
Kotlin
<lang scala>// Version 1.3.21
const val MAX = 15
fun countDivisors(n: Int): Int {
var count = 0
var i = 1
while (i * i <= n) {
if (n % i == 0) {
count += if (i == n / i) 1 else 2
}
i++
}
return count
}
fun main() {
println("The first $MAX anti-primes plus are:")
var i = 1
var next = 1
while (next <= MAX) {
if (next == countDivisors(i)) {
print("$i ")
next++
}
i++
}
println()
}</lang>
- Output:
The first 15 anti-primes plus are: 1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624
Pascal
Think of OEIS: A069654.
Counting divisors by prime factorisation.
If divCnt= Count of divisors is prime then the only candidate ist n = prime^(divCnt-1).
There will be more rules. If divCnt is odd then the divisors of divCnt are a^(even_factor*i)*..*k^(even_factor*j).
I think of next = 33 aka 11*3 with the solution 1031^2 * 2^10=1,088,472,064 with a big distance to next= 32 => 1073741830.
<lang pascal>program AntiPrimesPlus;
{$IFDEF FPC}
{$MODE Delphi}
{$ELSE}
{$APPTYPE CONSOLE} // delphi
{$ENDIF} const
MAX =32;
function getDividersCnt(n:NativeUint):NativeUint; // getDividersCnt by dividing n into its prime factors // aka n = 2250 = 2^1*3^2*5^3 has (1+1)*(2+1)*(3+1)= 24 dividers var
divi,quot,deltaRes : NativeUint;
begin
result := 1;
//divi := 2; //separat without division while Not(Odd(n)) do Begin n := n SHR 1; inc(result); end;
//from now on only odd numbers
divi := 3;
while (sqr(divi)<=n) do
Begin
deltaRes := 0;
repeat
quot := n div divi;
if n <> quot*divi then
BREAK;
n := quot;
inc(deltaRes,result);
until n < divi;
inc(result,deltaRes);
inc(divi,2);
end;
//if last factor of n is prime
IF n <> 1 then
result := result*2;
end;
var
i,next,DivCnt: NativeUint;
begin
writeln('The first ',MAX,' anti-primes plus are:');
i := 1;
next := 1;
repeat
DivCnt := getDividersCnt(i);
IF DivCnt= next then
Begin
write(i,' ');
inc(next);
//if next is prime then only prime( => mostly 2 )^(next-1) is solution
IF (next > 4) AND (getDividersCnt(next) = 2) then
Begin
i := 1;
For DivCnt := 2 to Next do
inc(i,i);// 2^(next-1)
dec(i);// i is incremented afterwards
end;
end;
inc(i);
until Next > MAX;
writeln;
end.</lang>
- Output:
The first 32 anti-primes plus are: 1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624 4632 65536 65572 262144 262192 263169 269312 4194304 4194306 4477456 4493312 4498641 4498752 268435456 268437200 1073741824 1073741830 real 0m0.419s
Perl
<lang perl>use strict; use warnings; use ntheory 'divisors';
print "First 15 terms of OEIS: A005179\n"; for my $n (1..15) {
my $l = 0;
while (++$l) {
print "$l " and last if $n == divisors($l);
}
}
print "\n\nFirst 15 terms of OEIS: A69654\n"; my $m = 0; for my $n (1..15) {
my $l = $m;
while (++$l) {
print("$l "), $m = $l, last if $n == divisors($l);
}
}</lang>
- Output:
First 15 terms of OEIS: A005179 1 2 4 6 16 12 64 24 36 48 1024 60 4096 192 144 First 15 terms of OEIS: A069654 1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624
Perl 6
This task could be interpreted in a few ways.
Could be the sequence of the smallest natural numbers such that each an has n divisors: OEIS:A005179.
Or, could be the sequence where each term an is the smallest natural number > an-1 that has n divisors: OEIS:A069654.
Or, it could be something else entirely.
Whichever, here are a few possibilities.
<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 = 15;
put "First $limit terms of OEIS:A005179"; put (1..$limit).map: -> $n { first { $n == .&div-count }, 1..Inf };
my $m = 1; put "\nFirst $limit terms of OEIS:A069654"; put (1..$limit).map: -> $n { my $ = $m = first { $n == .&div-count }, $m..Inf };
- Actually, since there is no verbiage in the task description about
- choosing the _smallest_ integer, for each term, this complies with
- a strict interpretation of the requirements.
my $antipp = (1..5000).race.classify: { .&div-count }; put "\nTechnically correct is the best kind of correct:"; put (1..$limit).map: { $antipp{$_}.pick };
- Oooo! Here's a good one. Each term is the nth occurrence of an integer with
- n divisors. Limit to 10 terms as this gets pretty intensive pretty quickly.
my @primes = grep { .is-prime }, 1..*; @primes[$limit]; # prime the array. SCNR
put "\nNth occurrence of an integer with n divisors:"; put (1..$limit).hyper(:2batch).map: -> $n {
($n > 4 and $n.is-prime) ??
exp($n - 1, @primes[$n - 1]) !!
do {
my $i = 0;
(1..*).first: {
next unless $n == .&div-count;
next unless ++$i == $n;
$_
}
}
};</lang>
- Output:
First 15 terms of OEIS:A005179 1 2 4 6 16 12 64 24 36 48 1024 60 4096 192 144 First 15 terms of OEIS:A069654 1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624 Technically correct is the best kind of correct: 1 1777 9 989 625 4527 64 1270 1444 4208 1024 1694 4096 3776 144 Nth occurrence of an integer with n divisors: 1 3 25 14 14641 44 24137569 70 1089 405 819628286980801 160 22563490300366186081 2752 9801
REXX
Programming note: this Rosetta Code task (for 15 sequence numbers) doesn't require any optimization, but the code was optimized for listing higher numbers.
The method used is to find the number of proper divisors (up to the integer square root of X), and add one.
Optimization was included when examining even or odd index numbers (determine how much to increment the do loop). <lang rexx>/*REXX program finds and displays N numbers of the "anti─primes plus" sequence. */ parse arg N . /*obtain optional argument from the CL.*/ if N== | N=="," then N= 15 /*Not specified? Then use the default.*/ idx= 1 /*the maximum number of divisors so far*/ say '──index── ──anti─prime plus──' /*display a title for the numbers shown*/
- = 0 /*the count of anti─primes found " " */
do i=1 until #==N /*step through possible numbers by twos*/
d= #divs(i); if d\==idx then iterate /*get # divisors; Is too small? Skip.*/
#= # + 1; idx= idx + 1 /*found an anti─prime #; set new minD.*/
say center(#, 8) right(i, 15) /*display the index and the anti─prime.*/
end /*i*/
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/
- 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:
──index── ──anti─prime plus── 1 1 2 2 3 4 4 6 5 16 6 18 7 64 8 66 9 100 10 112 11 1024 12 1035 13 4096 14 4288 15 4624
Ring
<lang ring>
- Project : ANti-primes
see "working..." + nl see "wait for done..." + nl + nl see "the first 15 Anti-primes Plus are:" + nl + nl num = 1 n = 0 result = list(15) while num < 16
n = n + 1
div = factors(n)
if div = num
result[num] = n
num = num + 1
ok
end see "[" for n = 1 to len(result)
if n < len(result)
see string(result[n]) + ","
else
see string(result[n]) + "]" + nl + nl
ok
next see "done..." + nl
func factors(an)
ansum = 2
if an < 2
return(1)
ok
for nr = 2 to an/2
if an%nr = 0
ansum = ansum+1
ok
next
return ansum
</lang>
- Output:
working... wait for done... the first 15 Anti-primes Plus are: [1,2,4,6,16,18,64,66,100,112,1024,1035,4096,4288,4624] done...
Sidef
a(n) is the smallest number with exactly n divisors (A005179). <lang ruby>func n_divisors(n) {
1..Inf -> first_by { .sigma0 == n }
}
say 15.of { n_divisors(_+1) }</lang>
- Output:
[1, 2, 4, 6, 16, 12, 64, 24, 36, 48, 1024, 60, 4096, 192, 144]
a(n) is the smallest number > a(n-1) with exactly n divisors (A069654).
<lang ruby>func n_divisors(n, from=1) {
from..Inf -> first_by { .sigma0 == n }
}
with (1) { |from|
say 15.of { from = n_divisors(_+1, from) }
}</lang>
- Output:
[1, 2, 4, 6, 16, 18, 64, 66, 100, 112, 1024, 1035, 4096, 4288, 4624]
zkl
<lang zkl>fcn countDivisors(n)
{ [1..(n).toFloat().sqrt()] .reduce('wrap(s,i){ s + (if(0==n%i) 1 + (i!=n/i)) },0) }</lang>
<lang zkl>n:=15; println("The first %d anti-primes plus are:".fmt(n)); (1).walker(*).tweak(
fcn(n,rn){ if(rn.value==countDivisors(n)){ rn.inc(); n } else Void.Skip }.fp1(Ref(1)))
.walk(n).concat(" ").println();</lang>
- Output:
The first 15 anti-primes plus are: 1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624