Give the smallest number that has N divisors

Question

Your function takes a natural number and returns the smallest natural number that has exactly that amount of divisors, including itself.

Examples:

f(1) =  1 [1]
f(2) =  2 [1, 2]
f(3) =  4 [1, 2, 4]
f(4) =  6 [1, 2, 3, 6]
f(5) = 16 [1, 2, 4, 8, 16]
f(6) = 12 [1, 2, 3, 4, 6, 12]
 ...

The function doesn't have to return the list of divisors, they are only here for the examples.

Answer 1

APL, 25 24 23 characters

f←{({+/⍵=⍵∧⍳⍵}¨⍳2*⍵)⍳⍵}

Defines a function f which can then be used to calculate the numbers:

> f 13
4096

> f 14
192

The solution utilizes the fact that LCM(n,x)==n iff x divides n. Thus, the block {+/⍵=⍵∧⍳⍵} simply calculates the number of divisors. This function is applied to all numbers from 1 to 2^d ¨⍳2*⍵. The resulting list is then searched for d itself (⍳⍵) which is the desired function f(d).

Answer 2

GolfScript, 29 28 characters

{.{\.,{)1$\%},,-=}+2@?,?}:f;

Edit: A single char can be saved if we restrict the search to <2^n, thanks to Peter Taylor for this idea.

Previous Version:

{.{\)..,{)1$\%},,-@=!}+do}:f;

An attempt in GolfScript, run online.

Examples:

13 f p  # => 4096
14 f p  # => 192
15 f p  # => 144

The code contains essentially three blocks which are explained in detail in the following lines.

# Calculate numbers of divisors
#         .,{)1$\%},,-    
# Input stack: n
# After application: D(n)

.,          # push array [0 .. n-1] to stack
{           # filter array by function
  )         #   take array element and increase by one
  1$\%      #   test division of n ($1) by this value
},          # -> List of numbers x where n is NOT divisible by x+1
,           # count these numbers. Stack now is n xd(n)
-           # subtracting from n yields the result



# Test if number of divisors D(n) is equal to d
#         {\D=}+   , for D see above
# Input stack: n d
# After application: D(n)==d

{
  \         # swap stack -> d n
  D         # calculate D(n) -> d D(n)
  =         # compare
}+          # consumes d from stack and prepends it to code block         



# Search for the first number which D(n) is equal to d
#         .T2@?,?    , for T see above
# Input stack: d
# After application: f(d)

.           # duplicate -> d d
T           # push code block (!) for T(n,d) -> d T(n,d)
2@?         # swap and calculate 2^d -> T(n,d) 2^d
,           # make array -> T(n,d) [0 .. 2^d-1]
?           # search first element in array where T(n,d) is true -> f(d)

Answer 3

Mathematica 38 36

