Dê o menor número que possua N divisores

17

Sua função pega um número natural e retorna o menor número natural que possui exatamente a quantidade de divisores, incluindo ele próprio.

Exemplos:

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

A função não precisa retornar a lista de divisores, eles estão apenas aqui para os exemplos.

SteeveDroz
fonte
2
Isso é código-golfe ou código-desafio?
Marinus #
Opa, esqueci essa tag, código-golfe!
precisa saber é o seguinte
11
A005179
Peter Taylor

Respostas:

6

APL, 25 24 23 caracteres

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

Define uma função fque pode ser usada para calcular os números:

> f 13
4096

> f 14
192

A solução utiliza o fato de que LCM (n, x) == n se if x divide n . Assim, o bloco {+/⍵=⍵∧⍳⍵}simplesmente calcula o número de divisores. Esta função é aplicada a todos os números de 1 a 2 ^ d ¨⍳2*⍵ . A lista resultante é então pesquisada pelo próprio d ( ⍳⍵), que é a função desejada f (d) .

Howard
fonte
Parabéns! 23 caracteres ... uau!
precisa saber é o seguinte
19:{⍵⍳⍨(+/⊢=⊢∧⍳)¨⍳2*⍵}
Adám 28/06
Eu não acho que você precise definir f.
Zacharý
5

GolfScript, 29 28 caracteres

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

Edit: Um único caractere pode ser salvo se restringirmos a pesquisa a <2 ^ n, graças a Peter Taylor por essa ideia.

Versão anterior:

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

Uma tentativa no GolfScript, execute online .

Exemplos:

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

O código contém essencialmente três blocos que são explicados em detalhes nas seguintes linhas.

# 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
fonte
Parece entrar em um loop infinito para entrada 1.
Peter Taylor
Minha melhor solução até agora empresta bastante a sua, na medida em que acho que merece mais um comentário do que uma resposta separada.
Peter Taylor
4

Python: 64

Revisando a solução de Bakuriu e incorporando a sugestão do grc, bem como o truque da solução R do plannapus, obtemos:

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

O exemplo acima aumentará RuntimeError: maximum recursion depth exceededcom pequenas entradas no CPython e, mesmo definindo o limite para um número enorme, provavelmente causará alguns problemas. Nas implementações python que otimizam a recursão da cauda, ​​deve funcionar bem.

Uma versão mais detalhada, que não deve ter tais limitações, é a seguinte solução de 79 bytes:

def f(n,k=1):
    while 1:
        if sum(k%i<1for i in range(1,k+1))==n:return k
        k+=1
Bakuriu
fonte
Estou atingindo o limite de recursão em 11, 13, 17, 19 e outros.
Steven Rumbalski
@StevenRumbalski Ninguém mencionou que o programa deve funcionar com números inteiros arbitrários. Infelizmente, os números crescem muito rapidamente, mesmo com pequenas entradas.
Bakuriu 03/04
Você pode salvar alguns caracteres usando substituindo if elsecom and ore ==1com <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
Porque acho 66 um pouco mal, você pode salvar 2 caracteres se você usarsum(k%-~i<1for i in range(k))
Volatilidade
f=lambda n,k=1:n==sum(k%-~i<1for i in range(k))or-~f(n,k+1)salva 7 bytes.
Dennis
4

Mathematica 38 36

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

Uso:

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

Resultado:

498960

Editar

Alguma explicação:

DivisorSum [n, forma] representa a soma da forma [i] para todos os que dividem n.

Como form[i]estou usando a função 1 &, ela retorna sempre 1, calculando com eficiência a soma dos divisores de maneira concisa.

