P5
projecteuler.net

Smallest Multiple

ℹ️Published on Friday, 30th November 2001, 06:00 pm; Solved by 522159;
Difficulty rating: 5%

$2520$ is the smallest number that can be divided by each of the numbers from $1$ to $10$ without any remainder.

What is the smallest positive number that is evenly divisibledivisible with no remainder by all of the numbers from $1$ to $20$?



Soluzione

Questo si può fare in realtà tranquillamente su carta. Questo numero target \(n\) vogliamo che sia divisibile per ogni numero da 1 a 20, ma se ad esempio è divisibile per 8 di sicuro sarà divisibile anche per 2 e 4. L'idea è quindi di filtrare i fattori più "vincolanti", ovvero quelli che necessariamente dovremo prendere rispetto invece ad altri che verranno implicati. Un altro esempio, se prendiamo un multiplo di 2 e 5 allora possiamo ignorare 10, dato che sarà implicato.
Ragionando in questo modo si arriva a questo schema, che contiene i singoli fattori candidati, da 1 a 20 (partendo dall'alto per prendere subito quelli più vincolanti), seguiti da un commento e da quelli che via via ci salviamo.

\[ \begin{array}{lll} 19 & \text{manca} & \implies 19 \\ 18 = 3^2 \cdot 2 & \text{mancano} & \implies 19, 3^2, 2 \\ 17 & \text{manca} & \implies 19, 17, 3^2, 2 \\ 16 = 2^4 & \text{aggiorniamo l'esponente del 2} & \implies 19, 17, 3^2, 2^4 \\ 15 = 3\cdot 5 & \text{manca il 5} & \implies 19, 17, 3^2, 2^4, 5 \\ 14 = 2\cdot 7 & \text{manca il 7} & \implies 19, 17, 7, 3^2, 2^4, 5 \\ 13 & \text{manca} & \implies 19, 17, 13, 7, 3^2, 2^4, 5 \\ 12 = 2^2 \cdot 3 & \text{c'è già tutto} & \\ 11 & \text{manca} & \implies 19, 17, 13, 11, 7, 3^2, 2^4, 5 \\ 10 = 2 \cdot 5 & \text{c'è già tutto} & \implies 19, 17, 13, 11, 7, 3^2, 2^4, 5 \\ 9 = 3^2 & \text{c'è già tutto} & \\ 8 = 2^3 & \text{c'è già tutto} & \\ 7 & \text{c'è già tutto} & \\ 6 & \text{c'è già tutto} & \\ 5 & \text{c'è già tutto} & \\ 4 & \text{c'è già tutto} & \\ 3 & \text{c'è già tutto} & \\ 2 & \text{c'è già tutto} & \\ \end{array} \]

Quindi la risposta è \( n = 19\cdot 17\cdot 13\cdot 11\cdot 7\cdot5\cdot 3^2\cdot 2^4 \) ovvero

19 * 17 * 13 * 11 * 7 * 5 * 3^2 * 2^4
232792560

Last modified: March 18, 2026. Website built with Franklin.jl and the lovely Julia programming language.