Lite

Rex and Ralph: Prime Clues

 Category: Math Submitted By: javaguru Fun: (2.4) Difficulty: (3.16)

Two mathematicians, Rex and Ralph, have an ongoing competition to stump each other. Frustrated that Ralph was able to so easily figure out his last question, Rex is certain this one won't be so easy. He tells Ralph he's thinking of a number.

"The numbers one less and one more than the number are both the product of five prime numbers. The three numbers together have thirteen prime factors, all different. The sum of the prime factors of the number is 1400."

"OK," says Ralph after a moment. "That's probably enough information to find the number with a brute-force search, is that what you expect me to do?"

"No, no, no," replies Rex. "I don't want you to do anything as inelegant as that. Here's some more information."

"The digital sum of each of the number's prime factors is prime, as is digital sum of the product of these sums. In fact, if you the reverse the digits in the product's digital sum you get a different prime number that is the digital sum of the number I'm thinking of."

Ralph takes out a pad of paper and starts jotting down some notes.

"The middle two digits in the number are its only prime digits and the number formed by the middle two digits is also prime. The number formed by the first three digits in the number is prime and its digital sum is also prime. In fact, the digital sum of the digital sum, and the digital sum of the digital sum of the digital sum of the first three numbers are also both prime."

"What number am I thinking of?" asks Rex.

Ralph jots down a few more notes and then does a couple of calculations on his calculator. He says, "OK, I know it's one of two numbers, but I don't want to factor these to figure out which one."

Rex frowns and says, "One of those numbers is divisible by 13."

Ralph smiles and tells Rex the number.

What were the two numbers and which one was the one Rex was thinking of?

Note: The "digital sum" is the sum of the digits in a number. For example, the digital sum of 247 = 2 + 4 + 7 = 13.

The two numbers Ralph finds are 443,794 and 887,314. Rex's number is 887,314.

887313 = 3 x 7 x 29 x 31 x 47
887314 = 2 x 487 x 911
887315 = 5 x 11 x 13 x 17 x 73

Here's how Ralph did it:

First, since the three adjacent numbers don't share any prime numbers, the middle number must be even, otherwise both the other numbers would have to be divisible by 2. If one of the factors in Rex's number is two, then the other two factors must add up to 1400 - 2 = 1398.

The maximum product of two numbers that add up to 1398 is 699 x 699, so the upper bound for Rex's number is 2 x 699 x 699 = 977,202.

The product of the first ten odd prime numbers is

3 x 5 x 7 x 11 x 13 x 17 x 19 x 23 x 29 x 31 = 100,280,245,065

This is the minimum value for the product of Rex's number minus one times Rex's number plus one. Therefore the square root of this number is the lower bound for Rex's number. The square root of 100,280,245,065 ~ 316,670. So now Ralph knows that Rex's number is an even number between 316,670 and 977,202. He figures this could be found by brute force given the other clues. (In fact, 887,314 is the only number in this range that is between two numbers with five or more unique prime factors, but Ralph doesn't know that.)

The digital sum of the prime factors of the number are prime numbers, one of which is 2. The other two must be prime numbers between 316,670 / 1,398 ~ 227 and 1,398. The maximum digital sum for numbers in this range is 3 x 9 = 27, so the maximum value for the product of the three prime digital sums is 2 x 23 x 23 = 1,058. The digital sum of this number is also prime. The maximum digital sum in this range is 27, so the digital sum of this product is a prime number less than 27.

The largest digital sum for a number in the range 316,670 to 977,202 is 6 x 9 = 54. This means that the digital sum of the number must be a prime number less than 54 that is a different prime number less than 27 when reversed. There are four prime numbers less than 54 that are a different prime number when reversed: 13, 17, 31 and 37. The digital sum of Rex's number must be 31.

The middle two digits are prime. For there to be a middle two digits, the number of digits in the number must be even. So now the upper bound for the number is 977,202. The number formed by the middle two digits must also be prime. There are only four two-digit prime numbers composed of prime digits: 23, 37, 53 and 73. The number formed by the first three digits is prime, so the third digit can't be 2 or 5. The middle two digits must be either 37 or 73.

Since the sum of the first three digits is a prime number, the sum must be one of 5, 7, 11, 13, 17, 19 or 23. Since the number must start with a 4, 6, 8 or 9, the minimum value for the first three digits is 403, which eliminates 5 as a digital sum. The digital sum of the digital sum of the first three digits must be prime, so it can't be 13, 17 or 19. This leaves 7, 11 or 23 as the digital sum of the first three digits.

Since the only possibility for the first three digits totaling 7 is 403, Ralph did a couple of quick calculations to determine that 403 = 13 x 31, so it isn't prime. So the digital sum of the first three digits must be either 11 or 23 and the digital sum of the last three digits must be 20 or 8.

There are only four ways to make a digital sum of 11 for the first three digits that ends in a three or seven and starts with 4, 6, 8 or 9: 407, 443, 623 and 803. Ralph does a couple more quick calculations and determines that 407 = 11 x 37, 623 = 7 x 89 and 803 = 11 x 73, but that 443 is prime. If 443 are the first three digits, then the last three digits must total 20, start with a 7 and end with a 4, 6 or 8. There is only three ways to do this: 758, 776 and 794. The fifth digit can't be prime, so only 794 is possible. This gives the first number 443,794.

If the first three digits total 23, start with a 4, 6, 8 or 9, and end with a 3 or 7, then the choices are 887 and 977. The second digit in 977 is prime, so the only choice is 887. Ralph checks and finds that 887 is prime. If the first three numbers are 887 then the last three must start with a 3, end with a 4, 6 or 8 and total 8. Only 314 is possible, giving the second number 887,314.

When Rex tells Ralph one of the numbers is divisible by 13, Ralph finds that 443,794 = 13 x 34,138. Since 13 can't be one of the prime factors of the number, the number must be 887,314.