Dr. belisarius
fonte
Como não havia código de código de golfe, dei uma resposta longa! oops
DavidC 03/04
@DavidCarraher Eu só adivinhou :)
Dr. belisarius
Eu pensei que sabia o que DivisorSumretorna (a soma dos divisores), mas não vejo como isso é instrumental para responder à pergunta. Você explicaria como isso funciona? BTW, acho que você deve incluir dados de tempo para n = 200; a função é notavelmente rápida, considerando todos os números que precisavam verificar.
DavidC
@DavidCarraher Ver edição. Re: timings - Minha máquina está muito lenta :(
Dr. belisarius
O Mathematica não possui built-ins suficientes para que a abordagem mais sofisticada do fatoração seja mais curta? Se for esse o caso, estou decepcionado.
Peter Taylor
3

J, 33 caracteres

Bastante rápido, analisa todos os números menores e calcula o número de divisores com base na fatoração.

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

   f 19
262144
randomra
fonte
3

Haskell 54

Solução rápida e suja (tão legível e não complicada):

f k=head[x|x<-[k..],length[y|y<-[1..x],mod x y==0]==k]
shiona
fonte
A edição não tornou a resposta mais curta, mas talvez seja mais semelhante a haskell. Além disso, sempre incluí a nova linha no meu código, isso está errado?
Shiona
Eu pensei que você estivesse errado; o principal objetivo da edição era atualizar a contagem. A mudança no código em si foi pequena. Acho que as outras entradas aqui também não contam a nova linha à direita, como, por exemplo, a entrada para J (33 caracteres).
Will Ness
2

K, 42

Solução recursiva ineficiente que explode facilmente a pilha

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

APL 33

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

Exemplo:

F 6
12           
Graham
fonte
2

APL (25)

{⍵{⍺=+/0=⍵|⍨⍳⍵:⍵⋄⍺∇⍵+1}1}
marinus
fonte
Trapaceiro! eco -n '{⍵ {⍺ = + / 0 = ⍵ | ⍨⍳⍵: ⍵⋄⍺∇⍵ + 1} 1}' | wc -c me dá 47! Mas, sério, você poderia me dar um link para algum tutorial fácil para APL? Tentei pesquisar no Google e li alguns artigos, mas, no final, sempre quero perguntar "Por que eles estão fazendo isso :(?". Nunca trabalhei com nenhuma linguagem de sintaxe não-ASCII e quero descobrir se tem qualquer vantagem real.
XzKto
Isto é para o Dyalog APL, que é o que eu uso, você pode baixar a versão do Windows gratuitamente no mesmo site. dyalog.com/MasteringDyalogAPL/MasteringDyalogAPL.pdf
marinus
Uau, parece que eu realmente posso entender esse. Obrigado pelo link! A única desvantagem é que eles têm alguma política de licenciamento muito estranho, mas talvez eu só preciso melhorar meu Inglês)
XzKto
2

R - 47 caracteres

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

!n%%1:nfornece um vetor de booleanos: TRUE quando um número inteiro de 1 a n é um divisor de n e FALSE, se não. sum(!n%%1:n)força os booleanos a 0 se FALSE e 1 se VERDADEIRO e os soma, para queN-sum(...) é 0 quando o número de divisores é N. 0 é então interpretado como FALSO porwhile qual então pára.

Uso:

f(6)
[1] 12
f(13)
[1] 4096
plannapus
fonte
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}

Realmente, existem apenas 46 caracteres significativos:

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

Eu provavelmente deveria aprender um idioma com sintaxe mais curta :)

XzKto
fonte
N=>eval("for(j=i=m=1;m-N||j-i;j>i?i+=m=j=1:m+=!(i%++j));i")
TuxCrafting 15/10/16
2

Haskell: 49 caracteres

Pode ser visto como uma melhoria da solução anterior da Haskell, mas foi concebido por si só (aviso: é muito lento):

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

É uma função bastante interessante, por exemplo, observe que f (p) = 2 ^ (p-1), onde p é um número primo.

Para s
fonte
A maneira eficiente, em vez de curta, de calculá-lo seria fatorar nprimos (com repetição), ordenar descendente, decrementar cada um, compactar com uma sequência infinita de primos e depois dobrar o produto dep^(factor-1)
Peter Taylor
2
@ Petereteray Não é necessário. Para n = 16 = 2 * 2 * 2 * 2, a solução é 2 ^ 3 * 3 ^ 1 * 5 ^ 1 = 120, não 2 ^ 1 * 3 ^ 1 * 5 ^ 1 * 7 ^ 1 = 210.
randomra
2

