Hacker News Reader

Comment by notelonmusk | Hacker News Reader

The article's opening sentence: "Any positive number can be found at the beginning of a factorial..." is a strong statement but no proof is given.

Missing: "... with high probability, and supported by analysis of the digits of factorials from 1 to 10,000"

The work by Diaconis mentioned but not cited: [0] https://statweb.stanford.edu/~cgates/PERSI/papers/digits.pdf - The distribution of leading digits ad uniform distribution mod 1 - Persi Diaconis

The sequence: [1] https://oeis.org/A076219 - Smallest positive integer m such that m! begins with n in base 10 :: 1, 2, 9, 8, 7, 3, 6, 14, 96, 27, 22, 5, 15, 42, 25, 89, 69, 76, 63, 16, 87, 113, 54, ...

View on HN

I'm not sure what you're getting at, but "any positive number can be found at the beginning of a factorial" is correct. Not with high probability, but with absolute certainty. I don't know which Diaconis proved, but it's pretty easy to construct a non-probabilistic, constructive proof.

Edit: The paper you linked does not prove it with high probability, it proves {n!} is a strong Benford sequence. Edit: Which implies absolute certainty.

> I'm not sure what you're getting at

I'm sure what I'm not getting at, which is the proof. I'll think about it. Processing ...

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

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.

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.

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).

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! .

It shows {fracPart(log10(n!))} is dense.

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!

Every time n hits a power of 10, not n!.

E.g. 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.

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.

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).

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?

The distance you cover with step b is about b/(log(10) 10^k). The exact distance is log10((10^k + b)/10^k). That's a funny way of saying fracPart(log10(10^k + b)).

The number of steps tells you how big the last step is.

Okay I think I buy it. Great proof, thanks!

I haven't thought about this carefully but is it correct to say the probability of finding n as the leading digits for a bounded m (but both very large) is a decreasing function of n?

Very cool! Is there a pattern in the sequence of m's? It feels as though there must be some bounds on the terms of the sequence on m's given that the probability of appearance of n as the first digits decreases with n, in the sequence of factorials.

Reply on news.ycombinator.com