Factorial Properties

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
ircmaxell
Posts: 44
Joined: Wed Dec 24, 2008 3:06 am UTC

Factorial Properties

Postby ircmaxell » Fri Oct 01, 2010 9:06 pm UTC

With as little code as possible (bonus points for 1 readable line), estimate the number of trailing 0's the factorial of n will have within 10 of the actual figure (And n be very large, yet the estimate should still hold)...

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

Re: Factorial Properties

Postby Xias » Fri Oct 01, 2010 10:18 pm UTC

Spoiler:
n/5 rounded down.


Am I missing something?

User avatar
ircmaxell
Posts: 44
Joined: Wed Dec 24, 2008 3:06 am UTC

Re: Factorial Properties

Postby ircmaxell » Fri Oct 01, 2010 10:30 pm UTC

Xias wrote:
Spoiler:
n/5 rounded down.


Am I missing something?

Doesn't work:
Spoiler:
n = 1000. Your estimate would be 200. The actual is 249, so it's off by a significant amount (25% actually)...

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: Factorial Properties

Postby Nitrodon » Fri Oct 01, 2010 10:35 pm UTC

Spoiler:
Here's the exact formula, but I'm too lazy to translate it into code:
[math]\sum_{i=1}^{\log_5(n)} \left \lfloor \frac{n}{5^i} \right \rfloor[/math]

Also, I don't know of any way to do this in one readable line of code while remaining within 10 for both n=2,384,185,791,015,624 and n=2,384,185,791,015,625. Are you sure it's possible?

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

Re: Factorial Properties

Postby Xias » Fri Oct 01, 2010 10:40 pm UTC

ircmaxell wrote:
Xias wrote:
Spoiler:
n/5 rounded down.


Am I missing something?

Doesn't work:
Spoiler:
n = 1000. Your estimate would be 200. The actual is 249, so it's off by a significant amount (25% actually)...


Right. I didn't think about
Spoiler:
Numbers divisible by 25, 125, etc.

I noticed that it would be based on the instances of 5 in the factorial and kind of jumped the gun.

User avatar
Lopsidation
Posts: 183
Joined: Tue Oct 27, 2009 11:29 pm UTC

Re: Factorial Properties

Postby Lopsidation » Sat Oct 02, 2010 2:01 am UTC

Most readable one-liner ever:
Spoiler:
(Array.new(n) {|x| x+1}).inject(1) {|product, new| product*new}.to_s.gsub(/[0]+\z/) {|match| puts match.length}

Computes the factorial, converts it to a string, and finds the number of zeroes at the end.

ericgrau
Posts: 92
Joined: Sat Dec 13, 2008 7:14 pm UTC

Re: Factorial Properties

Postby ericgrau » Sat Oct 02, 2010 8:11 am UTC

Xias wrote:
ircmaxell wrote:
Xias wrote:
Spoiler:
n/5 rounded down.


Am I missing something?

Doesn't work:
Spoiler:
n = 1000. Your estimate would be 200. The actual is 249, so it's off by a significant amount (25% actually)...


Right. I didn't think about
Spoiler:
Numbers divisible by 25, 125, etc.

I noticed that it would be based on the instances of 5 in the factorial and kind of jumped the gun.

Spoiler:
In that case does this work?

for(i = 1; i <= log(n) / log(5); i++;) {result += floor(n / 5 ^ i);}

Multiples of 25 get counted twice, btw, both for 5 and 25, so they do each provide 2 zeros
Likewise multiples of 125 get counted 3 times, etc.
log (n) / log(5) = log10 n / log10 5 = log5 n (old math rule I remembered, ln n / ln 5 also gives the same result)

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

Re: Factorial Properties

Postby Tirian » Sat Oct 02, 2010 9:01 pm UTC

Spoiler:
def fact(x): return x/5 + fact(x/5) if x else 0

User avatar
undecim
Posts: 289
Joined: Tue Jan 19, 2010 7:09 pm UTC
Contact:

Re: Factorial Properties

Postby undecim » Sun Oct 03, 2010 1:49 am UTC

