21
\$\begingroup\$

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.

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

32 Answers 32

6
\$\begingroup\$

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

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

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)
\$\endgroup\$
2
  • \$\begingroup\$ Seems to go into an infinite loop for input 1. \$\endgroup\$ Apr 3 '13 at 16:05
  • \$\begingroup\$ 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. \$\endgroup\$ Apr 3 '13 at 16:31
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
5
  • \$\begingroup\$ I'm hitting the recursion limit on 11, 13, 17, 19, and others. \$\endgroup\$ Apr 3 '13 at 17:31
  • \$\begingroup\$ @StevenRumbalski Nobody mentioned that the program should work with arbitrary integers. Unfortunately the numbers grow up pretty fast even with small inputs. \$\endgroup\$
    – Bakuriu
    Apr 3 '13 at 19:00
  • \$\begingroup\$ 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) \$\endgroup\$
    – grc
    Apr 4 '13 at 1:18
  • \$\begingroup\$ Because I find 66 a little too evil, you can save 2 characters if you use sum(k%-~i<1for i in range(k)) \$\endgroup\$
    – Volatility
    Apr 25 '13 at 21:51
  • \$\begingroup\$ f=lambda n,k=1:n==sum(k%-~i<1for i in range(k))or-~f(n,k+1) saves 7 bytes. \$\endgroup\$
    – Dennis
    Oct 15 '16 at 5:32
4
\$\begingroup\$

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.

\$\endgroup\$
10
  • \$\begingroup\$ There was no code-golf tag so I gave a long answer! oops \$\endgroup\$
    – DavidC
    Apr 3 '13 at 13:23
  • \$\begingroup\$ @DavidCarraher I just guessed :) \$\endgroup\$ Apr 3 '13 at 13:28
  • \$\begingroup\$ 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. \$\endgroup\$
    – DavidC
    Apr 3 '13 at 13:31
  • \$\begingroup\$ @DavidCarraher See edit. Re: timings - My machine is way toooo slow :( \$\endgroup\$ Apr 3 '13 at 13:35
  • \$\begingroup\$ 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. \$\endgroup\$ Apr 3 '13 at 16:41
3
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ ...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). \$\endgroup\$ Sep 9 '20 at 10:40
  • \$\begingroup\$ 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... \$\endgroup\$ Sep 9 '20 at 10:44
  • \$\begingroup\$ @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! \$\endgroup\$
    – plannapus
    Sep 10 '20 at 5:54
3
\$\begingroup\$

J, 33 chars

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

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

   f 19
262144
\$\endgroup\$
3
\$\begingroup\$

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]
\$\endgroup\$
2
  • \$\begingroup\$ 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? \$\endgroup\$
    – shiona
    Apr 5 '13 at 17:04
  • \$\begingroup\$ 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). \$\endgroup\$
    – Will Ness
    Apr 13 '13 at 19:52
3
\$\begingroup\$

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
\$\endgroup\$
4
  • \$\begingroup\$ That's a poor golf score, but +1 for the path you've taken! \$\endgroup\$
    – SteeveDroz
    Apr 17 '13 at 6:05
  • \$\begingroup\$ 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) \$\endgroup\$
    – AMK
    Apr 17 '13 at 15:59
  • \$\begingroup\$ 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. \$\endgroup\$
    – AMK
    Apr 17 '13 at 16:09
  • \$\begingroup\$ @AMK Yes, you're right. Thanks for pointing that out. \$\endgroup\$
    – Ray
    Apr 17 '13 at 16:27
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

APL 33

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

Example:

F 6
12           
\$\endgroup\$
2
\$\begingroup\$

APL (25)

{⍵{⍺=+/0=⍵|⍨⍳⍵:⍵⋄⍺∇⍵+1}1}
\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$
    – XzKto
    Apr 4 '13 at 12:55
  • \$\begingroup\$ 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 \$\endgroup\$
    – marinus
    Apr 5 '13 at 11:19
  • \$\begingroup\$ 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 ) \$\endgroup\$
    – XzKto
    Apr 5 '13 at 12:21
2
\$\begingroup\$

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

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

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 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) \$\endgroup\$ Apr 3 '13 at 18:46
  • 2
    \$\begingroup\$ @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. \$\endgroup\$
    – randomra
    Apr 3 '13 at 19:15
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Nice, but not eligible for that puzzle as the language is more recent than the question. \$\endgroup\$
    – SteeveDroz
    Apr 25 '19 at 7:07
  • 1
    \$\begingroup\$ 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/… \$\endgroup\$ Apr 25 '19 at 7:16
  • \$\begingroup\$ 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! \$\endgroup\$
    – SteeveDroz
    Apr 25 '19 at 20:58
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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

Mathematica graphics

\$\endgroup\$
3
  • \$\begingroup\$ David, shorter and faster than Length@Divisors@n is DivisorSigma[0,n]. \$\endgroup\$
    – Mr.Wizard
    May 13 '13 at 11:06
  • \$\begingroup\$ Thanks. I hadn't known about that use of DivisorSigma. \$\endgroup\$
    – DavidC
    May 14 '13 at 2:46
  • \$\begingroup\$ math.stackexchange.com/questions/1551959/… \$\endgroup\$
    – Sparr
    Nov 29 '15 at 19:49
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

Japt, 8 bytes

@¶Xâ l}a

Try it

\$\endgroup\$
2
1
\$\begingroup\$

Raku, 28 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
2
  • \$\begingroup\$ 7 bytes by simplifying the range to all natural numbers \$\endgroup\$
    – Jo King
    Oct 5 '20 at 7:45
  • \$\begingroup\$ I managed to save one more byte using a different approach... \$\endgroup\$ Dec 13 '20 at 23:29
1
\$\begingroup\$

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.
\$\endgroup\$
3
  • \$\begingroup\$ Why do you do 2*? Is it that every number after that has more divisors than n? \$\endgroup\$ Oct 15 '16 at 5:48
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – Dennis
    Oct 15 '16 at 5:50
  • \$\begingroup\$ 5 bytes \$\endgroup\$ Dec 11 '20 at 22:11
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ 6 bytes with (find first). \$\endgroup\$
    – ovs
    Dec 14 '20 at 0:05
0
\$\begingroup\$

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;}
\$\endgroup\$
0
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.