Donner le plus petit nombre qui a N diviseurs

17

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.

SteeveDroz
la source
2
Est-ce du code-golf ou du code-challenge?
marinus
Oups, j'ai oublié cette balise, code-golf!
SteeveDroz
11
A005179
Peter Taylor

Réponses:

6

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

Howard
la source
Félicitations! 23 personnages ... wow!
SteeveDroz
19:{⍵⍳⍨(+/⊢=⊢∧⍳)¨⍳2*⍵}
Adám
Je ne pense pas que vous ayez besoin de définir f.
Zacharý
5

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)
Howard
la source
Semble entrer dans une boucle infinie pour l'entrée 1.
Peter Taylor
Jusqu'à présent, ma meilleure solution emprunte beaucoup à la vôtre, dans la mesure où je pense qu'elle mérite d'être un commentaire plutôt qu'une réponse distincte.
Peter Taylor
4

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
Nikita Borisov
la source
4

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
Bakuriu
la source
J'atteins la limite de récursivité sur 11, 13, 17, 19 et autres.
Steven Rumbalski
@StevenRumbalski Personne n'a mentionné que le programme devrait fonctionner avec des entiers arbitraires. Malheureusement, les chiffres augmentent assez rapidement même avec de petites entrées.
Bakuriu du
Vous pouvez enregistrer certains caractères en remplaçant if elsepar and oret ==1par <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
Parce que je trouve 66 un peu trop diabolique, vous pouvez enregistrer 2 personnages si vous utilisezsum(k%-~i<1for i in range(k))
Volatilité
f=lambda n,k=1:n==sum(k%-~i<1for i in range(k))or-~f(n,k+1)enregistre 7 octets.
Dennis
4

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.

Dr. belisarius
la source
Il n'y avait pas de code-golf, j'ai donc donné une longue réponse! oups
DavidC
@DavidCarraher Je viens de deviner :)
Dr belisarius
Je pensais que je savais ce qui DivisorSumrevient (la somme des diviseurs) mais je ne vois pas comment cela est déterminant pour répondre à la question posée. Pourriez-vous expliquer comment cela fonctionne? BTW, je pense que vous devriez inclure des données de synchronisation pour n = 200; la fonction est remarquablement rapide, compte tenu de tous les chiffres qu'elle a dû vérifier.
DavidC
@DavidCarraher Voir modifier. Re: timings - Ma machine est beaucoup trop lente :(
Dr. belisarius
Mathematica n'a-t-il pas suffisamment de fonctionnalités intégrées pour que l'approche plus sophistiquée autour de l'affacturage soit plus courte? Si c'est le cas, je suis déçu.
Peter Taylor
3

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
randomra
la source
3

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]
shiona
la source
L'édition n'a pas raccourci la réponse, mais elle ressemble peut-être plus à un haskell. De plus, j'ai toujours inclus le retour à la ligne à la longueur de mon code, est-ce faux?
shiona
Je pensais que tu avais mal compté; l'objectif principal de la modification était de mettre à jour le décompte. Le changement de code lui-même était mineur. Je pense que les autres entrées ici ne comptent pas non plus la nouvelle ligne de fin, comme par exemple l'entrée pour J (33 caractères).
Will Ness
2

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
tmartin
la source
2

APL 33

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

Exemple:

F 6
12           
Graham
la source
2

APL (25)

{⍵{⍺=+/0=⍵|⍨⍳⍵:⍵⋄⍺∇⍵+1}1}
marinus
la source
Tricheur! echo -n '{⍵ {⍺ = + / 0 = ⍵ | ⍨⍳⍵: ⍵⋄⍺∇⍵ + 1} 1}' | wc -c me donne 47! Mais vraiment, pourriez-vous s'il vous plaît me donner un lien vers un tutoriel facile pour APL? J'ai essayé de le chercher sur Google et j'ai lu quelques articles, mais toujours à la fin, je veux toujours demander "Pourquoi font-ils cela :(?". Je n'ai jamais travaillé avec un langage de syntaxe non ASCII et je veux savoir si il a un réel avantage.
XzKto
C'est pour Dyalog APL, c'est ce que j'utilise, vous pouvez télécharger la version Windows gratuitement sur le même site. dyalog.com/MasteringDyalogAPL/MasteringDyalogAPL.pdf
marinus
Wow, on dirait que je peux vraiment comprendre celui-ci. Merci pour le lien! Le seul inconvénient est qu'ils ont une politique de licence très étrange, mais peut-être que je dois juste améliorer mon anglais)
XzKto
2

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
plannapus
la source
2

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

XzKto
la source
N=>eval("for(j=i=m=1;m-N||j-i;j>i?i+=m=j=1:m+=!(i%++j));i")
TuxCrafting du
2

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.

Fors
la source
Le moyen efficace, par opposition à court, de le calculer serait de factoriser nen nombres premiers (avec répétition), de trier par ordre décroissant, de décrémenter chacun, de compresser avec une séquence infinie de nombres premiers, puis de plier le produit dep^(factor-1)
Peter Taylor
2
@PeterTaylor Pas nécessaire. Pour n = 16 = 2 * 2 * 2 * 2, la solution est 2 ^ 3 * 3 ^ 1 * 5 ^ 1 = 120, pas 2 ^ 1 * 3 ^ 1 * 5 ^ 1 * 7 ^ 1 = 210.
randomra
2

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.

Fors
la source
2

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
Rayon
la source
C'est un mauvais score de golf, mais +1 pour le chemin que vous avez emprunté!
SteeveDroz
Pour 8 = 2 * 2 * 2, cet algorithme donne le nombre 2 * 3 * 5 = 30. Mais la meilleure solution est 2 ^ 3 * 3 = 24 (pour 8 = 2 * 4)
AMK
La solution est incorrecte si le nombre spécifié de diviseurs contient une puissance élevée de petit nombre premier. Les solutions énumérées les plus probables pour les puissances de 10 sont donc fausses.
AMK
@AMK Oui, vous avez raison. Merci d'avoir fait remarquer cela.
Ray
2

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 .

Chaîne indépendante
la source
Sympa, mais pas éligible pour ce puzzle car la langue est plus récente que la question.
SteeveDroz
Quand j'étais nouveau ici, l'une des premières choses qui m'ont été dites était que les langues plus récentes que les questions ne sont plus non compétitives, et cela est sauvegardé par meta: codegolf.meta.stackexchange.com/questions/12877/…
Unrelated String
Eh bien, peu importe alors. Apparemment, les règles sont faites pour évoluer et nous devons garder à l'esprit que le but principal de ce site est de s'améliorer et de s'amuser. Réponse acceptée!
SteeveDroz
1

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.

ugoren
la source
1

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

Graphiques Mathematica

DavidC
la source
David, plus court et plus rapide que Length@Divisors@nest DivisorSigma[0,n].
Mr.Wizard
Merci. Je ne connaissais pas cette utilisation de DivisorSigma.
DavidC
1

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.
Dennis
la source
Pourquoi tu fais ça 2*? Est-ce que chaque nombre après cela a plus de diviseurs que n?
Erik l'Outgolfer
2
Non; par exemple, tous les nombres premiers ont exactement deux diviseurs. Cependant, nous recherchons le plus petit entier positif avec n diviseurs. Comme 2**(n-1)appartient à cette gamme, la plus petite aussi.
Dennis
0

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;}
Cisplatine
la source
0

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)
Baptiste M.
la source
0

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)
Brad Gilbert b2gills
la source