Sum of factorials for large numbers

I want to calculate the sum of digits of N!.

I want to do this fo开发者_运维问答r really large values of N, say N(1500). I am not using .NET 4.0. I cannot use the BigInteger class to solve this.

Can this be solved by some other algorithm or procedure? Please help.

I want to do some thing like this Calculate the factorial of an arbitrarily large number, showing all the digits but in C#. However I am unable to solve.

There is no special magic that allows you to calculate the sum of the digits, as far as I am concerned.

It shouldn't be that hard to create your own BigInteger class anyway - you only need to implement the long multiplication algorithm from 3rd grade.

If your goal is to calculate the sum of the digits of N!, and if N is reasonably bounded, you can do the following without a BigInteger type:

• Find a list of factorial values online (table lookup will be much more efficient than calculating from scratch, and does not require BigInteger)
• Store as a string data type
• Parse each character in the string as an integer
• Add the resulting integers

There are two performance shortcuts that you can use for whatever implementation you choose.

1. Chop off any zeros from the numbers.
2. If the number is evenly divisible by 5^n, divide it by 10^n.

in this way,

16*15*14*13*12*11*10*9*8*7*6*5*4*3*2 = 20,922,789,888,000
//-->
16*1.5*14*13*12*11*1*9*8*7*6*0.5*4*3*2 = 20,922,789,888 //Sum of 63

Also, it feels like there should be some algorithm without reverting to calculating it all out. Going to 18!, the sums of the digits are:

2,6,6,3,9,9,9,27,27,36,27,27,45,45,63,63,63
//the sums of the resulting digits are:
2,6,6,3,9,9,9,9,9,9,9,9,9,9,9,9,9

and notably, the sum of the digits of 1500! is 16749 (the sum of whose digits are 27)

Here's some working code. Some components can be improved upon to increase efficiency. The idea is to use whatever multiplication algorithm I was told in school, and to store long integers as strings.

As an afterthought, I think it would be smarter to represent large numbers with List<int>() instead of string. But I'll leave that as an exercise to the reader.

Code Sample

static string Mult(string a, string b)
    {
        int shift = 0;
        List<int> result = new List<int>();
        foreach (int aDigit in a.Reverse().Select(c => int.Parse(c.ToString())))
        {
            List<int> subresult = new List<int>();
            int store = 0;
            foreach (int bDigit in b.Reverse().Select(c => int.Parse(c.ToString())))
            {
                int next = aDigit*bDigit + store;
                subresult.Add(next%10);
                store = next/10;
            }

            if (store != 0) subresult.Add(store);

            subresult.Reverse();
            for (int i = 0; i < shift; ++i) subresult.Add(0);
            subresult.Reverse();

            int newResult = new List<int>();
            store = 0;
            for (int i = 0; i < subresult.Count; ++i)
                {
                    if (result.Count >= i + 1)
                    {
                        int next = subresult[i] + result[i] + store;
                        if (next >= 10)
                            newResult.Add(next % 10);
                        else newResult.Add(next);
                        store = next / 10;
                    }
                    else
                    {
                        int next = subresult[i] + store;
                        newResult.Add(next % 10);
                        store = next / 10;
                    }
                }

            if (store != 0) newResult.Add(store);

            result = newResult;
            ++shift;
        }

        result.Reverse();
        return string.Join("", result);
    }

    static int FactorialSum(int n)
    {
        string result = "1";
        for (int i = 2; i <= n; i++)
            result = Mult(i.ToString(), result);
        return result.Sum(r => int.Parse(r.ToString()));
    }

Code Testing

Assuming the code snippet above is in the same class as your Main method, call it thusly.

Input

    static void Main(string[] args)
    {
        Console.WriteLine(FactorialSum(1500));
    }

Output

16749

Here's a port of the C++ code you reference in one of your comments. One thing to realize when porting from C++ to C# is that integers that are zero evaluate to false and integers that are non-zero evaluate to true when used in a Boolean comparison.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ArbitraryFactorial
{
    class Program
    {
        const int max = 5000;

        static void display(int[] arr)
        {
            int ctr = 0;
            for (int i = 0; i < max; i++)
            {
                if (ctr == 0 && arr[i] != 0) ctr = 1;
                if (ctr != 0)
                    Console.Write(arr[i]);

            }
        }

        static void factorial(int[] arr, int n)
        {
            if (n == 0) return;
            int carry = 0;
            for (int i = max - 1; i >= 0; --i)
            {
                arr[i] = (arr[i] * n) + carry;
                carry = arr[i] / 10;
                arr[i] %= 10;
            }
            factorial(arr, n - 1);
        }

        static void Main(string[] args)
        {
            int[] arr = new int[max];
            arr[max - 1] = 1;
            int num;
            Console.Write("Enter the number: ");
            num = int.Parse(Console.ReadLine());
            Console.Write("Factorial of " + num + " is: ");
            factorial(arr, num);
            display(arr);
        }
    }
}

you can find the source code at : http://codingloverlavi.blogspot.in/2013/03/here-is-one-more-interesting-program.html

#include<stdio.h>
#include<conio.h>
#include<iostream.h>
#include<time.h>
#define max 5000
void multiply(long int *,long int);
void factorial(long int *,long int);


int main()
{
clrscr();
cout<<"PROGRAM TO CALCULATE FACTORIAL OF A NUMBER";
cout<<"\nENTER THE NUMBER\n";
long int num;
cin>>num;

long int a[max];
for(long int i=0;i<max;i++)
    a[i]=0;

factorial(a,num);

clrscr();

//PRINTING THE FINAL ARRAY...:):):)
cout<<"THE FACTORIAL OF "<<num<<" is "<<endl<<endl;
long int flag=0;

int ans=0;
for(i=0;i<max;i++)
{
    if(flag||a[i]!=0)
    {
        flag=1;
        cout<<a[i];
        ans=ans+a[i];
    }
}

cout<<endl<<endl<<"the sum of all digits is: "<<ans;


getch();
return 1;
}

void factorial(long int *a,long int n)
{
long int lavish;
long int num=n;
lavish=n;
for(long int i=max-1;i>=0&&n;i--)
{
    a[i]=n%10;
    n=n/10;
}

for(i=2;i<(lavish);i++)
{
    multiply(a,num-1);
    num=num-1;

}
}


void multiply(long int *a,long int n)
{

for(long int i=0;i<max;i++)
    a[i]=a[i]*n;

for(i=max-1;i>0;i--)
{
    a[i-1]=a[i-1]+(a[i]/10);
    a[i]=a[i]%10;
}
}

You can't use these numbers at all without a BigInteger type.
No algorithm or procedure can squeeze numbers larger than 2⁶⁴ into a long.

You need to find a BigInteger implementation for .Net 3.5.