In python, first thing I though (ignoring the number of lines) is

Spoiler:

Code: Select all

def FactoralTrailingZeroes(n):
    zeroes=0
    for i in range(1,n+1):
        j=i
        while not j%5:
            j=j/5
            zeroes += 1
    return zeroes


Focusing on lines, I came up with...
Spoiler:
...what is technically 3 lines, but all the work is done on one:

Code: Select all

import math
def FactoralTrailingZeroes(n):
    return (floor(n/5) + FactoralTrailingZeroes(floor(n/5))) if n else 0

Experimentation shows that this is equally precise and orders of of a magnitude faster than my initial function

Although, I exported the results of this function for 1 < n < 1000 to Open Office Calc and made a column for f(n)/n, and noticed that it converged to roughly 0.25. In fact, for n >=, f(n) is within 10% of n/4, and within 1% after 1250.

If I were going for the most efficient possible code (excluding assembly, though this would probably be easy to convert to assembly) and could except results within 10% error, I would use this C code (not tested, but I see no problems with it):

EDIT: Oops, misplaced parenthesis.

Code: Select all

int estimatezeroes(int n){
    if (n < 125) {
        if (n < 25) {
            return (n-(n%5))/5
        }
        return (n-(n%5))/5 + (n-(n%25))/25
    }
    return n>>2
}


or, in one semi-readable line:

Code: Select all

int estimatezeroes(int n){ return n < 125 ? ( n - ( n % 5 ) ) / 5  + ( n - ( n % 25 ) ) / 25  : n>>2 }


in this code, for n >= 125, the function returns n>>2, which is equivalent to (but far more efficient than) floor(n/4)

You could even twerk this to whatever precision you need by increasing the limit of the precise algorithm. For example, the following line guarantees 2% accuracy:

Code: Select all

int estimatezeroes(int n){ return n < 625 ? ( n - ( n % 5 ) ) / 5 + ( n - ( n % 25 ) ) / 25 + ( n - ( n % 125 ) ) / 125 : n>>2 }


EDIT: Hah, misread OP slightly.
Spoiler:
As far as I can tell through experiment, this is never more than 10 digits off, at least no where within the range of int or long

Code: Select all

int estimatezeroes(int n){ return n>>2 }
Last edited by undecim on Sun Oct 03, 2010 3:23 am UTC, edited 1 time in total.
Blue, blue, blue

User avatar
undecim
Posts: 289
Joined: Tue Jan 19, 2010 7:09 pm UTC
Contact:

Re: Factorial Properties

Postby undecim » Sun Oct 03, 2010 3:17 am UTC

Proof to my previous assumption that...
Spoiler:
...f(n)/n converges to 1/4

Starting with Nitrodon's formula:
[math]f(n) = \sum_{i=1}^{\log_5(n)} \left \lfloor \frac{n}{5^i} \right \rfloor[/math]
replace all n with 5^n
[math]f(5^n) = \sum_{i=1}^{\log_5(5^n)} \left \lfloor \frac{5^n}{5^i} \right \rfloor[/math]
simplify
[math]f(5^n) = \sum_{i=1}^{n} {5^{n-i}}[/math]
Take the limit of f(5^n)/5^n
[math]\lim_{n\to\infty} \frac{f(5^n)}{5^n} = \lim_{n\to\infty} \frac{\sum_{i=1}^{n} {5^{n-i}}}{5^n}[/math]
Simplify
[math]\lim_{n\to\infty} \frac{f(5^n)}{5^n} = \lim_{n\to\infty} \sum_{i=1}^{n} {5^{-i}}[/math]
Take the sum of the geometric series
[math]\lim_{n\to\infty} \frac{f(5^n)}{5^n} = \frac{\frac{1}{5}}{1-\frac{1}{5}}[/math]
simplify
[math]\lim_{n\to\infty} \frac{f(5^n)}{5^n} = \frac{1}{4}[/math]
replace 5^n with n
[math]\lim_{n\to\infty} \frac{f(n)}{n} = \frac{1}{4}[/math]
Blue, blue, blue

