4 ms·
For any target number K, we can pick lower and upper bounds N and M with the following properties: 1. Multiplying by N causes the leading digits to increase by
by ThrustVectoring 7y ago
For any target number K, we can pick lower and upper bounds N and M with the following properties:
1. Multiplying by N causes the leading digits to increase by at least 0.5 and at most 1.0
2. Multiplying by M causes the leading digits to increase by at most 1.0
3. M - N is more than twice as large as the target number.
4. M > N and M & N both have the same number of digits.
We start at N!, then checking N+1! etc, increasing the leading digits by at least 0.5 and at most 1.0. We do this more than 2K times, so we're guaranteed to hit exactly K.
The first two conditions are pretty simple to achieve - if we're targeting 2019, then 10,003 works for N and 10,004 works for M, and we can easily find some number that fills our need for whatever target we get. For the third condition, we can multiply both N and M by 10. This increases M-N by a factor of ten, but has the exact same effect for the leading digit multiplication.
- markisus 7y agoWhat 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?
- ThrustVectoring 7y agoIf 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.
- markisus 7y agoMaybe 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?
- ThrustVectoring 7y ago6! / 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.
- deleted 7y ago[deleted]