Le moltiplicazioni sono gratis

Partendo dal numero 1 (che ha costo 0), si possono ottenere tutti i numeri interi positivi sommando o moltiplicando due di quelli già ricavati. Al primo passo si può solo ricavare 2 (1+1); al secondo passo si può arrivare a 3 (1+2) e a 4 (2+2, oppure 2×2). C'è però un piccolo problema: mentre le moltiplicazioni sono gratis, ogni addizione ha costo 1. Pertanto il numero 2 ha costo 1, il numero 3 ha costo 2, mentre il numero 4 ha costo 1 (conviene fare la moltiplicazione e non l'addizione). Qual è il più piccolo numero che costa almeno 3? E il più piccolo che costa almeno 4?

   

   

Problema tratto dai Problem of the Week di Stan Wagon.