Smallest multiple

exercise No. 80

Q:

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

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Tip

The remainder operator % allows for testing whether a given integer value n can be divided by an another integer value k without remainder.

Increment an integer candidate in a loop till the desired condition is being fulfilled.

A:

We propose the following solution:

   public static void main(String[] args) {

      final int highestDivisor = 20;             // May be adjusted to other limits.

      int candidate = highestDivisor;            // start with highest divisor.

      boolean atLeastOneRemainder;

      do {
         candidate++;                            // next candidate value.
         atLeastOneRemainder = false;

         for (int i = 2; i <= highestDivisor; i++) {
            if (0 != candidate % i) {            // Is there a non-zero remainder?
               atLeastOneRemainder = true;       // Continue outer while.
               break;                            // Leave current for loop.
            }
         }

      } while (atLeastOneRemainder);             // Increase candidate further?

      System.out.println(candidate);
   }

Executing this code results in a value of 232792560 for the smallest desired value.

exercise No. 81

Smallest multiple, purely algebraic solution Create comment in forum

Q:

Solving the previous exercise by a program is quite a no-brainer (from a software developer's point of view). Provide a different solution purely based on algebraic considerations. In other words: Your solution should work by using paper and pencil exclusively.

Tip

Consider the underlying prime factors of all values from [2, 3, ...20].

A:

We decompose each value within [2, 3, ...20] into prime factors:

Value Contributing prime factors
2 3 5 7 11 13 17 19
2 2
3 3
4 2 2
5 5
6 2 3
7 7
8 2 2 2
9 3 3
10 2 5
11 11
12 2 2 3
13 13
14 2 7
15 3 5
16 2 2 2 2
17 17
18 2 3 3
19 19
20 2 2 5

As expected we find an identical value for the desired smallest integer value of 2*2*2*2*3*3*5*7*11*13*17*19 = 232792560 which is the least common multiple of [2, 3, ...20].