algorithm - para - Encontrar el LCM de un rango de números
minimo comun multiplo y maximo comun divisor (13)
print "LCM of 4 and 5 = ".LCM(4,5)."/n";
sub LCM {
my ($a,$b) = @_;
my ($af,$bf) = (1,1); # The factors to apply to a & b
# Loop and increase until A times its factor equals B times its factor
while ($a*$af != $b*$bf) {
if ($a*$af>$b*$bf) {$bf++} else {$af++};
}
return $a*$af;
}
Leí hoy una interesante publicación de DailyWTF, "Fuera de todas las respuestas posibles ..." y me interesó lo suficiente como para desenterrar la publicación original del foro donde se envió. Esto me hizo pensar cómo iba a resolver este problema interesante: la pregunta original se plantea en Project Euler como:
2520 es el número más pequeño que se puede dividir por cada uno de los números del 1 al 10 sin ningún resto.
¿Cuál es el número más pequeño que es uniformemente divisible por todos los números del 1 al 20?
Para reformar esto como una pregunta de programación, ¿cómo crearías una función que pueda encontrar el mínimo común múltiplo para una lista arbitraria de números?
Soy increíblemente malo con la matemática pura, a pesar de mi interés en la programación, pero pude resolver esto después de un poco de búsqueda en Google y algo de experimentación. Tengo curiosidad por saber qué otros enfoques podrían tomar los usuarios. Si lo desea, publique algunos códigos a continuación, con suerte junto con una explicación. Tenga en cuenta que, aunque estoy seguro de que existen bibliotecas para calcular el GCD y el LCM en varios idiomas, estoy más interesado en algo que muestra la lógica más directamente que llamar a una función de biblioteca :-)
Estoy muy familiarizado con Python, C, C ++ y Perl, pero cualquier lenguaje que prefiera es bienvenido. Puntos de bonificación por explicar la lógica para otras personas con desafíos matemáticos como yo.
EDITAR : Después de enviar, encontré esta pregunta similar. Mínimo múltiplo común para 3 o más números pero fue respondido con el mismo código básico que ya descubrí y no hay una explicación real, así que sentí que esto era lo suficientemente diferente como para dejarlo abierto.
Al expandir el comentario de @ Alexander, señalaría que si puedes factorizar los números en sus números primos, eliminar duplicados, luego multiplicar, obtendrás tu respuesta.
Por ejemplo, 1-5 tienen los factores primos de 2,3,2,2,5. Elimine el ''2'' duplicado de la lista de factores del ''4'', y tiene 2,2,3,5. Multiplicarlos juntos rinde 60, que es tu respuesta.
El enlace de Wolfram proporcionado en el comentario anterior, http://mathworld.wolfram.com/LeastCommonMultiple.html entra en un enfoque mucho más formal, pero la versión corta está arriba.
Aclamaciones.
El LCM de uno o más números es el producto de todos los factores primos distintos en todos los números, cada primo a la potencia del máximo de todos los poderes a los que ese primo aparece en los números uno toma el LCM de.
Digamos 900 = 2 ^ 3 * 3 ^ 2 * 5 ^ 2, 26460 = 2 ^ 2 * 3 ^ 3 * 5 ^ 1 * 7 ^ 2. La potencia máxima de 2 es 3, la potencia máxima de 3 es 3, la potencia máxima de 5 es 1, la potencia máxima de 7 es 2 y la potencia máxima de cualquier primo superior es 0. Entonces, el LCM es: 264600 = 2 ^ 3 * 3 ^ 3 * 5 ^ 2 * 7 ^ 2.
Aquí está mi puñalada de Python:
#!/usr/bin/env python
from operator import mul
def factor(n):
factors = {}
i = 2
while i <= n and n != 1:
while n % i == 0:
try:
factors[i] += 1
except KeyError:
factors[i] = 1
n = n / i
i += 1
return factors
base = {}
for i in range(2, 2000):
for f, n in factor(i).items():
try:
base[f] = max(base[f], n)
except KeyError:
base[f] = n
print reduce(mul, [f**n for f, n in base.items()], 1)
El primer paso obtiene los factores primos de un número. El segundo paso construye una tabla hash de la cantidad máxima de veces que se vio cada factor, luego los multiplica todos juntos.
Un algoritmo en Haskell. Este es el lenguaje en el que pienso hoy en día para el pensamiento algorítmico. Esto puede parecer extraño, complicado y poco atractivo. ¡Bienvenido a Haskell!
primes :: (Integral a) => [a]
--implementation of primes is to be left for another day.
primeFactors :: (Integral a) => a -> [a]
primeFactors n = go n primes where
go n ps@(p : pt) =
if q < 1 then [] else
if r == 0 then p : go q ps else
go n pt
where (q, r) = quotRem n p
multiFactors :: (Integral a) => a -> [(a, Int)]
multiFactors n = [ (head xs, length xs) | xs <- group $ primeFactors $ n ]
multiProduct :: (Integral a) => [(a, Int)] -> a
multiProduct xs = product $ map (uncurry (^)) $ xs
mergeFactorsPairwise [] bs = bs
mergeFactorsPairwise as [] = as
mergeFactorsPairwise a@((an, am) : _) b@((bn, bm) : _) =
case compare an bn of
LT -> (head a) : mergeFactorsPairwise (tail a) b
GT -> (head b) : mergeFactorsPairwise a (tail b)
EQ -> (an, max am bm) : mergeFactorsPairwise (tail a) (tail b)
wideLCM :: (Integral a) => [a] -> a
wideLCM nums = multiProduct $ foldl mergeFactorsPairwise [] $ map multiFactors $ nums
La respuesta no requiere ningún juego de pies de lujo en términos de factoraje o poderes principales, y ciertamente no requiere el Tamiz de Eratóstenes.
En su lugar, debe calcular el LCM de un solo par calculando el GCD usando el algoritmo de Euclides (que NO requiere factorización, y de hecho es significativamente más rápido):
def lcm(a,b):
gcd, tmp = a,b
while tmp != 0:
gcd,tmp = tmp, gcd % tmp
return a*b/gcd
entonces puedes encontrar el LCM total reduciendo la matriz usando la función lcm () anterior:
reduce(lcm, range(1,21))
One-liner en Haskell.
wideLCM = foldl lcm 1
Esto es lo que utilicé para mi propio Proyecto Problema 5 de Euler.
Hay una solución rápida para esto, siempre y cuando el rango sea de 1 a N.
La observación clave es que si n (<N) tiene factorización prima p_1^a_1 * p_2^a_2 * ... p_k * a_k , entonces aportará exactamente los mismos factores al LCM que p_1^a_1 y p_2^a_2 .. p_k^a_k . Y cada uno de estos poderes también está en el rango de 1 a N. Por lo tanto, solo tenemos que considerar las potencias primarias puras más altas que N.
Por ejemplo, para 20 tenemos
2^4 = 16 < 20
3^2 = 9 < 20
5^1 = 5 < 20
7
11
13
17
19
Al multiplicar todas estas energías primarias juntas obtenemos el resultado requerido de
2*2*2*2*3*3*5*7*11*13*17*19 = 232792560
Entonces en pseudo código:
def lcm_upto(N):
total = 1;
foreach p in primes_less_than(N):
x=1;
while x*p <= N:
x=x*p;
total = total * x
return total
Ahora puede ajustar el ciclo interno para que funcione de manera ligeramente diferente para obtener más velocidad, y puede precalcular la función primes_less_than(N) .
EDITAR:
Debido a un reciente voto positivo decidí volver a visitar esto, para ver cómo fue la comparación de velocidad con los otros algoritmos enumerados.
El tiempo para el rango 1-160 con iteraciones de 10k, contra los métodos de Joe Beibers y Mark Ransoms es el siguiente:
Joes: 1.85s Marks: 3.26s Mina: 0.33s
Aquí hay un gráfico de log-log con los resultados hasta 300.
El código para mi prueba se puede encontrar aquí:
import timeit
def RangeLCM2(last):
factors = range(last+1)
result = 1
for n in range(last+1):
if factors[n] > 1:
result *= factors[n]
for j in range(2*n, last+1, n):
factors[j] /= factors[n]
return result
def lcm(a,b):
gcd, tmp = a,b
while tmp != 0:
gcd,tmp = tmp, gcd % tmp
return a*b/gcd
def EuclidLCM(last):
return reduce(lcm,range(1,last+1))
primes = [
2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
947, 953, 967, 971, 977, 983, 991, 997 ]
def FastRangeLCM(last):
total = 1
for p in primes:
if p>last:
break
x = 1
while x*p <= last:
x = x * p
total = total * x
return total
print RangeLCM2(20)
print EculidLCM(20)
print FastRangeLCM(20)
print timeit.Timer( ''RangeLCM2(20)'', "from __main__ import RangeLCM2").timeit(number=10000)
print timeit.Timer( ''EuclidLCM(20)'', "from __main__ import EuclidLCM" ).timeit(number=10000)
print timeit.Timer( ''FastRangeLCM(20)'', "from __main__ import FastRangeLCM" ).timeit(number=10000)
print timeit.Timer( ''RangeLCM2(40)'', "from __main__ import RangeLCM2").timeit(number=10000)
print timeit.Timer( ''EuclidLCM(40)'', "from __main__ import EuclidLCM" ).timeit(number=10000)
print timeit.Timer( ''FastRangeLCM(40)'', "from __main__ import FastRangeLCM" ).timeit(number=10000)
print timeit.Timer( ''RangeLCM2(60)'', "from __main__ import RangeLCM2").timeit(number=10000)
print timeit.Timer( ''EuclidLCM(60)'', "from __main__ import EuclidLCM" ).timeit(number=10000)
print timeit.Timer( ''FastRangeLCM(60)'', "from __main__ import FastRangeLCM" ).timeit(number=10000)
print timeit.Timer( ''RangeLCM2(80)'', "from __main__ import RangeLCM2").timeit(number=10000)
print timeit.Timer( ''EuclidLCM(80)'', "from __main__ import EuclidLCM" ).timeit(number=10000)
print timeit.Timer( ''FastRangeLCM(80)'', "from __main__ import FastRangeLCM" ).timeit(number=10000)
print timeit.Timer( ''RangeLCM2(100)'', "from __main__ import RangeLCM2").timeit(number=10000)
print timeit.Timer( ''EuclidLCM(100)'', "from __main__ import EuclidLCM" ).timeit(number=10000)
print timeit.Timer( ''FastRangeLCM(100)'', "from __main__ import FastRangeLCM" ).timeit(number=10000)
print timeit.Timer( ''RangeLCM2(120)'', "from __main__ import RangeLCM2").timeit(number=10000)
print timeit.Timer( ''EuclidLCM(120)'', "from __main__ import EuclidLCM" ).timeit(number=10000)
print timeit.Timer( ''FastRangeLCM(120)'', "from __main__ import FastRangeLCM" ).timeit(number=10000)
print timeit.Timer( ''RangeLCM2(140)'', "from __main__ import RangeLCM2").timeit(number=10000)
print timeit.Timer( ''EuclidLCM(140)'', "from __main__ import EuclidLCM" ).timeit(number=10000)
print timeit.Timer( ''FastRangeLCM(140)'', "from __main__ import FastRangeLCM" ).timeit(number=10000)
print timeit.Timer( ''RangeLCM2(160)'', "from __main__ import RangeLCM2").timeit(number=10000)
print timeit.Timer( ''EuclidLCM(160)'', "from __main__ import EuclidLCM" ).timeit(number=10000)
print timeit.Timer( ''FastRangeLCM(160)'', "from __main__ import FastRangeLCM" ).timeit(number=10000)
En Haskell:
listLCM xs = foldr (lcm) 1 xs
Que puede pasar una lista, por ejemplo:
*Main> listLCM [1..10]
2520
*Main> listLCM [1..2518]
266595767785593803705412270464676976610857635334657316692669925537787454299898002207461915073508683963382517039456477669596355816643394386272505301040799324518447104528530927421506143709593427822789725553843015805207718967822166927846212504932185912903133106741373264004097225277236671818323343067283663297403663465952182060840140577104161874701374415384744438137266768019899449317336711720217025025587401208623105738783129308128750455016347481252967252000274360749033444720740958140380022607152873903454009665680092965785710950056851148623283267844109400949097830399398928766093150813869944897207026562740359330773453263501671059198376156051049807365826551680239328345262351788257964260307551699951892369982392731547941790155541082267235224332660060039217194224518623199770191736740074323689475195782613618695976005218868557150389117325747888623795360149879033894667051583457539872594336939497053549704686823966843769912686273810907202177232140876251886218209049469761186661055766628477277347438364188994340512556761831159033404181677107900519850780882430019800537370374545134183233280000
Esta es probablemente la respuesta más limpia y más corta (tanto en términos de líneas de código) que he visto hasta ahora.
def gcd(a,b): return b and gcd(b, a % b) or a
def lcm(a,b): return a * b / gcd(a,b)
n = 1
for i in xrange(1, 21):
n = lcm(n, i)
Aquí está mi solución javascript, espero que les resulte fácil de seguir:
function smallestCommons(arr) {
var min = Math.min(arr[0], arr[1]);
var max = Math.max(arr[0], arr[1]);
var smallestCommon = min * max;
var doneCalc = 0;
while (doneCalc === 0) {
for (var i = min; i <= max; i++) {
if (smallestCommon % i !== 0) {
smallestCommon += max;
doneCalc = 0;
break;
}
else {
doneCalc = 1;
}
}
}
return smallestCommon;
}
Este problema es interesante porque no requiere que encuentre el LCM de un conjunto arbitrario de números, se le da un rango consecutivo. Puede usar una variación del Tamiz de Eratóstenes para encontrar la respuesta.
def RangeLCM(first, last):
factors = range(first, last+1)
for i in range(0, len(factors)):
if factors[i] != 1:
n = first + i
for j in range(2*n, last+1, n):
factors[j-first] = factors[j-first] / factors[i]
return reduce(lambda a,b: a*b, factors, 1)
Editar: Un voto positivo reciente me hizo volver a examinar esta respuesta que tiene más de 3 años. Mi primera observación es que hoy lo habría escrito un poco diferente, usando enumerate por ejemplo.
La segunda observación es que este algoritmo solo funciona si el inicio del rango es 2 o menos, porque no intenta separar los factores comunes por debajo del inicio del rango. Por ejemplo, RangeLCM (10, 12) devuelve 1320 en lugar de los 660 correctos.
La tercera observación es que nadie intentó sincronizar esta respuesta con ninguna otra respuesta. Mi instinto me decía que esto mejoraría con respecto a una solución LCM de fuerza bruta a medida que aumentaba el alcance. Las pruebas probaron que mi instinto era correcto, al menos esta vez.
Como el algoritmo no funciona para rangos arbitrarios, lo reescribí para suponer que el rango comienza en 1. Eliminé la llamada para reduce al final, ya que era más fácil calcular el resultado a medida que se generaban los factores. Creo que la nueva versión de la función es más correcta y más fácil de entender.
def RangeLCM2(last):
factors = range(last+1)
result = 1
for n in range(last+1):
if factors[n] > 1:
result *= factors[n]
for j in range(2*n, last+1, n):
factors[j] /= factors[n]
return result
Aquí hay algunas comparaciones de tiempo contra el original y la solución propuesta por Joe Bebel que se llama RangeEuclid en mis pruebas.
>>> t=timeit.timeit
>>> t(''RangeLCM.RangeLCM(1, 20)'', ''import RangeLCM'')
17.999292996735676
>>> t(''RangeLCM.RangeEuclid(1, 20)'', ''import RangeLCM'')
11.199833288867922
>>> t(''RangeLCM.RangeLCM2(20)'', ''import RangeLCM'')
14.256165588084514
>>> t(''RangeLCM.RangeLCM(1, 100)'', ''import RangeLCM'')
93.34979585394194
>>> t(''RangeLCM.RangeEuclid(1, 100)'', ''import RangeLCM'')
109.25695507389901
>>> t(''RangeLCM.RangeLCM2(100)'', ''import RangeLCM'')
66.09684505991709
Para el rango de 1 a 20 dado en la pregunta, el algoritmo de Euclid supera tanto mi respuesta anterior como la nueva. Para el rango de 1 a 100, puede ver el avance del algoritmo basado en tamiz, especialmente la versión optimizada.
Aquí está mi respuesta en JavaScript. Primero me acerqué a esto desde primos, y desarrollé una función agradable de código reutilizable para encontrar primos y también para encontrar factores primos, pero al final decidí que este enfoque era más simple.
No hay nada único en mi respuesta que no esté publicado anteriormente, es solo en Javascript que no vi específicamente.
//least common multipe of a range of numbers
function smallestCommons(arr) {
arr = arr.sort();
var scm = 1;
for (var i = arr[0]; i<=arr[1]; i+=1) {
scm = scd(scm, i);
}
return scm;
}
//smallest common denominator of two numbers (scd)
function scd (a,b) {
return a*b/gcd(a,b);
}
//greatest common denominator of two numbers (gcd)
function gcd(a, b) {
if (b === 0) {
return a;
} else {
return gcd(b, a%b);
}
}
smallestCommons([1,20]);