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

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


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

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.

# 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

# 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 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 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 at 20:58

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

# 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


• 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

# Jelly, 6 bytes (non-competing)

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

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)


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