Votre fonction prend un nombre naturel et renvoie le plus petit nombre naturel qui a exactement ce nombre de diviseurs, y compris lui-même.

Exemples:

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

La fonction n'a pas à retourner la liste des diviseurs, ils ne sont là que pour les exemples.

APL, 25 24 23 caractères

f←{({+/⍵=⍵∧⍳⍵}¨⍳2*⍵)⍳⍵}

Définit une fonction fqui peut ensuite être utilisée pour calculer les nombres:

> f 13
4096

> f 14
192

La solution utilise le fait que LCM (n, x) == n ssi x divise n . Ainsi, le bloc {+/⍵=⍵∧⍳⍵}calcule simplement le nombre de diviseurs. Cette fonction est appliquée à tous les nombres de 1 à 2 ^ d ¨⍳2*⍵ . La liste résultante est ensuite recherchée pour d lui-même ( ⍳⍵) qui est la fonction souhaitée f (d) .

GolfScript, 29 28 caractères

{.{\.,{)1$\%},,-=}+2@?,?}:f;

Edit: Un seul caractère peut être enregistré si nous limitons la recherche à <2 ^ n, merci à Peter Taylor pour cette idée.

La version précédente:

{.{\)..,{)1$\%},,-@=!}+do}:f;

Une tentative dans GolfScript, exécutée en ligne .

Exemples:

13 f p  # => 4096
14 f p  # => 192
15 f p  # => 144

Le code contient essentiellement trois blocs qui sont expliqués en détail dans les lignes suivantes.

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

Python: 64

En révisant la solution de Bakuriu et en incorporant la suggestion de grc ainsi que l'astuce de la solution R de plannapus, nous obtenons:

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)

Ce qui précède soulèvera un RuntimeError: maximum recursion depth exceeded avec de petites entrées dans CPython, et même en fixant la limite à un nombre énorme, cela posera probablement des problèmes. Sur les implémentations python qui optimisent la récursivité de queue, cela devrait fonctionner correctement.

Une version plus détaillée, qui ne devrait pas avoir de telles limitations, est la solution suivante de 79 octets:

def f(n,k=1):
    while 1:
        if sum(k%i<1for i in range(1,k+1))==n:return k
        k+=1

Mathematica 38 36

(For[i=1,DivisorSum[++i,1&]!=#,];i)&

Usage:

(For[i=1,DivisorSum[++i,1&]!=#,];i)&@200

Résultat:

498960

Éditer

Quelques explications:

DivisorSum [n, form] représente la somme de la forme [i] pour tout i qui divise n.

Comme form[i]j'utilise la fonction 1 &, cela revient toujours 1, calculant ainsi efficacement la somme des diviseurs de manière laconique.

J, 33 caractères

Assez rapide, passe par tous les plus petits nombres et calcule le nombre de diviseurs en fonction de la factorisation.

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

   f 19
262144

Haskell 54

Solution rapide et sale (si lisible et non délicate):

f k=head[x|x<-[k..],length[y|y<-[1..x],mod x y==0]==k]

K, 42

Solution récursive inefficace qui fait exploser la pile assez facilement

{{$[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 

Exemple:

F 6
12           

APL (25)

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

R - 47 caractères

f=function(N){n=1;while(N-sum(!n%%1:n))n=n+1;n}

!n%%1:ndonne un vecteur de booléens: VRAI quand un entier de 1 à n est un diviseur de n et FAUX sinon. sum(!n%%1:n)contraint les booléens à 0 si FAUX et 1 si VRAI et les additionne, de sorte queN-sum(...) c'est 0 lorsque le nombre de diviseurs est N. 0 est alors interprété comme FAUX par whilelequel s'arrête ensuite.

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}

Il n'y a vraiment que 46 personnages significatifs:

for(j=i=m=1;m-N||j-i;j>i?i+=m=j=1:m+=!(i%++j))

Je devrais probablement apprendre une langue avec une syntaxe plus courte :)

Haskell: 49 caractères

Cela pourrait être considéré comme une amélioration de la solution Haskell antérieure, mais elle a été conçue à part entière (avertissement: c'est très lent):

f n=until(\i->n==sum[1|j<-[1..i],rem i j<1])(+1)1

C'est une fonction assez intéressante, notons par exemple que f (p) = 2 ^ (p-1), où p est un nombre premier.

C: 66 64 caractères

Une solution presque courte:

i;f(n){while(n-g(++i));return i;}g(j){return j?!(i%j)+g(j-1):0;}

Et ma solution précédente qui ne récuse pas:

i;j;k;f(n){while(k-n&&++i)for(k=0,j=1;j<=i;k+=!(i%j++));return i;}

Des solutions beaucoup plus courtes doivent exister.

Haskell (120C), une méthode très efficace

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

Code de test:

main=do putStrLn$show$ f (100000::Integer)

Cette méthode est très rapide. L'idée est d'abord de trouver les facteurs premiers de k=p1*p2*...*pm, où p1 <= p2 <= ... <= pm. Alors la réponse est n = 2^(pm-1) * 3^(p(m-1)-1) * 5^(p(m-2)-1) ....

Par exemple, en factorisant k = 18, nous obtenons 18 = 2 * 3 * 3. Les 3 premiers nombres premiers sont 2, 3, 5. Donc, la réponse n = 2 ^ (3-1) * 3 ^ (3-1) * 5 ^ (2-1) = 4 * 9 * 5 = 180

Vous pouvez le tester sous 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

Brachylog , 2 octets

fl

Essayez-le en ligne!

Prend l'entrée via sa variable de sortie et sort via sa variable d'entrée.

f     The list of factors of
      the input variable
 l    has length equal to
      the output variable.

Ce même prédicat exact, prenant l'entrée via sa variable d'entrée et la sortie via sa variable de sortie, résout ce problème à la place .

C, 69 caractères

Pas la plus courte, mais la première réponse C:

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)compte les diviseurs de nla plage 1..s. Compte donc les f(n,n)diviseurs de n.
g(d)boucle (par récursivité) jusqu'à f(x,x)==d, puis retourne x.

Mathematica 38 36

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

Usage

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

(* 64 *)

Première entrée (avant l' code-golfajout de la balise à la question.)

Un problème simple, étant donné que Divisors[n]renvoie les diviseurs de n(y compris n) et Length[Divisors[n]]renvoie le nombre de ces diviseurs. **

smallestNumber[nDivisors_] :=
   Module[{k = 1},
   While[Length[Divisors[k]] != nDivisors, k++];k]

Exemples

Table[{i, nDivisors[i]}, {i, 1, 20}] // Grid

Gelée , 6 octets (non concurrent)

2*RÆdi

Essayez-le en ligne!ou vérifiez tous les cas de test .

Comment ça fonctionne

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.

C ++, 87 caractères

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 caractères, non récursif

Un peu plus verbeux que les autres solutions python mais il est non récursif donc il n'atteint pas la limite de récursivité de cpython:

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 caractères

{my \a=$=0;a++while $_-[+] a X%%1..a;a}

Exemple d'utilisation:

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)