CODEWITHSUNDEEP
c++c
lidia901
lidia901

Reputation: 39

How many digits are in N factorial

I have the following problem, as says in the title: For each value of N, print out how many digits are in N!. For example, if n=32000, I should get 130271. I have thought about a recursive solution. It works for smaller numbers, but for the above example it prints 31997. I am convinced that my thinking is wrong, but I can't really find a rule for bigger numbers. Somewhere, n! begins to skip steps, I think. I mean, it does not increases with a digit, but with two or three. I have the following code:

#include <stdio.h>
#include <stdlib.h>

//For each value of N, print out how many digits are in N!.

int how_many(int n){
    if( n <= 3)
        return 1;
    if( n == 4)
        return 2;
    if( n == 5 || n == 6)
        return 3;
    if( n >= 7)
        return 1 + how_many(n-1);

    }


int main()
{
    int n;
    printf("The number n is : ");
    scanf("%d", &n);

    int counter = 0;

    counter = how_many(n);

    printf("n! has %d digits", counter);

    return 0;
}

Upvotes: 1

Views: 501

Answers (3)

lidia901
lidia901

Reputation: 39

The answer of @JohnZwinck solved my problem. Here is the resulting code:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define M_PI 3.14159265358979323846

//For each value of N, print out how many digits are in N!.

int digits_in_factorial(int n){
    return floor((n+0.5)*log(n) - n+ 0.5*log(2*M_PI))/log(10) + 1;
}

int main()
{
    int n;
    printf("Numarul n este : ");
    scanf("%d", &n);

    int counter = 0;

    counter = digits_in_factorial(n);

    printf("n! are %d cifre", counter);

    return 0;
}

Upvotes: 1

chux
chux

Reputation: 154070

OP's recursive method estimates too low:

return 1 + how_many(n-1);

Should be more like

return log10(n) + how_many(n-1);

Using OP's original integer approach and below how_many(32000) --> n! has 123560 digits - a better estimate.

int how_many(int n) {
  if (n <= 3)
    return 1;
  if (n == 4)
    return 2;
  if (n == 5 || n == 6)
    return 3;

  int count = 0 + how_many(n - 1);
  while (n > 3) {
    n /= 10;
    count++;
  }
  return count;
}

IAC, OP has found Stirling's method.

Upvotes: 0

John Zwinck
John Zwinck

Reputation: 249333

What you're doing is really log10(N!). Once you realize that, you can use Stirling's Approximation or one of the other techniques explored here: https://math.stackexchange.com/questions/138194/approximating-log-of-factorial

Upvotes: 7

Related Questions