Smallest multiple

exercise No. 83

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:

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 = highestDivisor; 2 <= i; i--) {     // Higher values are more likely having a remainder
        atLeastOneRemainder = 0 != candidate % i;   // Continue outer while,
        if (atLeastOneRemainder) {                  // Is there a non-zero remainder?
            break;                                  // leave current for loop.
        }
    }
} while (atLeastOneRemainder);                      // Increase candidate further?

System.out.println(candidate);                      // Print final result

The assignment atLeastOneRemainder = 0 != candidate % i deserves an explanation. Additional braces help understanding the expression: 

atLeastOneRemainder = (0 != (candidate % i))
                         ↘          ↘   ↙
                           ↘         int
                             ↘       ↙
                              boolean

This is fully equivalent to the more explicit code: 

if (0 == (candidate % i)) {
   atLeastOneRemainder = false;
} else {
   atLeastOneRemainder = true;
}

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

exercise No. 84

Smallest multiple, purely algebraic solution

Q:

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

Tip

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

A:

We decompose each value within [2, 3, ...20] into its 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].

Prev  Up  Next
Guessing numbers  Home  Pythagorean triples