# Give the smallest number that has N divisors

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

• Is this code-golf or code-challenge? – marinus Apr 3 '13 at 12:49
• Oops, forgot about that tag, code-golf! – SteeveDroz Apr 3 '13 at 13:06
• A005179 – Peter Taylor Apr 3 '13 at 15:28

### APL, 2524 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).

• Congrats! 23 characters... wow! – SteeveDroz Apr 8 '13 at 7:54
• 19: {⍵⍳⍨(+/⊢=⊢∧⍳)¨⍳2*⍵} – Adám Jun 28 '16 at 19:40
• I don't think you need to define f. – Zacharý Jul 9 '17 at 14:50

### 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)  • Seems to go into an infinite loop for input 1. – Peter Taylor Apr 3 '13 at 16:05 • My best solution so far borrows quite heavily from yours, to the extent that I think it deserves to be a comment rather than a separate answer. – Peter Taylor Apr 3 '13 at 16:31 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  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  • I'm hitting the recursion limit on 11, 13, 17, 19, and others. – Steven Rumbalski Apr 3 '13 at 17:31 • @StevenRumbalski Nobody mentioned that the program should work with arbitrary integers. Unfortunately the numbers grow up pretty fast even with small inputs. – Bakuriu Apr 3 '13 at 19:00 • You can save some chars by using replacing if else with and or and ==1 with <1: f=lambda n,k=1:n==sum(k%i<1for i in range(1,k+1))and k or f(n,k+1) – grc Apr 4 '13 at 1:18 • Because I find 66 a little too evil, you can save 2 characters if you use sum(k%-~i<1for i in range(k)) – Volatility Apr 25 '13 at 21:51 • f=lambda n,k=1:n==sum(k%-~i<1for i in range(k))or-~f(n,k+1) saves 7 bytes. – Dennis Oct 15 '16 at 5:32 ## 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. • There was no code-golf tag so I gave a long answer! oops – DavidC Apr 3 '13 at 13:23 • @DavidCarraher I just guessed :) – Dr. belisarius Apr 3 '13 at 13:28 • I thought I knew what DivisorSum returns (the sum of the divisors) but I don't see how that is instrumental for answering the question posed. Would you explain how it works. BTW, I think you should include timing data for n=200; the function is remarkably fast, given all the numbers it had to check. – DavidC Apr 3 '13 at 13:31 • @DavidCarraher See edit. Re: timings - My machine is way toooo slow :( – Dr. belisarius Apr 3 '13 at 13:35 • Does Mathematica not have enough built-ins for the more sophisticated approach around factoring to be shorter? If that's the case, I'm disappointed. – Peter Taylor Apr 3 '13 at 16:41 ## 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)  12 f(13)  4096  • ...7 years later, this question resurfaced in the 'Top Questions' page, so I gave it a shot, only to find that there was already this rather-similar R answer (from 7 years ago). Anyway, save 10 bytes by using scan() for input and T as a pre-defined variable: n=scan();while(n-sum(!T%%1:T))T=T+1;T (37 bytes). – Dominic van Essen Sep 9 '20 at 10:40 • by the way, R is the language of the month for September 2020 on CGCC, in case you feel like doing a spot of golfing again... – Dominic van Essen Sep 9 '20 at 10:44 • @DominicvanEssen The question explicitely asks for a function though! Thanks nonetheless! I am afraid I don't have much time for golfing those days unfortunately but I might give it a try this weekend, thanks for the heads up! – plannapus Sep 10 '20 at 5:54 ## J, 33 chars Fairly quick, goes through all smaller numbers and computes number of divisors based on factorization.  f=.>:@]^:([~:[:*/[:>:_&q:@])^:_&1 f 19 262144  ## 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]  • The edit did not make the answer any shorter, but it is maybe more haskell-like. Also I have always included the trailing newline to my code length, is this wrong? – shiona Apr 5 '13 at 17:04 • I thought you've miscounted; the main purpose for the edit was to update the count. The change in code itself was minor. I think the other entries here don't count the trailing newline either, like e.g. the entry for J (33 chars). – Will Ness Apr 13 '13 at 19:52 # 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  • That's a poor golf score, but +1 for the path you've taken! – SteeveDroz Apr 17 '13 at 6:05 • For 8=2*2*2 this algorithm give number 2*3*5=30. But best solution is 2^3*3=24 (for 8=2*4) – AMK Apr 17 '13 at 15:59 • The solution is incorrect if the specified number of divisors contain a high power of small prime. So most likely listed solutions for powers of 10 are wrong. – AMK Apr 17 '13 at 16:09 • @AMK Yes, you're right. Thanks for pointing that out. – Ray Apr 17 '13 at 16:27 ## 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


