Pseudo-prime

1729 Not a Dull Number

/ ivasallay / Leave a comment

Today’s Puzzle:

A little more than a hundred years ago near Cambridge University G. H. Hardy took a taxi to visit his young friend and fellow mathematician, Srinivasa Ramanujan, in the hospital. Hardy couldn’t think of anything interesting about his taxi number, 1729, and remarked to Ramanujan that it appeared to be a rather dull number. But even the reason for his hospitalization could not prevent Ramanujan’s genius from shining through. He immediately recognized 1729’s unique and very interesting attribute: it is the SMALLEST number that can be written as the sum of two cubes in two different ways! Indeed,
12³ + 1³ = 1729, and
10³ + 9³ = 1729.

Today’s puzzle looks a little bit like a modern-day American taxi cab with the clues 17 and 29 at the top of the cab. The table below the puzzle contains all the Pythagorean triples with hypotenuses less than 100 sorted by legs and by hypotenuses. Use the table and logic to write the missing sides of the triangles in the puzzle. The right angle on each triangle is the only one that is marked. Obviously, none of the triangles are drawn to scale. No Pythagorean triple will appear more than once in the puzzle.

Sorted TriplesHere’s the same puzzle without all the added color:

Print the puzzles or type the solutions in this excel file: 10 Factors 1721-1729.

What taxi cab might Hardy have tried to catch next? He might have had to wait a long time for it, 4104.
16³ + 2³ = 4104, and
15³ + 9³ = 4104.

Factors of 1729:

  • 1729 is a composite number.
  • Prime factorization: 1729 = 7 × 13 × 19.
  • 1729 has no exponents greater than 1 in its prime factorization, so √1729 cannot be simplified.
  • The exponents in the prime factorization are 1, 1, and 1. Adding one to each exponent and multiplying we get (1 + 1)(1 + 1)(1 + 1) = 2 × 2 × 2 = 8. Therefore 1729 has exactly 8 factors.
  • The factors of 1729 are outlined with their factor pair partners in the graphic below.

More About the Number 1729:

Did you notice these cool-looking factor pairs?
19 · 91 = 1729.
13 · 133 = 1729.

1729 is the hypotenuse of a Pythagorean triple:
665-1596-1729 which is 133 times (5-12-13).

1729 is the difference of two squares in four different ways:
865² – 864² = 1729,
127² – 120² = 1729,
73² – 60² = 1729, and
55² – 36² = 1729.

1729 is also a pseudoprime number! For example, even though it is a composite number, it passes the quick prime number test I first wrote about in 341 is the smallest composite number that gives a false positive for this Quick Prime Number Test:

It is known as a Carmichael number because back in 1909, Robert D. Carmichael, an American mathematician, showed that it passed even more prime number tests than this one.

645 Four Consecutive Odd Numbers Pass a Prime Number Test

/ ivasallay / Leave a comment

There is a quick test to see if an odd number is prime: Plug in the number for x in the equation y = 2^x (mod x). If y = 2, then x is VERY LIKELY a prime number. I call that equation the quick prime number test.

The smallest composite number that gives a false positive to this test is 341. Click on that number to see an in depth description of this quick prime number test and how it relates to Pascal’s triangle.

mod 341 calculator

This is only a picture of a calculator.

The second smallest number to give a false positive is 561. Click on that number to see MANY false positives for other tests for that composite number.

645 is not usually tested to see if it is prime because it ends with a 5 and the sum of its digits is a multiple of 3. From those two divisibility rules, we know that 645 is a composite number divisible by both 3 and 5.

Still 645 is the third smallest number to give a false positive to the quick prime number test.

Here is a chart of the quick prime number test applied to the odd numbers from 343 to 681. (A similar chart for odd numbers up to 341 can be seen here.) Whenever y equals 2, I’ve made that 2 red. Prime numbers have been highlighted in yellow. Pseudoprimes 561 and 645 are in bold print.

Prime Number Test 343-681

There are 119 numbers less than or equal to 561 that pass this prime number test, and only 3 of those numbers are composite numbers that give a false positive. Amazing.

Perhaps you noticed something else that’s pretty amazing: 641, 643, 645, and 647 are FOUR consecutive odd numbers that pass the quick prime number test, and 645 is the only composite number of the four. Those are the smallest four consecutive odd numbers that pass the test.

It makes me wonder if longer strings of numbers that pass the test are possible. As almost everybody knows 3, 5, and 7 are the only consecutive odd numbers that are also prime numbers. All other strings of three or more consecutive odd numbers contain at least one composite number that is a multiple of 3. Including pseudoprimes like 645 certainly opens up the possibility of longer strings of prime and pseudoprime numbers.

I also continue to be fascinated by the amount of times on the chart that y equals an odd power of 2 (2, 8, 32, 128, 512).

Interesting observation: All three of these pseudoprimes are of the form 4n + 1. All prime numbers of the form 4n + 1 can be written as the sum of two square numbers that have no common factors. 341, 561, and 645 cannot be written as such a sum so they cannot be prime numbers.

______________________________________

645 is the hypotenuse of the Pythagorean triple 387-516-645. What 3-digit number is the greatest common factor of those three numbers?

  • 645 is a composite number.
  • Prime factorization: 645 = 3 x 5 x 43
  • The exponents in the prime factorization are 1, 1, and 1. Adding one to each and multiplying we get (1 + 1)(1 + 1)(1 + 1) = 2 x 2 x 2 = 8. Therefore 645 has exactly 8 factors.
  • Factors of 645: 1, 3, 5, 15, 43, 129, 215, 645
  • Factor pairs: 645 = 1 x 645, 3 x 215, 5 x 129, or 15 x 43
  • 645 has no square factors that allow its square root to be simplified. √645 ≈ 25.39685.