Numberphile has a nice video on the fifth root trick: someone raises a two-digit number to the 5th power, reads the number aloud, and you tell them immediately what the number was.
Here’s the trick in a nutshell. For any number n, n^{5} ends in the same last digit as n. You could prove that by brute force or by Euler’s theorem. So when someone tells you n^{5}, you immediately know the last digit. Now you need to find the first digit, and you can do that by learning, approximately, the powers (10k)^{5} for i = 1, 2, 3, …, 9. Then you can determine the first digit by the range.
Here’s where the video is a little vague. It says that you don’t need to know the powers of 10k very accurately. This is true, but just how accurately do you need to know the ranges?
If the two-digit number is a power of 10, you’ll recognize the zeros at the end, and the last non-zero digit is the first digit of n. For example, if n^{5} = 777,600,000 then you know n is a multiple of 10, and since the last non-zero digit is 6, n = 60.
So you need to know the fifth powers of multiples of 10 well enough to distinguish (10k – 1)^{5} from (10k + 1)^{5}. The following table shows what these numbers are.
|---+---------------+---------------| | k | (10k - 1)^5 | (10k + 1)^5 | |---+---------------+---------------| | 1 | 59,049 | 161,051 | | 2 | 2,476,099 | 4,084,101 | | 3 | 20,511,149 | 28,629,151 | | 4 | 90,224,199 | 115,856,201 | | 5 | 282,475,249 | 345,025,251 | | 6 | 714,924,299 | 844,596,301 | | 7 | 1,564,031,349 | 1,804,229,351 | | 8 | 3,077,056,399 | 3,486,784,401 | | 9 | 5,584,059,449 | 6,240,321,451 | |---+---------------+---------------|
So any number less than a million has first digit 1. Any number between 1 million and 3 million has first digit 2. Etc.
You could choose the following boundaries, if you like.
|---+----------------| | k | upper boundary | |---+----------------| | 1 | 1,000,000 | | 2 | 3,000,000 | | 3 | 25,000,000 | | 4 | 100,000,000 | | 5 | 300,000,000 | | 6 | 800,000,000 | | 7 | 1,700,000,000 | | 8 | 3,200,000,000 | | 9 | 6,000,000,000 | |---+----------------|
The Numberphile video says you should have someone say the number aloud, in words. So as soon as you hear “six billion …”, you know the first digit of n is 9. If you hear “five billion” or “four billion” you know the first digit is 8. If you hear “three billion” then you know to pay attention to the next number, to decide whether the first digit is 7 or 8. Once you hear the first few syllables of the number, you can stop pay attention until you hear the last syllable or two.
Roman K. once helped to maintain a company website that served a large customer base mainly within the United Kingdom. Each customer was itself a business offering a range of services. The website displayed these businesses on a map so that potential customers could find them. This was done by geocoding the business' addresses to get their longitude and latitude coordinates, then creating points on the map at those locations.
Simple enough—except that over time, some of the businesses began creeping west through the Atlantic Ocean, toward the east coast of North America.
Roman had no idea where to start with troubleshooting. It was only happening with a subset of businesses, and only intermittently. He was certain the initial geocoded coordinates were correct. Those longitude and latitude values were stored in a database table of customer data with strict permissions in place. Even if he wanted to change them himself, he couldn't. Whatever the problem was, it was powerful, and oddly selective: it only ever changed longitude values. Latitude values were never touched.
Were they being hacked by their competitors? Were their customers migrating west en masse? Were goblins messing with the database every night when no one was looking?
Roman dug through reams of code and log files, searching desperately for any whiff of "longitude." He questioned his fellow developers. He blamed his fellow developers. It was all for naught, for the problem was no bug or hack. The problem was a "feature" of the database access layer. Roman discovered that the user class had a simple destructor method that saved all the currently loaded data back to the database:
function __destruct() {
if ($this->_changed) {
$this->database->update('customer_table', $this->_user_data, array('customer_id' => $this->_user_data['customer_id']));
}
}
The legwork was handled by a method called update()
. And just what did update()
do?
public function update($table, $record, $where = '') {
// snip
foreach ($record as $field => $value) {
if (isset($value[0]) && is_numeric($number) && ($value[0] == '+' || $value[0] == '-')) {
$set[] = "`$field` = `$field` {$value[0]} ".$number;
}
}
}
Each time a customer logged into their account via the website and changed their data: if any of their data began with either a plus or minus sign, those values would have some mysterious value (contained in the variable $number
) either added to or subtracted from them. Say a customer's business happened to be located west of the prime meridian. Their longitude would therefore be stored as a negative value, like -3. The next time that customer logged in and changed anything, the update()
method would subtract $number
from -3, relocating the customer to prime oceanic property. Latitude was never affected because latitude coordinates above the equator are positive. These coordinate values were simply stored as-is, with no sign in front of them.
There was no documentation for the database access layer. The developer responsible for it was long gone. As such, Roman never did learn whether there were some legitimate business reason for this "feature" to exist. He added a flag to the update()
method so that customers could disable the behavior upon request. Ever since, the affected companies have remained safely anchored upon UK soil.
Recently, Mark Dominus wrote about trying to memorize all the prime numbers under . This is a cool idea, but it made me start thinking about alternative: instead of memorizing primes, could we memorize a procedure for determining whether a number under is prime or composite? And can we make it clever enough to be done relatively quickly? This does tie into my other recent posts about primality testing, but to be clear, it’s also quite different: I am not talking about a general method for determining primality, but the fastest method we can devise for mentally determining, by hook or by crook, whether a given number under is prime. Hopefully there are rules we can come up with which are valid for numbers less than —and thus make them easier to test—even though they aren’t valid for bigger numbers in general.
As a warmup, today I’ll write about how I determine whether a number less than 100 is prime: I don’t have them memorized, but can very quickly decide whether such a number is prime or not—and you can, too! This is a situation where doing a little mathematical analysis beforehand goes a long way.
Since , every composite number less than has at least one factor which is less than . This means that every composite less than is divisible by , , , or . Multiples of 2, 3, and 5 are relatively easy to recognize, and as we’ll see, is not hard to deal with either.
Any even number or multiple of 5 (i.e. numbers ending with an even number or with a 5) is clearly composite. (Other than 2 and 5 themselves, of course.)
Multiples of are composite. There are many numbers which I think of as “obvious” multiples of three: 9, 21, 27, and 33 because I have had their factorizations memorized since third grade; 81 because it’s a power of three so I have it memorized too; and 39, 63, 69, 93, and 99 because they consist of two digits each of which is a multiple of three. As you probably know, there is also a simple test for determining divisibility by three: just add the digits and see whether the result is divisible by three. This test identifies a few more “nonobvious” multiples of three which you might otherwise think are prime: , , and .
What’s left? There are only three numbers less than 100 which are composite and not divisible by 2, 3, or 5:
So, to sum up, faced with a number less than 100 that I want to test for primality, I can quickly rule it out if it is divisible by 2, 3, or 5, or if it is a multiple of 7 I recognize (49, 77, or 91). And that’s it! Anything else has to be prime.
In a future post I plan to write about how feasible it is to come up with a similar procedure to identify all primes under 1000.