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.
Respostas:
APL,
252423 caracteresDefine uma função
f
que pode ser usada para calcular os números: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) .fonte
{⍵⍳⍨(+/⊢=⊢∧⍳)¨⍳2*⍵}
f
.GolfScript,
2928 caracteresEdit: Um único caractere pode ser salvo se restringirmos a pesquisa a <2 ^ n, graças a Peter Taylor por essa ideia.
Versão anterior:
Uma tentativa no GolfScript, execute online .
Exemplos:
O código contém essencialmente três blocos que são explicados em detalhes nas seguintes linhas.
fonte
1
.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:
fonte
Python: 66
O exemplo acima aumentará
RuntimeError: maximum recursion depth exceeded
com 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:
fonte
if else
comand or
e==1
com<1
:f=lambda n,k=1:n==sum(k%i<1for i in range(1,k+1))and k or f(n,k+1)
sum(k%-~i<1for i in range(k))
f=lambda n,k=1:n==sum(k%-~i<1for i in range(k))or-~f(n,k+1)
salva 7 bytes.Mathematica
3836Uso:
Resultado:
Editar
Alguma explicação:
Como
form[i]
estou usando a função1 &
, ela retorna sempre1
, calculando com eficiência a soma dos divisores de maneira concisa.fonte
DivisorSum
retorna (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.J, 33 caracteres
Bastante rápido, analisa todos os números menores e calcula o número de divisores com base na fatoração.
fonte
Haskell 54
Solução rápida e suja (tão legível e não complicada):
fonte
K, 42
Solução recursiva ineficiente que explode facilmente a pilha
.
fonte
APL 33
Exemplo:
fonte
APL (25)
fonte
R - 47 caracteres
!n%%1:n
fornece 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:
fonte
Javascript 70
Realmente, existem apenas 46 caracteres significativos:
Eu provavelmente deveria aprender um idioma com sintaxe mais curta :)
fonte
N=>eval("for(j=i=m=1;m-N||j-i;j>i?i+=m=j=1:m+=!(i%++j));i")
Haskell: 49 caracteres
Pode ser visto como uma melhoria da solução anterior da Haskell, mas foi concebido por si só (aviso: é muito lento):
É uma função bastante interessante, por exemplo, observe que f (p) = 2 ^ (p-1), onde p é um número primo.
fonte
n
primos (com repetição), ordenar descendente, decrementar cada um, compactar com uma sequência infinita de primos e depois dobrar o produto dep^(factor-1)
C:
6664 caracteresUma solução quase curta:
E minha solução anterior que não se aplica:
Soluções muito mais curtas devem existir.
fonte
Haskell (120C), um método muito eficiente
Código do teste:
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
:fonte
Braquilog , 2 bytes
Experimente online!
Toma entrada através de sua variável de saída e saídas através de sua variável de entrada.
Esse mesmo predicado, recebendo entrada por sua variável de entrada e enviando por sua variável de saída, resolve esse desafio .
fonte
C, 69 caracteres
Não é a mais curta, mas a primeira resposta C:
f(n,s)
conta divisores den
no intervalo1..s
. Entãof(n,n)
conta os divisores den
.g(d)
loops (por recursão) atéf(x,x)==d
, então retorna x.fonte
Mathematica
3836Uso
Primeira entrada (antes da
code-golf
adição da tag à pergunta.)Um problema direto, dado que
Divisors[n]
retorna os divisores den
(inclusiven
) eLength[Divisors[n]]
retorna o número desses divisores. **Exemplos
fonte
Length@Divisors@n
éDivisorSigma[0,n]
.DivisorSigma
.Gelatina , 6 bytes (não concorrente)
Experimente online! ou verifique todos os casos de teste .
Como funciona
fonte
2*
? Será que todo número depois disso tem mais divisores que n?2**(n-1)
pertence a esse intervalo, o menor também.C ++, 87 caracteres
fonte
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:
fonte
Perl 6 , 39 caracteres
Exemplo de uso:
fonte