A Powerfully Nice View Mystery Cache

This cache has been archived.

MathGen: There is too much trouble with this placement.

More
Hidden : 2/15/2008
Difficulty:
4 out of 5
Terrain:
3 out of 5

Size: Size: small (small)

Join now to view geocache location details. It's free!

Watch

How Geocaching Works
Looking for a different adventure?

Please note Use of geocaching.com services is subject to the terms and conditions in our disclaimer.

Geocache Description:

THIS CACHE IS NOT LOCATED AT THE POSTED COORDINATES. Instead it is located at a spot with a stunning view of both downtown San Francisco and the Briones/East Bay Area. To find the actual coordinates you need to solve the math problem below. Here is a photo taken from a spot near the cache site, looking to the east: Photo.

The coordinates of this cache are: N37 53.ABC W122 14.DEF (not 54.ABC and 15.DEF), where

ABC are the last three digits of 67^55 (a 101-digit number).
DEF are the last three digits of 13^99 (a 111-digit number).

(Here a^b here means power, i.e., 5^3 = 5 x 5 x 5 = 125). DON'T PANIC. You don't really need to do arithmetic on 100-digit numbers. It is possible to do this by hand, just using a pocket calculator. The basic "trick" is known as the "binary algorithm for exponentiation", and was known to the ancient Greeks. It is best illustrated by the following example:

Suppose you are given the problem of finding the last digit of 3^13. There are three ways to do this problem:

Solution 1: 3x3x3x3x3x3x3x3x3x3x3x3x3 = 1594323, so the answer is "3".

Solution 2: Note that 3^4 and 3^8 are easy to calculate, since we can do each by repeated squaring: 3^4 = (3^2)^2 = 81, and 3^8 = ((3^2)^2)^2 = 6561. Thus we can write 3^13 = 3^8 x 3^4 x 3^1 = 6561 x 81 x 3 = 1594323. This obtains the answer in only 7 multiplications instead of 13 (with much greater savings for large exponents). This "trick" depends on writing the exponent 13 as a sum of powers of two: 13 = 8 + 4 + 1. We can do this for any exponent. The first few powers of two are 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024...

Solution 3: In addition to what we did in Solution 2, note that since we are only interested in the last digit of the result, it suffices to take only the last digit after each multiplication, so that we can write 3^2 = 9 (take 9); 9^2 = 81 (take 1); 1^2 = 1 (take 1); thus the last digit of 3^8 is 1. Similarly, the last digit of 3^4 is 1. Putting these results together we can write that the last digit of 3^13 = (3^8 x 3^4 x 3^1) is the same as the last digit of 1 x 1 x 3 = 3. You can literally do this in your head. Similarly, if one takes the last two digits, or the last three, after each multiplication, one can obtain, in the end, the last two or three digits of the result.

In mathematical terms, by taking the last digit after each operation, we are performing arithmetic "mod 10". Taking the last two digits is equivalent to performing arithmetic "mod 100", and taking the last three digits is performing arithmetic "mod 1000". In the original problem stated above, you need to do multiplications mod 1000 (i.e, taking the last three digits), by following the procedure as outlined in Solutions 2 and 3. Once you understand the procedure, you should be able to find both ABC and DEF in just a minute or two, armed with nothing more than a pocket calculator and a sheet of paper. Check your work carefully for errors.

You can check your answers for this puzzle on Geochecker.com.

Additional Hints (Decrypt)

N cvar pbar, haqre n cvyr bs ebpxf, va n ohfu nobhg 40 sg sebz gur pvepyr.

Decryption Key

A|B|C|D|E|F|G|H|I|J|K|L|M
-------------------------
N|O|P|Q|R|S|T|U|V|W|X|Y|Z

(letter above equals below, and vice versa)


Attributes

No attributes available

Advertising with Us