Hacker News Reader

Comment by MauranKilom | Hacker News Reader

    12347
      -
    65393
    ++--
   [solution next - omitted for spoiler reasons]

I was more surprised about how little trial and error I needed to find primes than about how few guesses it actually took...

View on HN

Same, I was so surprised to get it solved at the second row, after ~8 attempts to find a prime without the numbers that had not matched.

    12347
      -
   [solved]

It seems a lot of us came up with 12347 for the first line.

While natural in terms of just inputting numbers, it's also not bad to use as first guess because primes are denser (in an "average absolute distance" sense) the lower the magnitude you're around. Without having checked, I would expect there to be more primes of the form 123** than 987**, so you're more likely to gain correct digits with this guess.

Edit: I checked, it's 9 vs 8 primes. But nearby prefixes also have more and there's a lot of variance. Still, there are overall more primes among the same range of smaller numbers (1000-5499 has ~4400 primes, 5500-99999 has ~4000).

Note that, despite this, you probably shouldn't include 0 in the starting guess (e.g. 10247) because 0 will be in the solution less frequently (can't be the leading digit), meaning you gain less info on average.

56809 is a pretty good second guess for this situation :p

Ha, those were exactly my first 2 guesses.

I read the "help" thing, which suggested 71429 as the first guess, so I started there. (9 was right, and the other digits were wrong. That meant the second guess got the right digits, and the third guess got the right prime.)

log(100000) is 5, so approximately 1 in 5 numbers below 100k is prime. Obviously those in the range 10000-99999 are less dense, but primes are still surprisingly common.

You want a natural log there; ln(100000) ~ 11.5.

That being said, the pool you're really working from is the numbers with last digit 1, 3, 7, or 9. One out of every 4.6 such numbers under 10^5 is prime. So just guessing until you find a prime is practical.

Hi, can you provide some search terms that will help me understand the relationship between ln and prime density?

https://en.wikipedia.org/wiki/Prime_number_theorem

Or https://en.wikipedia.org/wiki/Prime-counting_function .

Ah you're correct. Annoying how Google interprets log(x) as base-10 (but more shame on me for not realising that e^5 is obviously not 100000). In my experience everyone uses log and ln interchangeable outside of lessons at school.

log(x) historically conventionally defaults to base-10. https://en.m.wikipedia.org/wiki/Common_logarithm

As the wiki page itself notes though:

> On calculators, it is printed as "log", but mathematicians usually mean natural logarithm (logarithm with base e ≈ 2.71828) rather than common logarithm when they write "log".

And you can knock out multiples of 3 by adding digits.

Sure, but that's a little more work than just looking at the last digit, so it's debatable whether it's worth the trouble.

Looks like there's 8,363 5 digit primes, from 10007 to 99991, so about 1 in 11

Why isn’t 00002 your lower bound?

The game does not accept leading zeros (00017: "Not a 5 digit prime")

Reply on news.ycombinator.com