Умно­же­ние на число об­ра­ти­мо не для лю­бо­го числа, по­это­му, если мы пойдём от числа 629 к числу 19, тогда од­но­знач­но вос­ста­но­вим про­грам­му с ми­ни­маль­ным чис­лом ко­манд. По­лу­чен­ные ко­ман­ды будут за­пи­сы­вать­ся спра­ва на­ле­во.

1)  Число 629 не де­лит­ся на 2, зна­чит, оно по­лу­че­но при­бав­ле­ни­ем еди­ни­цы к числу 628: 629 = 628 + 1 (ко­ман­да 1).

2)  Т. к. мы хотим по­лу­чить ми­ни­маль­ное число ко­манд, то для по­лу­че­ния числа 628 нужно ис­поль­зо­вать умно­же­ние: 628 = 314 * 2 (ко­ман­да 2).

Далее, если число чётное, при­ме­ня­ем рас­суж­де­ние 2), если нечётное  — рас­суж­де­ние 1), по­это­му:

314 = 157 * 2 (ко­ман­да 2);

157 = 156 + 1 (ко­ман­да 1);

156 = 78 * 2 (ко­ман­да 2);

78 = 39 * 2 (ко­ман­да 2);

39 = 38 + 1 (ко­ман­да 1);

38 = 19 * 2 (ко­ман­да 2).

Счи­та­ем ко­ли­че­ство ко­манд и по­лу­ча­ем ответ: 8.