Numbers that look prime but aren't

 
A long time ago I made up the question (are questions ever really made up?)

What is the least number that looks prime but isn't?

It was not quite a joke in that it has an answer despite being non-rigorous.

My answer is 91:

Dividing by 2,3,5,11 have TRICKS

Squares are well known.

So the first number that looks prime but isn't is \(7\times 13=91.\)

I recently  saw the question asked on Quora and given a more interesting answer. The answer is by Nathan Nannon, a PhD in Math at Univ of CA, Davis (Graduated 2021). I paraphrase it here and then have some questions.

-----------------

What does it mean to look prime?

FIRST CRITERIA:

1) Its decimal representation ends in 1 , 3 , 7 , or 9 , and

2) It is not on the multiplication tables that a lot of people memorize, which go up to 12.

Based on these criteria, 39 is the first composite number that looks prime.

(If people no longer learn the mult tables then the answer would be 21.) 

SECOND CRITERIA: Use the trick that a number is divided by 3 if the sum of the digits is divisible by 3.  Then the first composite number that looks prime is 91 , followed by 119 , 133 , and 143.

THIRD CRITERIA: Fermat's Test: If \(p\) is prime then for all \(a\), \(a^p\equiv a \pmod p\).
Numbers that pass this test and yet are composite are called Carmichael numbers.

Here are the first few  Carmichael number:

561 AH- that does not count since 5+6+1 is divisible by 3.

1105 AH-doesn't count, ends with 5.

1729 AH- Nathan Nannon points out that 1729 is the sum of two cubes (more on that later) and hence we can use \(a^3+b^3 = (a+b)(a^2-ab+b^2)\). This only works if you KNOW that 1729 is the sum of two cubes. AH- most mathematicians do know this because (1) it is the least number that can be written as the sum of 2 cubes in 2 diff ways, and (2) this fact has been popularized by the following true story (I quote from Wikipedia, see here) which explains why such numbers are called Taxicab Numbers

The name is derived from a conversation ca. 1919 involving mathematicians G. H. Hardy and Srinivasa Ramanujan. As told by Hardy:

I remember once going to see him [Ramanujan] when he was lying ill at Putney. I had ridden in taxi-cab No. 1729, and remarked that the number seemed to be rather a dull one, and that I hoped it was not an unfavourable omen. "No," he replied, "it is a very interesting number; it is the smallest number expressible as the sum of two cubes in two different ways."

Note 

1) Oddly enough, the fact that 1729 is the sum of two cubes in TWO diff ways does not make it any easier to factor. We just needed one way. 

2) To say that 1729  does NOT look prime depends on history as well as math. If not for the Hardy-Ramanujan story, would most mathematicians know that 1729 is the sum of 2 cubes. Possibly since its 1000+729. But not clear. Martians may think 1729 looks prime.

2465 AH-doesn't count, ends with 5

2821 AH- just looking at it, it is clearly divisible by 7.

6601 AH- OKAY, this one really does look prime.

UPSHOT
Depending on what criteria you use, the least number that looks prime but isn't is either 21 OR 39 OR  91 OR  6601 or something else, depending on what looks prime to you.

------------------------------------------------------

QUESTION
Is there some natural and simple criteria that rules out 6601? This may depend on your definitions of natural and simple.

QUESTION The first few Carmichael numbers had small factors. 6601 is divided by 7. Is there some function   f with \(f(n) \ll \sqrt n\) such that if \(n\) is a Carmichael number then it has a factor \(< f(n)\). ?

The next few Carmichael number after 6601 is 8911, which 7 divides. So that looks good. But alas, Jack Chernick proved (see here) that any number of the form \((6k+1)(12k+1)(18k+1)\) where \(6k+1\),\(12k+1\), and \(18k+1\) are all primes, is a Carmichael number. It is not know if this generates infinitely many Carmichael numbers. Hence if some f(n) exists then its probably \(\Omega(n^{1/3})\).

Taking a Stand

On February 20th we got the news from the National Science Foundation Algorithms Foundations Team that long-time NSF program director Tracy Kimbrel, was leaving the NSF, and not by choice.

Along with many others in part-time status at NSF, my service has been terminated earlier than I intended or expected.  It has been a great privilege and a great honor to serve the Algorithmic Foundations community over the last decade and a half.  It's disappointing to have it end so abruptly.  I will miss it and all of you.

Tracy is just one of many government employees losing their jobs but when you know someone it feels personal. Tracy has been a fixture at the NSF and often comes to theory conferences to talk about grant opportunities and the state of the NSF. In my yearly pre-covid pilgrimages to the foundation for panels, I always had great conversations with Tracy and watched him work, getting the information he needed from us to make the tough decisions of which projects to fund, always many more worthy than the available funding. The theory community loses with Tracy out of the NSF.