Malle
Posts: 42
Joined: Wed Jan 07, 2009 1:50 pm UTC

Re: Factorial Properties

Postby Malle » Sun Oct 03, 2010 10:42 am UTC

Exact solution in MATLAB; it gives solutions up to and including 10^308, after which it complains.
Spoiler:
Specifically, it complains about recursion limit of 500.

Code: Select all

function z=fzf(n);if n>=5;z=floor(n/5)+fzf(n/5);else z=0;end;end

Recursively check through all powers of 5 to tally up how many 5's there are in the prime factorization of the factorial. We do not need to check the number of 2's, since we need only one of each and given that 2 < 5 there will be more 2's in the prime factorization.


undecim wrote:EDIT: Hah, misread OP slightly.
Spoiler:
As far as I can tell through experiment, this is never more than 10 digits off, at least no where within the range of int or long

Code: Select all

int estimatezeroes(int n){ return n>>2 }

This works up to
Spoiler:
5^11-2. For n=5^11-1, f(n) = 12207020 while n>>2 = 12207031
Specifically, the error seems to be bounded by
Spoiler:
e_max = floor(log(n+1)/log(5))
So
Spoiler:
while you have showed that f(n) approaches n/4, it does not approach quickly enough to make the error bounded over all n.

User avatar
ircmaxell
Posts: 44
Joined: Wed Dec 24, 2008 3:06 am UTC

Re: Factorial Properties

Postby ircmaxell » Mon Oct 04, 2010 12:47 pm UTC

Tirian wrote:
Spoiler:
def fact(x): return x/5 + fact(x/5) if x else 0

Won't that return floats (I'm a little bit familiar with Python, but not that versed with it)? If so, you'd need to wrap both divisions by a floor method. Otherwise, I think this wins so far...

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Factorial Properties

Postby mike-l » Mon Oct 04, 2010 2:05 pm UTC

Malle wrote:So
Spoiler:
while you have showed that f(n) approaches n/4, it does not approach quickly enough to make the error bounded over all n.

Actually he only showed that
Spoiler:
If f(n)/n has a limit, it is 1/4.

But it turns out that f(n) = n/4 - s/4, where s is the sum of the base 5 digits of n. And since s << n, the limit holds.

Now the question is can I find s faster than Tirian's algorithm (which yields s indirectly by the above formula)?
Last edited by mike-l on Wed Oct 06, 2010 3:14 am UTC, edited 3 times in total.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

Re: Factorial Properties

Postby Tirian » Mon Oct 04, 2010 4:44 pm UTC

ircmaxell wrote:
Tirian wrote:
Spoiler:
def fact(x): return x/5 + fact(x/5) if x else 0

Won't that return floats (I'm a little bit familiar with Python, but not that versed with it)? If so, you'd need to wrap both divisions by a floor method. Otherwise, I think this wins so far...


I can verify that this code works in Python 2.x. You'd need to say x/5.0 if you wanted a floating point quotient. I seem to recall that this is one of the nice features that they "fixed" when they jumped to 3.0, but It might be that integer division became x\5.

I didn't test it, but I assume you'd get a very similar length result in C and its relatives. You'd need "int" in two places, but the ternary operator is more compact.

Malle
Posts: 42
Joined: Wed Jan 07, 2009 1:50 pm UTC

Re: Factorial Properties

Postby Malle » Tue Oct 05, 2010 6:42 am UTC

mike-l wrote:
Spoiler:
Now the question is can I find s faster than Yakk's algorithm (which yields s indirectly by the above formula)?
Which algorithm would that be? I haven't seen anyone by that name post in this thread.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Factorial Properties

Postby mike-l » Wed Oct 06, 2010 3:14 am UTC

Malle wrote:
mike-l wrote:
Spoiler:
Now the question is can I find s faster than Yakk's algorithm (which yields s indirectly by the above formula)?
Which algorithm would that be? I haven't seen anyone by that name post in this thread.


Oops, was following another thread that Yakk was in, multitask fail. Should be Tirian's.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 6 guests