Hacker News Reader

Comment by metalliqaz | Hacker News Reader

So are people just really good with numbers? I don't know any 5 digit primes nor do I know a way to calculate them on the fly.

View on HN

apparently 9.3% of all '5 digit' numbers are prime, so random guessing isn't a bad strategy - you'll find one in 10.75 totally randomly chosen numbers to be prime.

Being a little smarter, prime number can only end in a 1, 3, 7 or 9 - (ending in 0, 2, 4, 6, 8 would be even, ending in 5 would be odd), so in fact it's more like 25% of 'likely' guesses.

IIRC, randomly guessing is _always_ a good strategy for "give me a prime in the range [a, b]" , in other words that's what's used for algorithms that need primes anyway. Either guess and check or guess and increase-by-2-until-prime.

Does work _much_ better in this range than at crypto sizes though.

Its a weird thing where in smaller scales, primes numbers that LOOK prime are decent candidates of actually being prime.

All one- and two-digit numbers that look prime are prime, except 91.

This assumes that you can easily identify - multiples of 2 and 5 (by their last digit) - multiples of 3 (the sum of their digits is divisible by 3) - multiples of 11 (for two-digit ones, they have both digits the same: 11, 22, 33, ..., 99) - squares

So the first number that looks prime but isn't is the product of the two smallest primes that aren't "easy", which is 7*13 = 91.

I used this site to explore options. http://compoasso.free.fr/primelistweb/page/prime/liste_onlin... It's a bit tedious but still fun-ish and seemed better than guessing.

Unlike Wordle, I assume it's unreasonable to expect a player to know primes so I don't think I'd call this cheating.

I intuited a probably-inaccurate trick with exponentially raising a small prime (e.g 7*7*7etc), doubling the multiple (*2), and subtracting 1 (to get an odd number).

That got me two substantially-different primes and narrowed my numbers a lot, which then became guesswork.

My guesses in the end:

  -?---
  ?---!
  ?-??!
  ?!??!
  !!!!!

The number you come up with in that way is at least guaranteed to not be divisible by 2 or 7. Obviously that doesn't mean it's prime but it definitely helps your odds.

Also usefully, (2(a+1)^n-1) % a = (2a(a+1)^(n-1) + 2(a+1)^(n-1) - 1) % a = 1. So if you choose one of the 3k+1 primes, it's also guaranteed not divisible by 3.

lol this would not help me at all

by the way am I supposed to take some meaning from the italicized '7' or was that just a typo?

He probably had 7x7x7, but with asterisks instead of the "x"s.

correct, thanks for the heads up. Fixed

If you are on Unix:

    primes 10000 99999 | less

Then recall that "less" includes a regex-based search on the / key.

This doesn't give you direction as to the best to try, of course, but it's hard to beat it in terms of bang for the buck if you're just going to try a few.

You can guess a prime relatively easily given a few attempts, as besides 2 and 5, all other primes will have a 1, 3, 7, or 9 as its least significant digit. So, for starters, you'd never guess a number with any other least significant digit.

Yeah I would really rather this just let me guess non-primes even though that would make it more challenging. Trying to find a prime by guessing randomly over and over is pretty frustrating.

I thought the same, but it rejects guesses that are not valid prime numbers. So you'll find some with trial and error. With that it took me only three guesses.

Reply on news.ycombinator.com