C: 66 64 caracteres

Uma solução quase curta:

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

E minha solução anterior que não se aplica:

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

Soluções muito mais curtas devem existir.

Para s
fonte
2

Haskell (120C), um método muito eficiente

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

Código do teste:

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

Este método é muito rápido. A idéia é primeiro encontrar os fatores primos de k=p1*p2*...*pm, onde p1 <= p2 <= ... <= pm. Então a resposta é n = 2^(pm-1) * 3^(p(m-1)-1) * 5^(p(m-2)-1) ....

Por exemplo, fatorando k = 18, obtemos 18 = 2 * 3 * 3. Os 3 primeiros números primos são 2, 3, 5. Portanto, a resposta n = 2 ^ (3-1) * 3 ^ (3-1) * 5 ^ (2-1) = 4 * 9 * 5 = 180

Você pode testá-lo em 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
Raio
fonte
Essa é uma baixa pontuação de golfe, mas +1 no caminho que você seguiu!
precisa saber é o seguinte
Para 8 = 2 * 2 * 2, esse algoritmo fornece o número 2 * 3 * 5 = 30. Mas melhor solução é de 2 ^ 3 * 3 = 24 (para 8 = 2 * 4)
AMK
A solução está incorreta se o número especificado de divisores contiver uma alta potência do prime pequeno. Portanto, as soluções listadas mais prováveis ​​para potências de 10 estão erradas.
AMK
@ AMK Sim, você está certo. Obrigado por apontar isso.
Raio
2

Braquilog , 2 bytes

fl

Experimente online!

Toma entrada através de sua variável de saída e saídas através de sua variável de entrada.

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

Esse mesmo predicado, recebendo entrada por sua variável de entrada e enviando por sua variável de saída, resolve esse desafio .

String não relacionada
fonte
Bom, mas não elegível para esse quebra-cabeça, pois o idioma é mais recente que a questão.
precisa saber é o seguinte
Quando eu era novo aqui, uma das primeiras coisas que me disseram foi que os idiomas mais novos que as perguntas não são mais concorrentes, e isso é acompanhado por meta: codegolf.meta.stackexchange.com/questions/12877/…
String não relacionada a
Oh bem, deixa pra lá então. Aparentemente, as regras são feitas para evoluir e devemos ter em mente que o objetivo principal deste site é melhorar a nós mesmos e nos divertir. Resposta aceita!
SteeveDroz
1

C, 69 caracteres

Não é a mais curta, mas a primeira resposta 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)conta divisores de nno intervalo 1..s. Então f(n,n)conta os divisores de n.
g(d)loops (por recursão) até f(x,x)==d, então retorna x.

Ugoren
fonte
1

Mathematica 38 36

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

Uso

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

(* 64 *)

Primeira entrada (antes da code-golfadição da tag à pergunta.)

Um problema direto, dado que Divisors[n]retorna os divisores de n(inclusive n) e Length[Divisors[n]]retorna o número desses divisores. **

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

Exemplos

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

Gráficos do Mathematica

DavidC
fonte
David, mais baixo e mais rápido do que Length@Divisors@né DivisorSigma[0,n].
Mr.Wizard
Obrigado. Eu não sabia sobre esse uso de DivisorSigma.
DavidC 14/05
1

Gelatina , 6 bytes (não concorrente)

2*RÆdi

Experimente online! ou verifique todos os casos de teste .

Como funciona

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
fonte
Por que você faz 2*? Será que todo número depois disso tem mais divisores que n?
Erik the Outgolfer
2
Não; por exemplo, todos os números primos têm exatamente dois divisores. No entanto, estamos procurando o menor número inteiro positivo com n divisores. Como 2**(n-1)pertence a esse intervalo, o menor também.
Dennis
0

C ++, 87 caracteres

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;}
Cisplatina
fonte
0

Python2, 95 caracteres, Não recursivo

Um pouco mais detalhado do que as outras soluções python, mas não é recursivo, portanto não atinge o limite de recursão do 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.
fonte
0

Perl 6 , 39 caracteres

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

Exemplo de uso:

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
fonte