DarCas Sandbox

Leggendo un articolo ho raccolto una sfida, quella di realizzare un algoritmo capace di fare la somma dei multipli di un numero in una serie.

Per intenderci, di una serie tipo: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10; la somma dei multipli di 3 è uguale a: 3 + 6 + 9 e cioè 18.

In realtà, mi ha incuriosito questa funzione perché ad occhio mi sembra una specializzazione, una delle tante, della funzione che ho derivato e di cui ho parlato in questo articolo.

Come sempre faccio mi sono messo a giocare con i numeri ed è venuta fuori una curiosa proprietà.

Se prendo prendo tanti numeri dall’inizio, quanti sono i multipli, e li moltiplico per il numero richiesto, ho lo stesso risultato di quando sommo tra loro tutti i multipli. Volendo tradurre in algebra questo concetto che potrebbe sembrare contorto abbiamo che: (1+2+3) * 3 = 18 che è esattamente lo stesso risultato di prima.

Quindi siamo di fronte alla soluzione del problema. Ora non ci resta che astrarre il tutto in modo da renderlo funzionale in qualsiasi caso.

Un multiplo è anche un numero che è divisibile per un altro. 10 diviso 3 è uguale a 3,3 (periodico). Tuttavia questo risultato ci dice che nella serie da 1 a 10 ci sono almeno 3 multipli. Quindi, dividendo il valore massimo della serie, per il multiplo – ed ignorando i decimali – so con certezza quanti multipli sono presenti nella serie.

Quindi, il primo step è eseguire l’operazione (nel caso della nostra serie): 10 div 3. Di questa operazione prendiamo solo la parte intera del risultato e cioè 3.

Il risultato di questa operazione la diamo in pasto alla funzione N*(N+1)/2. Per cui avremo 3*4/2 e cioè 6.

A questo punto non dobbiamo far altro che moltiplicare quest’ultimo risultato per il multiplo cioè 3 ed avremo il 18 che speravamo di ottenere.

Ovviamente invece che del 3, possiamo trovare i multipli di qualsiasi altro numero, il 5, il 7 eccetera.

L’articolo da cui ho raccolto la sfida chiedeva anche di sommare i multipli sia di 3 che di 5. Ovviamente nel fare questo bisogna tener conto degli eventuali multipli in comune tra i due. Nella serie da 1 a 10 non ci sono. Ma in quella da 1 a 20 c’è, ed è il 15. Per fare questo ci vuole un piccolo trucchetto (al momento non sono in grado di elaborare una funzione unica che riesca a fare questo).

Basta moltiplicare tra loro i due numeri multipli che si intendono trovare. Dopo di che si sommano tutti i multipli del nuovo numero sulla serie che siamo analizzando. Il risultato lo si sottrae alla somma dei multipli dell’uno e dell’altro multiplo iniziale.

Traduco: immaginiamo di voler calcolare la somma dei multipli di 3 e 5 della seria da 1 a 20. Dobbiamo sommare quindi 3 + 5 + 6 + 9 + 10 + 12 + 15 + 18 + 20 che è uguale a 98.

Basta fare:

20 div 3 = 6; 6*7/2 = 21; 21*3 = 63
20 div 5 = 4; 4*5/2 = 10; 10*5 = 50
20 div 15 = 1; 1*2/2 = 1; 1*15 = 15

63+50-15 = 98.

Chiaro? Ovviamente il tutto funziona anche nel caso del problema indicato dall’articolo: Sommare i multipli di 3 e 5 di una serie da 1 a 1000.

1000 div 3 = 333; 333*334/2 = 55611; 55611*3 = 166833
1000 div 5 = 200; 200*201/2 = 20100; 20100*5 = 100500
1000 div 15 = 66; 66*67/2 = 2211; 2211*15 = 33165

166833+100500-33165 = 234168 (tra l’altro mi sa che l’autore ha fatto uno sbaglio).

Tradurre tutto questo in software, come sempre è semplicissimo, arrivati a questo punto.