Sequence: smallest number greater than previous term with exactly n divisors: Difference between revisions
(→{{header|REXX}}: added the REXX computer programming language for this task.) |
|||
Line 327: | Line 327: | ||
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</pre> |
||
=={{header|REXX}}== |
|||
<lang rexx>/*REXX program finds and displays N number of anti─primes or highly─composite numbers.*/ |
|||
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> |
|||
{{out|output|text= when using the default input:}} |
|||
<pre> |
|||
──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 |
|||
</pre> |
|||
=={{header|Ring}}== |
=={{header|Ring}}== |
Revision as of 20:38, 9 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
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) } }
}
put 'First 15 terms of OEIS: A005179'; put (1..15).map: -> $n { first { $n == .&div-count }, 1..Inf };
my $m = 1; put "\nFirst 15 terms of OEIS: A069654"; put (1..15).map: -> $n { my $r = $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.
put "\nTechnically correct is the best kind of correct:"; my $antipp = (1..5000).race.classify: { .&div-count }; put (1..15).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 get pretty intensive pretty quickly.
put "\nNth occurrence of an integer with n divisors:"; put (1..10).hyper(:1batch).map: -> $n {
my $i = 0; my $iterator = $n %% 2 ?? (1..*) !! (1..*).map: *²; $iterator.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 2137 49 989 2401 2908 729 783 3025 4375 1024 3596 4096 2368 2500 Nth occurrence of an integer with n divisors: 1 3 25 14 14641 44 24137569 70 1089 405
REXX
<lang rexx>/*REXX program finds and displays N number of anti─primes or highly─composite numbers.*/ 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