51 ms·

Could you provide such a proof? (just general outline would suffice...) I can't figure out a "pretty easy" way to do it.

SamReidHughes 7y ago
Every time you hit a power of ten, fracPart(log10(n!)) gets the unit interval finely iterated by n=10^k, 10^k + 1, 10^k + 2, ..., 10^k + sqrt(2 log(10) 10^k).
- notelonmusk 7y ago
  Sorry, but how is that a proof? It's not clear whether there is a number A with decimal expansion (a_1 a_2 ... a_k ) such that there doesn't exist a positive number X for which X ! = (a_{1} a_{2} ... a_{k} x_{k+1} x_{k+1} ... x_{s} ) for some arbitrary length s in the decimal expansion of X! .
  - SamReidHughes 7y ago
    It shows {fracPart(log10(n!))} is dense.
    - deleted 7y ago
      [deleted]
- markisus 7y ago
  I'm also not getting your proof. What does it mean every time you hit a power of 10? The sequence n! does not hit powers of 10 since all terms of the sequence after n=3 are at least divisible by 3. I agree though, density in (0,1) of the fracPart(log10(n!)) is a good thing to try to prove, since 10^fracPart(log10(n!)) should have the same digits as 10^intPart(log10(n!))*10^fracPart(log10(n!))=10^log10(n!)=n!
  - SamReidHughes 7y ago
    Every time n hits a power of 10, not n!. E.g. https://www.wolframalpha.com/input/?i=Table%5B%5Bfrac%28log10%28%2810%5E6+%2B+n%29%21%29%29%2C+%2810%5E6+%2B+n%29%21%5D%2C%7Bn%2C0.0%2C20.0%2C1.0%7D%5D https://www.wolframalpha.com/input/?i=Table%5B%5Bfrac%28log1... In general for b << 10^k, we have fracPart[log10((10^k + b)!)] ≈ fracPart[log10((10^k)!) + b(b+1)/(2 log(10) 10^k)]. So it takes sqrt(2 log(10) 10^k) steps for these factorial values to work their way around the unit interval. Increase k and you fill it arbitrarily finely. Edit: ^^^ To be clear, the approximation there is formed using the linear approximation log(1 + b/10^k) ≈ b/10^k, and basic log multiplication/addition/division formulas.
    - markisus 7y ago
      The approximation holds only for b << 10^k. Then you don't get to take O(10^k) steps to work you way around the unit interval, do you? After the approximation breaks down, you don't know that the spacing is approximately uniform anymore.
      - SamReidHughes 7y ago
        You only need sqrt(2 log(10) 10^k) steps. The spacing is not uniform, it's just bounded by O(1/10^(k/2)). The spacing is, at its greatest, about 1/sqrt(2 log(10) 10^k).
        markisus 7y ago
        I'm not sure you only need that many steps. As you start out, each step gives you a lot of distance. But log gets flatter and flatter the more steps you take. If you knew the number of steps, I think you could only make a lower bound on spacing, not an upper bound. Since at worst all the steps could be clustered really close, except for the last one. But now I have to think more because it seems like it should actually help the argument that the spacing gets finer and finer as you step, because that is what we want anyway. And is the number of steps actually important to the proof?
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 ago
  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?
  - ThrustVectoring 7y ago
    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.
    - markisus 7y ago
      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?

SamReidHughes 7y ago

Every time you hit a power of ten, fracPart(log10(n!)) gets the unit interval finely iterated by n=10^k, 10^k + 1, 10^k + 2, ..., 10^k + sqrt(2 log(10) 10^k).

notelonmusk 7y ago
Sorry, but how is that a proof? It's not clear whether there is a number A with decimal expansion (a_1 a_2 ... a_k ) such that there doesn't exist a positive number X for which X ! = (a_{1} a_{2} ... a_{k} x_{k+1} x_{k+1} ... x_{s} ) for some arbitrary length s in the decimal expansion of X! .
- SamReidHughes 7y ago
  It shows {fracPart(log10(n!))} is dense.
  - deleted 7y ago
    [deleted]
markisus 7y ago
I'm also not getting your proof. What does it mean every time you hit a power of 10? The sequence n! does not hit powers of 10 since all terms of the sequence after n=3 are at least divisible by 3. I agree though, density in (0,1) of the fracPart(log10(n!)) is a good thing to try to prove, since 10^fracPart(log10(n!)) should have the same digits as 10^intPart(log10(n!))*10^fracPart(log10(n!))=10^log10(n!)=n!
- SamReidHughes 7y ago
  Every time n hits a power of 10, not n!. E.g. https://www.wolframalpha.com/input/?i=Table%5B%5Bfrac%28log10%28%2810%5E6+%2B+n%29%21%29%29%2C+%2810%5E6+%2B+n%29%21%5D%2C%7Bn%2C0.0%2C20.0%2C1.0%7D%5D https://www.wolframalpha.com/input/?i=Table%5B%5Bfrac%28log1... In general for b << 10^k, we have fracPart[log10((10^k + b)!)] ≈ fracPart[log10((10^k)!) + b(b+1)/(2 log(10) 10^k)]. So it takes sqrt(2 log(10) 10^k) steps for these factorial values to work their way around the unit interval. Increase k and you fill it arbitrarily finely. Edit: ^^^ To be clear, the approximation there is formed using the linear approximation log(1 + b/10^k) ≈ b/10^k, and basic log multiplication/addition/division formulas.
  - markisus 7y ago
    The approximation holds only for b << 10^k. Then you don't get to take O(10^k) steps to work you way around the unit interval, do you? After the approximation breaks down, you don't know that the spacing is approximately uniform anymore.
    - SamReidHughes 7y ago
      You only need sqrt(2 log(10) 10^k) steps. The spacing is not uniform, it's just bounded by O(1/10^(k/2)). The spacing is, at its greatest, about 1/sqrt(2 log(10) 10^k).
      - markisus 7y ago
        I'm not sure you only need that many steps. As you start out, each step gives you a lot of distance. But log gets flatter and flatter the more steps you take. If you knew the number of steps, I think you could only make a lower bound on spacing, not an upper bound. Since at worst all the steps could be clustered really close, except for the last one. But now I have to think more because it seems like it should actually help the argument that the spacing gets finer and finer as you step, because that is what we want anyway. And is the number of steps actually important to the proof?

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 ago
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?
- ThrustVectoring 7y ago
  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.
  - markisus 7y ago
    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?