# 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) 2105·370·5126·7120, a number that is far larger than a googol (a mere 10100). (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 = 2a·3b·5c·7d
for suitable values of a, b, c, and d.

Consider the first criterion. Using the expression above for n, we can say:

n/2 = 2a-1·3b·5c·7d
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.