A C program to find all factorions using a hash table

Question

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[]);
void display_answers(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);
 get_fact_digit_sum(answers,hash_table_fact);
 display_answers(answers);
 return 0;
}
void create_hash_table(int hash_table_fact[])
{ 
 int i = 1, fact = 1;
 hash_table_fact[0] = 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)
 {
 answers[answerCount++] = i;
 }
 }
 //Placing a 0 at the end to mark the end of the array
 answers[answerCount] = 0;
}
void display_answers(int answers[])
{
 int i;
 for(i = 0; answers[i] != 0; i++)
 {
 printf("%d\t",answers[i]);
 }
}

• Thank you: OK, so what do you expect to get out of this code review?
• Saikat: How to improve it in terms of performance and writing style.
• Saikat: @naomik I didn't state it explicitly because I thought it is understood in all questions on this site.
• Thank you: meta.codereview.stackexchange.com/questions/2436/…

Answer 1

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[0] - hash_table_fact[base-1];
 temp /= base;
 if (temp == 1) {
 // Special case: reached new digit.
 sum += hash_table_fact[1];
 break;
 }
 } else {
 sum += hash_table_fact[digit] - hash_table_fact[digit-1];
 break;
 }
 }
 if (sum == i) {
 answers[answerCount++] = i;
 }
 }
 // Placing a 0 at the end to mark the end of the array
 answers[answerCount] = 0;
}

The new way ran 4x faster than the old way for the given upper bound. If you extend the upper bound to 100 million (even though there are no answers that high), the new way runs 8x faster than the old way.

• Saikat: Fantastic idea ! Have you done this before ? Thanks a lot.
• Saikat: Are you a mathematician ?
• JS1: @user230452 I used this technique before for some other problem similar to this one. No I'm not a mathemetician. Here, I found the similar question that used the same technique to solve.
• Saikat: Well done. I will implement this technique on another program and upload it soon and it's very similar to the question you linked. You can check it out and give your comments.
• Saikat: I encountered this kind of problem (requiring sum of digits) and variations for the first time in eight grade. (About 8 years back.) Every time I get this kind of problem, I just think of the same thing. This thought of optimizing it never occurred to me. Thanks !