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

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 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

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 6

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 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

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 9

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 10

Rust, 55 bytes

|n|(1..).find(|x|(1..*x).filter(|d|x%d<1).count()==n-1)

Try it online!

|n|                 //Number of divisors
  (1..)             //Infinite range starting at 1
    .find(|x|       //Find an x such that
      (1..*x)       //Possible divisors
        .filter(|d| //Keep the ones that
          x%d<1     //x is divisible by
        )
        .count()    //Count how many divisors there are (not including x)
         == n-1)     //Make sure there are n-1 of them

Answer 11

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 12

APL 33

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

Example:

F 6
12           

Answer 13

APL (25)

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

Answer 14

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 15

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 16

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 17

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 18

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 19

Husk, 6 bytes

€moLḊN

Try it online!

1 byte shorter than the previous Husk answer...

€           # index of first occurrence of input among
 m   N      # map over all natural numbers
  oLḊ       # length of list of divisors

Answer 20

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 21

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)

Answer 22

Japt, 8 bytes

@¶Xâ l}a

Try it

Answer 23

Raku, 28 bytes

{(1…(*X%%^*+1).sum==$_)-1}

Try it online!

Answer 24

Setanta, 79 bytes

gniomh(n){k:=1nuair-a 1{a:=k le i idir(1,k+1)ma k%i a-=1ma a==n toradh k k+=1}}

Try it here!

Answer 25

Husk, ^{9 8} 7 bytes

ḟȯ=⁰LḊN

Try it online!

-1 byte from Zgarb.

-1 byte from Jo King. (Simplifying range)

Explanation

▼fȯ=¹LḊḣΠ
       ḣΠ range from 1..factorial(n)
 f        filter values using the following predicate:
     LḊ   length of list of divisors
   =¹     = n.
▼         take the minimum value.

Answer 26

Jelly, 6 bytes

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 27

05AB1E, 7 bytes

-1 byte thanks to @ovs.

∞.ΔÑgQ

Try it online!

∞.ΔÑgQ  # full program
 .Δ     # find first...
∞       # natural number...
     Q  # which has...
        # implicit input...
   Ñg   # divisors
        # implicit output

Answer 28

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 29

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 30

Scala, 66 bytes

def f(n:Int,x:Int=1):Int=if(1.to(x).count(x%_<1)!=n)f(n,x+1)else x

Try it in Scastie