Give the smallest number that has N divisors
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).
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)
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.