Sequence: smallest number with exactly n divisors: Difference between revisions
Line 388: | Line 388: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Using the formulae from the OEIS:A005179 link above.<br> |
|||
Uses primes[] and add_block() from [[Extensible_prime_generator#Phix|Extensible_prime_generator]] |
Uses primes[] and add_block() from [[Extensible_prime_generator#Phix|Extensible_prime_generator]], |
||
product() has recently been added as a new builtin, if you need it see [[Deconvolution/2D%2B#Phix]]. |
product() has recently been added as a new builtin, if you need it see [[Deconvolution/2D%2B#Phix]]. |
||
<lang Phix>constant limit = iff(machine_bits()=32?58:66) |
<lang Phix>constant limit = iff(machine_bits()=32?58:66) |
Revision as of 07:25, 8 June 2019
Calculate the sequence where each term an is the smallest natural number that has exactly n divisors.
- Task
Show here, on this page, at least the first 15 terms of the sequence.
- See also
- Related tasks
ALGOL 68
<lang algol68>BEGIN
PROC count divisors = ( INT n )INT: BEGIN INT count := 0; FOR i WHILE i*i <= n DO IF n MOD i = 0 THEN count +:= IF i = n OVER i THEN 1 ELSE 2 FI FI OD; count END # count divisors # ; INT max = 15; [ max ]INT seq;FOR i TO max DO seq[ i ] := 0 OD; INT found := 0; FOR i WHILE found < max DO IF INT divisors = count divisors( i ); divisors <= max THEN # have an i with an appropriate number of divisors # IF seq[ divisors ] = 0 THEN # this is the first i with that many divisors # seq[ divisors ] := i; found +:= 1 FI FI OD; print( ( "The first ", whole( max, 0 ), " terms of the sequence are:", newline ) ); FOR i TO max DO print( ( whole( seq( i ), 0 ), " " ) ) OD; print( ( newline ) )
END</lang>
- Output:
The first 15 terms of the sequence are: 1 2 4 6 16 12 64 24 36 48 1024 60 4096 192 144
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, k, n, seq[MAX]; for (i = 0; i < MAX; ++i) seq[i] = 0; printf("The first %d terms of the sequence are:\n", MAX); for (i = 1, n = 0; n < MAX; ++i) { k = count_divisors(i); if (k <= MAX && seq[k - 1] == 0) { seq[k - 1] = i; ++n; } } for (i = 0; i < MAX; ++i) printf("%d ", seq[i]); printf("\n"); return 0;
}</lang>
- Output:
The first 15 terms of the sequence are: 1 2 4 6 16 12 64 24 36 48 1024 60 4096 192 144
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() {
int i, k, n, seq[MAX]; for (i = 0; i < MAX; ++i) seq[i] = 0; cout << "The first " << MAX << " terms of the sequence are:" << endl; for (i = 1, n = 0; n < MAX; ++i) { k = count_divisors(i); if (k <= MAX && seq[k - 1] == 0) { seq[k - 1] = i; ++n; } } for (i = 0; i < MAX; ++i) cout << seq[i] << " "; cout << endl; return 0;
}</lang>
- Output:
The first 15 terms of the sequence are: 1 2 4 6 16 12 64 24 36 48 1024 60 0 192 144
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
Factor
<lang factor>USING: fry kernel lists lists.lazy math math.primes.factors prettyprint sequences ;
- A005179 ( -- list )
1 lfrom [ 1 swap '[ dup divisors length _ = ] [ 1 + ] until ] lmap-lazy ;
15 A005179 ltake list>array .</lang>
- Output:
{ 1 2 4 6 16 12 64 24 36 48 1024 60 4096 192 144 }
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 seq := make([]int, max) fmt.Println("The first", max, "terms of the sequence are:") for i, n := 1, 0; n < max; i++ { if k := countDivisors(i); k <= max && seq[k-1] == 0 { seq[k-1] = i n++ } } fmt.Println(seq)
}</lang>
- Output:
The first 15 terms of the sequence are: [1 2 4 6 16 12 64 24 36 48 1024 60 4096 192 144]
Java
<lang java>import java.util.Arrays;
public class OEIS_A005179 {
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; int[] seq = new int[max]; System.out.printf("The first %d terms of the sequence are:\n", max); for (int i = 1, n = 0; n < max; ++i) { int k = count_divisors(i); if (k <= max && seq[k - 1] == 0) { seq[k- 1] = i; n++; } } System.out.println(Arrays.toString(seq)); }
}</lang>
- Output:
The first 15 terms of the sequence are: [1, 2, 4, 6, 16, 12, 64, 24, 36, 48, 1024, 60, 4096, 192, 144]
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() {
var seq = IntArray(MAX) println("The first $MAX terms of the sequence are:") var i = 1 var n = 0 while (n < MAX) { var k = countDivisors(i) if (k <= MAX && seq[k - 1] == 0) { seq[k - 1] = i n++ } i++ } println(seq.asList())
}</lang>
- Output:
The first 15 terms of the sequence are: [1, 2, 4, 6, 16, 12, 64, 24, 36, 48, 1024, 60, 4096, 192, 144]
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); }
}</lang>
- Output:
First 15 terms of OEIS: A005179 1 2 4 6 16 12 64 24 36 48 1024 60 4096 192 144
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 = 15;
put "First $limit terms of OEIS:A005179"; put (1..$limit).map: -> $n { first { $n == .&div-count }, 1..Inf };
</lang>
- Output:
First 15 terms of OEIS:A005179 1 2 4 6 16 12 64 24 36 48 1024 60 4096 192 144
Phix
Using the formulae from the OEIS:A005179 link above.
Uses primes[] and add_block() from Extensible_prime_generator,
product() has recently been added as a new builtin, if you need it see Deconvolution/2D+#Phix.
<lang Phix>constant limit = iff(machine_bits()=32?58:66)
sequence found = repeat(0,limit)
integer n = 1
atom ri
for i=1 to limit do
sequence f = factors(i,1) integer lf = length(f) if lf<=2 then ri = power(2,i-1) -- prime (or 1) elsif lf=3 then ri = power(6,f[2]-1) -- p^2 (eg f={1,5,25}) elsif f[2]>2 -- (see note) and f[$] = power(f[2],lf-1) then while length(primes)<lf-1 do add_block() end while ri = power(product(primes[1..lf-1]),f[2]-1) -- p^k (eg f={1,3,9,27}) elsif length(f)=4 then ri = power(2,f[3]-1)*power(3,f[2]-1) -- p*q (eg f={1,2,3,6}) else while found[i]=0 do integer k = length(factors(n,1)) -- do the rest manually if k<=limit and found[k]=0 then found[k] = n end if n += 1 end while ri = found[i] end if printf(1,"%d->%d\n",{i,ri})
end for</lang> note: the f[2]>2 test should really be something more like >log(primes[lf-1])/log(2), apparently, but everything seems ok within the IEE754 53/64 bit limits this imposes. afaict, it takes longer to print the answers that it did to calculate them, tee hee!
- Output:
64-bit (as shown) manages 8 more answers than 32-bit, which as per limit halts on 58.
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 59->288230376151711744 60->5040 61->1152921504606846976 62->3221225472 63->14400 64->7560 65->331776 66->46080
REXX
<lang rexx>/*REXX program finds and displays the smallest 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.*/ say '──divisors── ──smallest number with N divisors──' /*display title for the numbers.*/ @.= /*the @ array is used for memoization*/
do i=1 for N /*step through a number of divisors. */ do j=1+(i\==1) by 1+(i\==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.*/ say center(i, 12) right(j, 19) /*display the #divs and the smallest #.*/ @.j=. /*mark as having found #divs for this J*/ leave /*found a number, so now get the next I*/ end /*j*/ 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:
──divisors── ──smallest number with N divisors── 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
Sidef
<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]
zkl
<lang zkl>fcn countDivisors(n)
{ [1.. n.toFloat().sqrt()].reduce('wrap(s,i){ s + (if(0==n%i) 1 + (i!=n/i)) },0) }
A005179w:=(1).walker(*).tweak(fcn(n){
var N=0,cache=Dictionary(); if(cache.find(n)) return(cache.pop(n)); // prune while(1){ if(n == (d:=countDivisors(N+=1))) return(N); if(n<d and not cache.find(d)) cache[d]=N; }
});</lang> <lang zkl>N:=15; println("First %d terms of OEIS:A005179".fmt(N)); A005179w.walk(N).concat(" ").println();</lang>
- Output:
First 15 terms of OEIS:A005179 1 2 4 6 16 12 64 24 36 48 1024 60 4096 192 144