# Puzzle of the Week for 5 April 1999: Solution

The smallest integer that satisfies all of the criteria is 308,051,071,072,-
023,814,772,744,512,305,619,601,673,927,548,514,737,917,843,576,685,084,811,-
194,204,788,667,429,616,593,108,641,919,623,102,245,023,637,108,933,835,699,-
072,653,698,444,366,455,078,125,000,000,000,000,000,000,000,000,000,000,000,-
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,-
000,000,000,000,000, or (more concisely)
2^{105}·3^{70}·5^{126}·7^{120},
a number that is far larger than a googol (a mere 10^{100}).
(By the way, why does this number end with so many zeroes?)

To prove that this answer is correct, we must first recognize that any
solution must have prime factors of 2, 3, 5, and 7 (otherwise the divisions
specified in the puzzle would not yield integer results). Any larger prime
factors can be shown to be unnecessary and will just yield larger values for
**n**. Hence we can say that

**n = 2**^{a}·3^{b}·5^{c}·7^{d}

for suitable values of **a, b, c,** and **d**.
Consider the first criterion. Using the expression above for
**n**, we can say:

**n/2 = 2**^{a-1}·3^{b}·5^{c}·7^{d}

If **n/2** is a square, we know that **a-1, b, c,** and **d**
must be even (see the hints). Similar
reasoning implies that if **n/3** is a cube, then **a, b-1, c,**
and **d** must be multiples of three. If **n/5** is a fifth
power, then **a, b, c-1,** and **d** must be multiples of five,
and if **n/7** is a seventh power, then **a, b, c,** and
**d-1** must be multiples of seven.
Now consider all of our deductions regarding **a**: it must be
odd (if **a-1** is even), and a multiple of 3, 5, and 7. The
smallest value for **a** must be therefore be 3·5·7,
or 105.

Following the same type of reasoning, we see that **b** must be
a multiple of 2, 5, and 7, and one more than a multiple of 3. The
smallest multiple of 2, 5, and 7 (70) has the desired characteristic
of being one more than a multiple of 3, so **b** = 70.

Continuing, **c** is a multiple of 2, 3, and 7, and one more than
a multiple of 5. In this case, 2·3·7 = 42
is two more than a multiple of 5; twice this (84) is four more than a
multiple of 5, but 3·42 = 126 is one greater than a multiple of
5, so **c** = 126.

Finally, we see that **d** is a multiple of 2, 3, and 5 and one
more than a multiple of 7; 2·3·5 = 30, and the first
multiple of 30 that is one more than a multiple of 7 is 4 · 30
= 120 (7·17 + 1), so we have **d** = 120. Putting all of
these deductions together, we obtain the result at the top of this
page.

The calculation of the result in long form (308,051,...) was performed
in less than a tenth of a second by a program named `bc` (basic
calculator), which (unlike most calculators) computes with arbitrary
precision, using the same methods we use for pencil and paper
arithmetic (except for the little bits of ground-up eraser that always
end up all over the paper). The original version of `bc` was
written at Bell Labs for Unix. The PCs in the library can run
`bc` under Linux.

## Links