Find the largest natural number n such that n! is computed exactly

Question

I am starting out with matlab and am trying learn how the language works.

I am trying to work out how to Find the largest natural number n such that n! is computed exactly. I am allowed to use the Matlab functions factorial and intmax.

I am using Matlab version 2017a.

Many thanks

Thanks for joining Stack Overflow! Please review [How to ask](https://stackoverflow.com/help/how-to-ask)! — Bender Bending, Aug 04 '17 at 03:59
Wouldn't it just be the maximum `n` such that `factorial(n) <= intmax`? You could try to just keep computing `factorial(n)` until it is greater than `intmax`. — jodag, Aug 04 '17 at 04:47
Actually nevermind, large factorials would have a large number of trailing zeros (in both binary and decimal) due to so many 2s and 10s in the multiplication. Those values could potentially be represented exactly even as double precision floating point numbers so you can likely represent a few factorials larger than `intmax` perfectly in MATLAB. — jodag, Aug 04 '17 at 04:49
Which data type are you doing this for? `double`? `int64`? `int32`? It kinda matters... — gnovice, Aug 04 '17 at 04:53

gnovice · Answer 1 · 2017-08-04T05:27:25.783

Technically, you don't even need to use the factorial or intmax functions to solve this. Here's an example for an unsigned 64-bit integer type:

total = uint64(1);  % Set the data type you want here
N = 1;
while (total == (total*(N+1))/(N+1))
  N = N+1;
  total = total*N;
end
disp(N)

And the output:

 20    % Largest N for uint64 types that gives correct factorial(N)

This works due to the fact that data types have an upper limit on the size of the number they can represent. If you make the number too big, it will saturate at the maximum for integer types or lose precision for floating-point types (some interesting related information about precision here). The above loop keeps a running total that stores the factorial up to N and checks to see if multiplying then dividing by N+1 gives the same result, which it won't if the initial multiplication causes an overflow/precision loss.

@Tom J If this answers the question then please mark as answered. — jodag, Aug 04 '17 at 07:26

score 1 · Answer 2 · answered Aug 04 '17 at 04:40

Possible solution:

n=1;
Vec=[1];
IsAccurate=true;

while IsAccurate
    n=n+1;
    Vec(end+1)=n; %#ok<SAGROW>
    Factorial=prod(Vec); %multiply all vector elements
    IsAccurate=true;
    for i=1:n %test if division of factorial by number give correct result
        Number1=Factorial/Vec(i);
        Number2=prod(Vec([1:i-1,i+1:n]));
        Diff=Number1-Number2;
        IsAccurate=IsAccurate & Diff==0;
    end
end
disp(n)

Find the largest natural number n such that n! is computed exactly

2 Answers2