7 ms·
Any number can start a factorial
- notelonmusk 7y agoThe 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 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 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, ...
- SamReidHughes 7y agoI'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.
- notelonmusk 7y ago> 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 ...
- deleted 7y ago[deleted]
- deleted 7y ago[deleted]
- lurquer 7y agoCould you provide such a proof? (just general outline would suffice...) I can't figure out a "pretty easy" way to do it.
- SamReidHughes 7y agoEvery 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 agoSorry, 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 agoIt shows {fracPart(log10(n!))} is dense.
- deleted 7y ago[deleted]
- markisus 7y agoI'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 agoEvery 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.
- amilein7minutes 7y agoI 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?
- amilein7minutes 7y agoVery 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.
- sillysaurusx 7y agoIn case anyone else was curious, Bedford's Law is apparently just a fancy name for the phenomenon where 1's appear much more frequently than 9's in any random sample of numbers. I think Bernie Madoff got caught faking the books due to the distributions not being shaped like Bedford's Law.
- eindiran 7y agoThat's correct, but I think its "Benford's Law" rather than "Bedford's Law". https://en.wikipedia.org/wiki/Benford%27s_law https://en.wikipedia.org/wiki/Benford%27s_law
- OnlineGladiator 7y agoWhat on Earth‽‽‽ How have I never heard of this before, and much more importantly - why is it true (I skimmed the wikipedia page and I didn't really see anything for 'why' but mostly for 'what')? So it takes the data and draws it on a log scale to visualize it, but doesn't explain why the data naturally transposes to a log scale (we are talking about random data sets in nature). If I think of it as a village with 1,000 people is more likely than a village with 2,000 people is more likely than a village with 3,000 people (and this continues in both directions), the only real conclusion I can come to is that nature prefers smaller numbers of things. But that wouldn't extend to something like accounting books (or at least the jump is not immediately obvious to me). EDIT: I guess I chose a bad example (although my point still is useful as a thought exercise), since this was used as an exception to the rule: > Benford's law is violated by the populations of all places with population at least 2500 from five US states according to the 1960 and 1970 censuses, where only 19% began with digit 1 but 20% began with digit 2, for the simple reason that the truncation at 2500 introduces statistical bias.
- ouid 7y agodid you type the first "‽" and then copy/paste the rest? basically the reason for this is that for any probability distribution over natural numbers that can reasonably be called the average probability distribution of natural numbers, I have to assign smaller probabilities to larger numbers. There's a lot of ways in which this is formally true, but it's certainly true practically. Among the k digit numbers, the ones starting with 2 are larger than the numbers starting with 1, so they have to be at most equally likely, but there are the same number of each, so the probability of picking any number starting with two has to be less than or equal to the probability of picking any number starting with 1.
- SamReidHughes 7y agoThe footnote and comments talk about this, but don't exactly mention that what you want for the probability of the leading digits "2019" is log10(2.020)-log10(2.019).
- LeoPanthera 7y agoWhile attempting to verify this, I was surprised to learn that bc has no built-in factorial function, even in the mathlib.
- therein 7y agoWhile looking into this, TIL bc is very scriptable: $ bc define fact_rec (n) { if (n < 0) { print "oops"; halt; } if (n < 2) return 1; return n*fact_rec(n-1); } fact_rec(5) 120