Hacker News Reader

Comment by markisus | Hacker News Reader

What does "multiplying by N" mean? Like if my current guess is X! and that doesn't work, I should try (N*M)! ?

What does "increase by at least 0.5" mean? If my leading digits are 999, how do you increase them at all?

If your current guess is X such that N<X<M, then (X+1)!/(X!) = X+1. Since this is also between N and M inclusive, adding one to the factorial is equivalent to multiplying the leading digit by a number that is slightly larger than one. This multiplication will cause the leading digits of (X+1)! to be larger than the leading digits of (X!). If the leading digits are all nines, you just wrap around to 100 and the same logic gets you as far as you want to go.

Maybe an example will help me understand. Let's say I wanted to have the leading digits 921, and I start with a guess of X=5.

What do I do now?

6! / 5! = 6, which is way too big. So, instead try X=15. The leading digits of 16 is still too big, so go to X=105. Repeat this process until you get a sufficiently small change in the leading digits between adjacent numbers - 10,005 barely works, so might as well go to 100,005 instead and be sure we're hitting every number.

Now the problem is that you might not have enough small increments you can make. You can always replace X=100,005 with X=1,000,0050 - multiply by ten, and the leading digits behave the same on multiplication, but you have ten times as many numbers you can multiply by.

You basically can divvy up things in as many fine increments as you want, so you can always find some number that does things properly.

Reply on news.ycombinator.com