(For[i=1,DivisorSum[++i,1&]!=#,];i)&

Usage:

(For[i=1,DivisorSum[++i,1&]!=#,];i)&@200

Result:

498960

Edit

Some explanation:

DivisorSum[n,form] represents the sum of form[i] for all i that divide n.

As form[i] I am using the function 1 &, that returns always 1, so effectively computing the sum of the divisors in a terse way.

Answer 4

Python: 66

f=lambda n,k=1:n==sum(k%i<1for i in range(1,k+1))and k or f(n,k+1)

The above will raise a RuntimeError: maximum recursion depth exceeded with small inputs in CPython, and even setting the limit to a huge number it will probably give some problems. On python implementations that optimize tail recursion it should work fine.

A more verbose version, which shouldn't have such limitations, is the following 79 bytes solution:

def f(n,k=1):
    while 1:
        if sum(k%i<1for i in range(1,k+1))==n:return k
        k+=1

Answer 5

Python: 64

Revising Bakuriu's solution and incorporating grc's suggestion as well as the trick from plannapus's R solution, we get:

f=lambda n,k=1:n-sum(k%i<1for i in range(1,k+1))and f(n,k+1)or k

Answer 6

Haskell 54

Quick and dirty (so readable and non-tricky) solution:

f k=head[x|x<-[k..],length[y|y<-[1..x],mod x y==0]==k]

Answer 7

J, 33 chars

Fairly quick, goes through all smaller numbers and computes number of divisors based on factorization.

   f=.>:@]^:([~:[:*/[:>:_&q:@])^:_&1

   f 19
262144

Answer 8

K, 42

Inefficient recursive solution that blows up the stack quite easily

{{$[x=+/a=_a:y%!1+y;y;.z.s[x;1+y]]}[x;0]} 

.

k){{$[x=+/a=_a:y%!1+y;y;.z.s[x;1+y]]}[x;0]}14
192
k){{$[x=+/a=_a:y%!1+y;y;.z.s[x;1+y]]}[x;0]}13
'stack

Answer 9

APL 33

F n            
i←0              
l:i←i+1          
→(n≠+/0=(⍳i)|i)/l
i 

Example:

F 6
12           

Answer 10

APL (25)

{⍵{⍺=+/0=⍵|⍨⍳⍵:⍵⋄⍺∇⍵+1}1}

Answer 11

R - 47 characters

f=function(N){n=1;while(N-sum(!n%%1:n))n=n+1;n}

!n%%1:n gives a vector of booleans: TRUE when an integer from 1 to n is a divisor of n and FALSE if not. sum(!n%%1:n) coerces booleans to 0 if FALSE and 1 if TRUE and sums them, so that N-sum(...) is 0 when number of divisors is N. 0 is then interpreted as FALSE by while which then stops.

Usage:

f(6)
[1] 12
f(13)
[1] 4096

Answer 12

Haskell: 49 characters

It could be seen as an improvement of the earlier Haskell solution, but it was conceived in its own right (warning: it's very slow):

f n=until(\i->n==sum[1|j<-[1..i],rem i j<1])(+1)1

It's quite an interesting function, for example note that f(p) = 2^(p-1), where p is a prime number.

Answer 13

Javascript 70

function f(N){for(j=i=m=1;m-N||j-i;j>i?i+=m=j=1:m+=!(i%++j));return i}

Really there are only 46 meaningful characters:

for(j=i=m=1;m-N||j-i;j>i?i+=m=j=1:m+=!(i%++j))

I probably should learn a language with shorter syntax :)

Answer 14

C: 66 64 characters

An almost short solution:

i;f(n){while(n-g(++i));return i;}g(j){return j?!(i%j)+g(j-1):0;}

And my previous solution that doesn't recurse:

i;j;k;f(n){while(k-n&&++i)for(k=0,j=1;j<=i;k+=!(i%j++));return i;}

Much shorter solutions must exist.

Answer 15

Haskell (120C), a very efficient method

1<>p=[]
x<>p|mod x p>0=x<>(p+1)|1<2=(div x p<>p)++[p]
f k=product[p^(c-1)|(p,c)<-zip[r|r<-[2..k],2>length(r<>2)](k<>2)]

Test code:

main=do putStrLn$show$ f (100000::Integer)

This method is very fast. The idea is first to find the prime factors of k=p1*p2*...*pm, where p1 <= p2 <= ... <= pm. Then the answer is n = 2^(pm-1) * 3^(p(m-1)-1) * 5^(p(m-2)-1) ....

For example, factorizing k=18, we get 18 = 2 * 3 * 3. The first 3 primes is 2, 3, 5. So the answer n = 2^(3-1) * 3^(3-1) * 5^(2-1) = 4 * 9 * 5 = 180

You can test it under ghci:

*Main> f 18
180
*Main> f 10000000
1740652905587144828469399739530000
*Main> f 1000000000
1302303070391975081724526582139502123033432810000
*Main> f 100000000000
25958180173643524088357042948368704203923121762667635047013610000
*Main> f 10000000000000
6558313786906640112489895663139340360110815128467528032775795115280724604138270000
*Main> f 1000000000000000
7348810968806203597063900192838925279090695601493714327649576583670128003853133061160889908724790000
*Main> f 100000000000000000
71188706857499485011467278407770542735616855123676504522039680180114830719677927305683781590828722891087523475746870000
*Main> f 10000000000000000000
2798178979166951451842528148175504903754628434958803670791683781551387366333345375422961774196997331643554372758635346791935929536819490000
*Main> f 10000000000000000000000
6628041919424064609742258499702994184911680129293140595567200404379028498804621325505764043845346230598649786731543414049417584746693323667614171464476224652223383190000

Answer 16

Brachylog, 2 bytes

fl

Try it online!

Takes input through its output variable and outputs through its input variable.

f     The list of factors of
      the input variable
 l    has length equal to
      the output variable.

This exact same predicate, taking input through its input variable and outputting through its output variable, solves this challenge instead.

Answer 17

Mathematica 38 36

(For[k=1,DivisorSigma[0, k]!= #,k++]; k)&

Usage

   (For[k = 1, DivisorSigma[0, k] != #, k++]; k) &[7]

(* 64 *)

---

First entry (before the code-golf tag was added to the question.)

A straightforward problem, given that Divisors[n] returns the divisors of n (including n) and Length[Divisors[n]] returns the number of such divisors.**

smallestNumber[nDivisors_] :=
   Module[{k = 1},
   While[Length[Divisors[k]] != nDivisors, k++];k]

Examples

Table[{i, nDivisors[i]}, {i, 1, 20}] // Grid

Answer 18

C, 69 chars

Not the shortest, but the first C answer:

f(n,s){return--s?f(n,s)+!(n%s):1;}
x;
g(d){return++x,f(x,x)-d&&g(d),x;}

f(n,s) counts divisors of n in the range 1..s. So f(n,n) counts divisors of n.
g(d) loops (by recursion) until f(x,x)==d, then returns x.

Answer 19

Jelly, 6 bytes (non-competing)

2*RÆdi

Try it online! or verify all test cases.

How it works

2*RÆdi  Main link. Argument: n (integer)

2*      Compute 2**n.
  R     Range; yield [1, ..., 2**n]. Note that 2**(n-1) has n divisors, so this
        range contains the number we are searching for.
   Æd   Divisor count; compute the number of divisors of each integer in the range.
     i  Index; return the first (1-based) index of n.

Answer 20

C++, 87 characters

int a(int d){int k=0,r,i;for(;r!=d;k++)for(i=2,r=1;i<=k;i++)if(!(k%i))r++;return k-1;}

Answer 21

Python2, 95 characters, Non-recursive

A bit more verbose than the other python solutions but it's non-recursive so it doesn't hit cpython's recursion limit:

from itertools import*
f=lambda n:next(i for i in count()if sum(1>i%(j+1)for j in range(i))==n)

Answer 22

Perl 6, 39 chars

{my \a=$=0;a++while $_-[+] a X%%1..a;a}

Example usage:

say (0..10).map: {my \a=$=0;a++while $_-[+] a X%%1..a;a}

(0 1 2 4 6 16 12 64 24 36 48)