Há um número bastante curioso que aparece algumas vezes em problemas de matemática ou enigmas. O pseudo-fatorial (N) é o mínimo múltiplo comum (isto é, o mais baixo) comum dos números 1 a N; em outras palavras, é o número mais baixo que possui todos os números de 1 a N como fatores.
Por exemplo, pseudo-fatorial (7) = 3 * 4 * 5 * 7, que é o mesmo que 7! exceto que 2 e 6 foram removidos porque estão contidos em outros termos.
Escreva um programa para calcular o pseudo-fatorial (N) e, como sempre, o código mais curto vence.
Aqui está uma pequena lista para seu uso. Mais casos de teste podem ser encontrados no OEIS em A003418 .
Fatorial:
- 1
- 2
- 6
- 24
- 120
- 720
- 5040
Pseudo-fatorial:
- 1
- 2
- 6
- 12
- 60
- 60
- 420
code-golf
math
number-theory
factorial
Tony Ruth
fonte
fonte
2
e6
foram removidos da lista de múltiplos. Você pode esclarecer as regras?Respostas:
Dyalog APL , 3 bytes
APL vence Jelly ‽
⍳
1 argumento∧/
LCM atravésfonte
Gelatina , 4 bytes
Experimente online! ou verifique todos os casos de teste .
Como funciona
fonte
C (com x86), 52 bytes
Verifica números de 1 para cima. Para cada número, divide-o por todos os números de n para 1 e soma os restantes. Para quando a soma é 0.
Uso:
Não é óbvio como ele retorna um valor (não há
return
declaração).A convenção de chamada para x86 diz que a função deve retornar seu valor no
eax
registro. Convenientemente, a instrução de divisãoidiv
espera sua entradaeax
e gera o resultado emeax
(quociente) eedx
(restante). A última iteração dividek
por1
, entãoeax
, conterá o valor correto quando a função sair.Isso funciona apenas com otimizações ativadas (no modo de depuração, ele gera
421
).fonte
int
por padrão (incluindo o valor de retorno). Ele funciona para argumentos de função se eles forem declarados usando a chamada sintaxe "estilo antigo". A declaração com tipos definidos explicitamente seriaint d(n,k,b,t) int n,k,b,t; {...}
cdecl
estdcall
usar o mesmo método para o retorno de valor, então eu acho quex86
é o suficienteHaskell, 20 bytes
Exemplo de uso:
map f [1..7]
->[1,2,6,12,60,60,420]
.O
lcm
truque em Haskell.fonte
Python + SymPy, 45 bytes
Bastante auto-explicativo.
Python 2,
5754 bytesTeste em Ideone .
Como funciona
A entrada é armazenada em variáveis i e r .
exec
executa o seguinte código r vezes.Enquanto i varia de r a 1 , adicionamos o valor inicial de r (armazenado em t ) quantas vezes for necessário para r para criar um múltiplo de i . O resultado é, obviamente, um múltiplo de t .
O valor final de r é, portanto, um múltiplo de todos os números inteiros no intervalo [1, ..., n] , em que n é a entrada.
fonte
exec
truques de terceiros, há uma solução de 78 bytes:from fractions import*;lambda n:reduce(lambda x,y:x*y/gcd(x,y),range(1,n+1),1)
usa o fato dissolcm(x,y) = x*y/gcd(x,y)
.Python, 46 bytes
Procurando o múltiplo
c
deg(n-1)
diretamente. Antes, eu pensava que esse método encontraria 0 erroneamente como um múltiplo de qualquer coisa, mas oor
curto-circuito ou(c%n<1)*c
também pularác==0
porque 0 é Falsey.50 bytes:
Como a solução de Dennis , mas como uma função recursiva. Tendo calculado
g(n-1)
, procura o menor múltiploi*n
den
que também é múltiplo deg(n-1)
. Muito devagar.Graças a Dennis por 4 bytes, olhando para múltiplos em
n
vez deg(n-1)
.fonte
J, 9 bytes
Abordagem direta. Cria o intervalo de números
[0, ..., n-1]
, adiciona um a cada um e reduz-o usando o LCM.Uso
fonte
MATL , 4 bytes
Experimente online!
Explicação
fonte
Mathematica, 13 bytes
fonte
LCM
eRange
com@*
?LCM
opera elemento a elemento em uma lista, que seria passada porRange
, o que significa que apenas retornaria o lcm ( x ) para x de 1 a n . Além disso, há uma falta&
que fecharia a função anônima. Algo comoLCM@@Range@#&
13 bytes funcionaria.Julia, 11 bytes
Experimente online!
fonte
Pitão - 8 bytes
Verifica todos os números até encontrar um que seja divisível por
[1..N]
.Conjunto de Teste .
fonte
Oitava, 27 bytes
Cria uma função anônima que pode ser chamada como
ans(N)
.Demo Online
Explicação
Esta solução cria uma lista de todos os números entre
1
ex
(1:x
), converte-os em uma matriz de células comnum2cell
. Em seguida, a{:}
indexação cria uma lista separada por vírgula que é passada paralcm
vários argumentos de entrada para calcular o múltiplo menos comum. Um 1 é sempre passado como o primeiro argumento para,lcm
porquelcm
sempre precisa de pelo menos dois argumentos de entrada.fonte
lcm
no Octave aceita mais de 2 entradas! InteressanteMATLAB, 49 bytes
fonte
bsxfun
Perl 6 , 13 bytes
Bloco de código anônimo que cria um intervalo de 1 até a entrada (inclusive) e reduz isso com
&infix:<lcm>
.Exemplo:
fonte
JavaScript (ES6),
9288807469 bytes:Obrigado @ConorOBrien e @Neil
fonte
b?g(b,a%b):a
salva um byte.y*++i/g(y,i)
economiza mais alguns bytes.05AB1E, 20 bytes
Explicação
Experimente online
fonte
Minkolang 0.15 , 12 bytes
Eu tenho duas soluções de 12 bytes e incluí as duas.
Experimente aqui!
Explicação
Tão simples quanto possível.
Experimente aqui!
Explicação
Uma terceira solução pode ser derivada disso: remova a
1
e adicione ad
após a corrented
. Nos dois casos, o número extra é necessário porque o loop for é executado muitas vezes, e fazê-lo menos uma vez leva dois bytes (um1-
pouco antes do[
).fonte
Ruby, 25 bytes
Ruby, 25 bytes
fonte
g=
.Idioma do GameMaker, 60 bytes
Baseado na lógica da resposta de anatolyg.
fonte
PHP,
615248 byteseconomizou 9 bytes graças a @ user59178, 4 bytes mesclando os loops.
A recursão no PHP é volumosa devido à
function
palavra-chave; então eu uso a iteração.E com alguns "truques" pequenos, agora até venci o JS de Arnauld .
recebe entrada do argumento da linha de comando. Corra com
-r
.demolir
destroçado
Na verdade, são dois loops em um:
Nota: copiado da minha resposta na duplicata
fonte
Japonês, 10 bytes
Nenhum LCM embutido.
Tente
fonte
Pyke, 3 bytes, não-competitivo
Experimente aqui!
fonte
Hoon , 67 bytes
Crie a lista
[1..n]
, dobre a lista com lcm. Infelizmente, o Hoon stdlib não possui um pré-criado que eu possa usar: /fonte
, 7 caracteres / 9 bytes
Try it here (ES6 only).
Apenas um LCM de faixa inclusiva de 1 a entrada.
fonte
AWK, 42 bytes
Uso da linha de comando:
Eu não vi uma
AWK
solução e uma duplicata da pergunta acabou de ser postada ontem, então pensei em juntar isso. É uma solução bastante lenta para19
ou maior na minha caixa, mas funciona.fonte
QBIC ,
3532 bytesIsso me trouxe aqui.
Explicação:
Aqui está uma versão que para de testar
q
quandob
não a divide de maneira limpa. Além disso, a fim de testarb
's contraq
é revertida na suposição de que mais elevadosb
' s será mais difícil de dividir por (take2
,3
,4
por exemplo: se%2=0
,%4
poderia ser!0
. E vice-versa, não tanto ...).fonte
Axioma, 35 bytes
código de teste e resultados
Acabei de fazer a solução de Encontre o menor número inteiro positivo que tem todos os números inteiros de 1 a n como fatores você diz que é duplicado.
fonte
Pari / GP , 14 bytes
Experimente online!
fonte
8ª , 23 bytes
Código
Esse código deixa o pseudo-fatorial resultante no TOS
Uso e exemplo
Ou mais claramente
fonte