## APL 33

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


Example:

F 6
12


## APL (25)

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

• Cheater! echo -n '{⍵{⍺=+/0=⍵|⍨⍳⍵:⍵⋄⍺∇⍵+1}1}' | wc -c gives me 47! But really, could you please give me a link to some easy tutorial for APL? I tried to google it and have read a few articles, but still in the end I always want to ask "Why are they doing this :( ?". I have never worked with any non-ASCII syntax language and want to find out if it has any real advantage. – XzKto Apr 4 '13 at 12:55
• This is for Dyalog APL, which is what I use, you can download the Windows version for free at the same site. dyalog.com/MasteringDyalogAPL/MasteringDyalogAPL.pdf – marinus Apr 5 '13 at 11:19
• Wow, looks like I can really understand this one. Thank you for the link! The only downside is that they have some very strange licensing policy but maybe I just need to improve my english ) – XzKto Apr 5 '13 at 12:21

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

• N=>eval("for(j=i=m=1;m-N||j-i;j>i?i+=m=j=1:m+=!(i%++j));i") – TuxCrafting Oct 15 '16 at 10:06

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

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.

• The efficient, as opposed to short, way to calculate it would be to factor n into primes (with repetition), sort descending, decrement each one, zip with an infinite sequence of primes, and then fold the product of p^(factor-1) – Peter Taylor Apr 3 '13 at 18:46
• @PeterTaylor Not necessary. For n=16=2*2*2*2 solution is 2^3*3^1*5^1=120, not 2^1*3^1*5^1*7^1=210. – randomra Apr 3 '13 at 19:15

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

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

• Nice, but not eligible for that puzzle as the language is more recent than the question. – SteeveDroz Apr 25 '19 at 7:07
• When I was new here one of the first things I was told was that languages newer than questions aren't noncompeting anymore, and this is backed up by meta: codegolf.meta.stackexchange.com/questions/12877/… – Unrelated String Apr 25 '19 at 7:16
• Oh well, nevermind then. Apparently, rules are made to evolve and we must keep in mind that this site main purpose is to improve ourselves and have fun. Answer accepted! – SteeveDroz Apr 25 '19 at 20:58

# 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


# Mathematica 38 36

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


Usage

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

(* 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 • David, shorter and faster than Length@Divisors@n is DivisorSigma[0,n]. – Mr.Wizard May 13 '13 at 11:06
• Thanks. I hadn't known about that use of DivisorSigma. – DavidC May 14 '13 at 2:46
• math.stackexchange.com/questions/1551959/… – Sparr Nov 29 '15 at 19:49

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


# Japt, 8 bytes

@¶Xâ l}a


Try it

# Raku, 28 bytes

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


Try it online!

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

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


# Jelly, 6 bytes

2*RÆdi


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

• Why do you do 2*? Is it that every number after that has more divisors than n? – Erik the Outgolfer Oct 15 '16 at 5:48
• No; e.g., all primes have exactly two divisors. However, we are searching for the smallest positive integer with n divisors. Since 2**(n-1) belongs to that range, the smallest one does as well. – Dennis Oct 15 '16 at 5:50
• 5 bytes – caird coinheringaahing Dec 11 '20 at 22:11

# 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


# 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

• 6 bytes with .Δ (find first). – ovs Dec 14 '20 at 0:05

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


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


# 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