We did get some good news earlier this week with the NSF reinstating most of their probationary employees. And Trump did say near the end of his speech yesterday "we are going to conquer the vast frontiers of science" but apparently we'll do it with a much smaller NSF if Trump follows through with his plans.

Talking with some fellow academics at another university, they had almost given up. "What can we do?". 

We can push back.

Start by doing nothing. Don't preemptively change your policies and your values. Too many universities and organization are abandoning DEI programs, changing their curriculum, freezing hiring of faculty and students, in anticipation of challenges to come. We may see a time that new policies will survive the courts and force us to change, but not yet.

While the democrats in congress seem powerless, many of the governors, including my own governor JB Pritzker, have fought back, mostly in the courts, and have stopped, for now, much of the damage to the NIH and NSF. The computing societies urge congress to protect our research funding, especially in a time when we need to compete technologically with China and other countries. 

As individuals, we can take our own steps, participate in Stand Up for Science on Friday, reach out to our representatives at the national and state level, and just be part of the resistance. We can't let bullies dictate our future, we must control it for ourselves. 

Karp recently turned 90 but there was no conference to celebrate that. Which numbers do we use and why?

Karp turned 90 in January of 2025. I searched to see if there is a 90th Birthday Conference for him.  I did not find one (is there one?).  For which years do we have celebratory birthday conferences?

Here are some conferences in honor of  60th Birthdays, by alphabetical order of last name. 

Eric Allender here

Laci Babai here

Allan Borodin here

Stephen Cook here

Rod Downey here

Juris Hartmanis (at the 1988 Structures, now Complexity, conference, predating the web). Lance posted about it here.

Russell Impagliazzo here

Ravi Kanan here

Richard Karp (I could not find the link.)

Stuart Kurtz here

Michael Rabin (I could not find the link but I recall planning to go but snow cancelled my flight.)

Ronitt Rubinfeld here

Michael Saks here

Alexander Shen here

Michael Sipser here

Shang-Hua Teng here

Leslie Valiant here (I thought he also had an 80th bday but I am wrong- he is younger than 80.) 

Vijay Vazarani here

Nikolay Vereschagin here

Avi Wigderson here

I am sure there are more. 

Having a conference for someone's 80th birthday is also done. Here are a few:

Richard Stanley here

Michael Rabin here

Stephen Cook here (This was actually a conference for 50 years of Complexity Theory: A Celebration of the work of Stephen Cook. It was 50 years since Cook published what is now called the Cook-Levin Theorem. It also happened to be the year he turned 80.) 

Donald Knuth here but also see Lance's blog post on the meeting   here  and Knuth's favorite bday     here.

 Martin Kruskal here and here for my post on it, and Clyde Kruskal (Martin's son) post on it. That was back in 2007 when I was a guest poster. And Clyde was my guest, so he was a guest-guest poster.

I am sure there are many more. 

Numbers between 60 and 80 are rare (my wife read this and noted that there are 18 of them not including endpoints) but here are some:

John Osborne  (UMCP Math Prof) had a 64th. Could not find a link. 

Dick Dudley 65.  (MIT Math professor, Not to be confused with Big Dick Dudley who was a wrestler or Underwood Dudley who wrote a book on Math Cranks, see here, which I was amazed to find out I DID NOT write a review of.

Mike Patterson here (Why 66? Why not 66!)

Harry Lewis had a 70th, see here (I asked WHY 70? He said the organizer, Margo Seltzer, wanted it then. That is another point- the organizer really controls which year and also if it happens at all.) 

Mihalis Yannakakis had a 70th here 

Ravi Kanan 70 here

Leonid Levin had a 75th, see here

Dick Lipton has a 75th, see here

Manuel Blum had a 77th since 77=7*11 is a Blum Integer. ( The only reason I know it exists is because Lance went to it.) 

I've seen 100th bday conferences. 

Turing here (This is one of many Turing Celebrations for his 100th. It was in 2012. Turing died in 1954.)

Erdos here (This was in 2012. Erdos died in 1996)

Chernoff here (He attended. He is still alive as of this writing, at the age of 101) 

Kolmogorov here (The Day K turned 100 a student told me this. I then gave a lecture on Kolm complexity instead of the planned topic, on the fly. Now that my course is all on slides, and some classrooms don't even have  a blackboard or whiteboard, I can't do that anymore. Oh well.)

I am sure there are more. 

1) Why are 60, 80, 100 the usual numbers? They are nice and round. And 60 is big enough so that the person being celebrated has done stuff, but not so big that they are dead. 

2) There should be more clever ones like Osborn (64) and Blum (77). If there was ever a conference in my honor that would be hard, since the number most associated to me is 5/12 (see here). I had not done much in math at the age of 5 months. Oh well.