# A C program to find all factorions using a hash table

The objective of this program is to find all factorions, which are numbers equal to the sum of the factorials of their digits.

I am seeking suggestions on how to improve the performance of this code, as well as stylistic advice.

#include <stdio.h>
#include <stdlib.h>
#define base 10 //We are working in base 10
#define upper_bound 2540160 //This is 7 x 9! because a factorion can have at most seven digits.
//If it has d digits, it must satisfy the inequality 10^{d-1} < n <= 9!d, which isn't satisfied above d = 8
#define expected_no_of_answers 5 //I chose 5 somewhat arbitrarily. I knew beforehand there are only four answers in base 10

//Function prototype
void create_hash_table(int[]);
void get_fact_digit_sum(int[],int[]);

int main()
{
int hash_table_fact[base], answers[expected_no_of_answers]; //Creating a hash table where t[n] -> n!

create_hash_table(hash_table_fact);

return 0;
}

void create_hash_table(int hash_table_fact[])
{
int i = 1, fact = 1;
hash_table_fact = 1; //0! = 1

for(i = 1; i < base; i++)
{
fact = fact*i;
hash_table_fact[i] = fact;
}
}

void get_fact_digit_sum(int answers[], int hash_table_fact[])
{
int answerCount = 0, i = 1, temp, sum;

//Combing through the search space to search for factorions
for(i = 1; i <= upper_bound; i++)
{
temp = i;
sum = 0;
//Getting the sum of the factorials of the digits
while(temp != 0)
{
sum = sum + hash_table_fact[ (temp%base) ];
temp = temp/base;
}
if(sum == i)
{
}
}

//Placing a 0 at the end to mark the end of the array
}

{
int i;

for(i = 0; answers[i] != 0; i++)
{
}
}

• OK, so what do you expect to get out of this code review? – user633183 Feb 13 '17 at 23:45
• How to improve it in terms of performance and writing style. – user230452 Feb 14 '17 at 0:11
• @naomik I didn't state it explicitly because I thought it is understood in all questions on this site. – user230452 Feb 14 '17 at 0:12
• meta.codereview.stackexchange.com/questions/2436/… – user633183 Feb 14 '17 at 0:13

### You can use the previous sum to compute the next one

Your main loop computes the sum of factorials of digits from scratch for each number, but you are throwing away a lot of work from number to number. Think about two consecutive numbers, such as:

1234: sum = 1! + 2! + 3! + 4!
1235: sum = 1! + 2! + 3! + 5!


You can see that for 1235, it only differs from 1234 by the last digit, so you can compute its sum more quickly if you do this:

sum = previousSum + 5! - 4!


If the last digit wraps around from 9 to 0, you have to do the same thing with the next digit on the left:

1239: sum = 1! + 2! + 3! + 9!
1240: sum = 1! + 2! + 4! + 0!

sum  = previousSum;
sum += 0! - 9! // Ones digit
sum += 4! - 3! // Tens digit


If you reach a new power of 10, you need to do something a little different:

 99: sum =      9! + 9!
100: sum = 1! + 0! + 0!

sum  = previousSum;
sum += 0! - 9! // Ones digit
sum += 0! - 9! // Tens digit
sum += 1!      // Hundreds digit (note: do not subtract 0!)


### Sample rewrite

Using this idea, your function becomes this:

void get_fact_digit_sum(int answers[], int hash_table_fact[])
{
int answerCount = 0;
int sum         = 1;

// Combing through the search space to search for factorions
for (int i = 1; i <= upper_bound; i++) {
int temp = i;

while (1) {
int digit = temp % base;
if (digit == 0) {
sum += hash_table_fact - hash_table_fact[base-1];
temp /= base;
if (temp == 1) {
// Special case: reached new digit.
sum += hash_table_fact;
break;
}
} else {
sum += hash_table_fact[digit] - hash_table_fact[digit-1];
break;
}
}
if (sum == i) {
}
}

// Placing a 0 at the end to mark the end of the array