lcm – minimo comune multiplo

Tutto è nato da qui: Qual è Il Più Piccolo Numero? [Per I Giochi Matematici].

Certe prof…
Che poi Annarita è coautrice del blog, l’altro blog.
E vi assicuro che è brava, rockz 😀

Allora il problema è:

Un numero intero maggiore di 2 lascia un resto di 2 quando è diviso da ciascuno dei seguenti numeri: 3, 4, 5 e 6. Qual è il più piccolo numero che abbia tali caratteristiche?

I ragazzi, alcuni allievi, altri no, hanno risposto esattamente, bravi 😀
Nessuno però ha riportato la prima cosa che ho pensato io: quel numero deve essere modulo 2 per ognuno dei numeri dati, quindi dev’essere 2 più dell’mcm (minimo comune multiplo, ai miei tempi si scriveva così, spero sia ancora valido).

Il passo successivo è stato –prima di subito– pensare di automatizzare la soluzione per qualunque lista di numeri. Usando il ‘puter, certo.
Tra tutti i linguaggi di programmazione ho pensato a Python perché molto conosciuto, facile, potente, sexy, … Insomma io consiglio Python per quasi tutto, anche per questo.
Dunque minimo comune multiplo in inglese si dice least common multiple e allora cerco nella documentazione online; probabilmente la funzione si chiamerà lcm, come per l’MCD (si scrive così, vero) si chiama gcd per greatest common divisor.

Non l’ho trovata! Panico? No, niente panico! c’è scritto anche sulla copertina della Guida Galattica 😀

Si può fare, mi son detto, che sarà mai…
Ma mi sono accorto subito che sì, è fattibile ma viene lunga, vediamo se qualcuno ha avuto un’idea migliore, il Web è pieno di geeks.
In questi casi la cosa migliore è Stack Overflow e difatti ecco qua: Least common multiple for 3 or more numbers.

Ho imparato da tempo che conviene leggere fino in fondo, difatti ecco che c’è scritto “[…] Here’s one:  enrico-franchi.org/2010/09/nice-functional-lcm-in-python.html”

OK, quello che cercavo, bravo Enrico 🙂

Allora, si ha:

#!/usr/bin/python
# -*- coding: utf-8 -*-

import sys
from fractions import gcd

def lcm(numbers):
    return reduce(lambda x, y: (x * y) / gcd(x, y), numbers, 1)

numeri = sys.argv[1:]

for n in range(len(numeri)):
	numeri[n] = int(numeri[n])

print numeri
LCM = lcm(numeri)
print LCM

La funzione di Enrico fa tutto lei, basta passargli la lista degli argomenti, togliendo il primo (quello con indice 0 che contiene il nome dello script). Ah sì, gli argomenti sono stringhe e vanno trasformati in interi. Tutto qui.

Ma aspetta un attimino: non hai raccontato di SymPy recentemente?
Sì, vediamo: Computes integer least common multiple of two numbers.
OK, per due numeri. Quindi diventa:

#!/usr/bin/python
# -*- coding: utf-8 -*-

import sys
from sympy import ilcm

numeri = sys.argv[1:]

for n in range(len(numeri)):
	numeri[n] = int(numeri[n])

print numeri
LCM = reduce(ilcm, numeri)
print LCM

In ogni caso per una lista di numeri bisogna usare reduce(). Che è una di quelle cose che all’inizio uno si chiede a cosa serva, come lambda (che c’è nella versione di Enrico).

Allora reduce, lo cerchiamo sulla guida online:

reduce(function, iterable[, initializer])

Applica function di due argomenti cumulativamente agli elementi di iterable, da sinistra a destra, in modo da ridurre l’iterabile a un solo valore. Per esempio, reduce(lambda(x, y: x+y, [1, 2, 3, 4, 5]) calcola ((((1+2)+3)+4)+5).

OK, caso chiuso, per Python.
Ma per gli altri linguaggi?
Calma, prossimamente: Ankh-Morpork non è stata costruita in un giorno 😉