135 lines
3.2 KiB
C
135 lines
3.2 KiB
C
/* The number 145 is well known for the property that the sum of the factorial of its digits is equal to 145:
|
|
*
|
|
* 1! + 4! + 5! = 1 + 24 + 120 = 145
|
|
*
|
|
* Perhaps less well known is 169, in that it produces the longest chain of numbers that link back to 169; it turns out that there are
|
|
* only three such loops that exist:
|
|
*
|
|
* 169 → 363601 → 1454 → 169
|
|
* 871 → 45361 → 871
|
|
* 872 → 45362 → 872
|
|
*
|
|
* It is not difficult to prove that EVERY starting number will eventually get stuck in a loop. For example,
|
|
*
|
|
* 69 → 363600 → 1454 → 169 → 363601 (→ 1454)
|
|
* 78 → 45360 → 871 → 45361 (→ 871)
|
|
* 540 → 145 (→ 145)
|
|
*
|
|
* Starting with 69 produces a chain of five non-repeating terms, but the longest non-repeating chain with a starting number
|
|
* below one million is sixty terms.
|
|
*
|
|
* How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?*/
|
|
|
|
#define _POSIX_C_SOURCE 199309L
|
|
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <time.h>
|
|
|
|
#define N 1000000
|
|
|
|
int factorial(int n);
|
|
int len_chain(int n);
|
|
|
|
int factorials[10] = {0};
|
|
int chains[N] = {0};
|
|
|
|
int main(int argc, char **argv)
|
|
{
|
|
int i, count = 0;
|
|
double elapsed;
|
|
struct timespec start, end;
|
|
|
|
clock_gettime(CLOCK_MONOTONIC, &start);
|
|
|
|
/* Simple brute force approach, for every number calculate
|
|
* the length of the chain.*/
|
|
for(i = 3; i < N; i++)
|
|
{
|
|
if(len_chain(i) == 60)
|
|
{
|
|
count++;
|
|
}
|
|
}
|
|
|
|
clock_gettime(CLOCK_MONOTONIC, &end);
|
|
|
|
elapsed = (end.tv_sec - start.tv_sec) + (double)(end.tv_nsec - start.tv_nsec) / 1000000000;
|
|
|
|
printf("Project Euler, Problem 74\n");
|
|
printf("Answer: %d\n", count);
|
|
|
|
printf("Elapsed time: %.9lf seconds\n", elapsed);
|
|
|
|
return 0;
|
|
}
|
|
|
|
/* Recursively calculate the factorial, of a number, saving the result
|
|
* so that it can be reused later.*/
|
|
int factorial(int n)
|
|
{
|
|
if(n == 0 || n == 1)
|
|
{
|
|
return 1;
|
|
}
|
|
else if(factorials[n] != 0)
|
|
{
|
|
return factorials[n];
|
|
}
|
|
else
|
|
{
|
|
factorials[n]=n*factorial(n-1);
|
|
return factorials[n];
|
|
}
|
|
}
|
|
|
|
int len_chain(int n)
|
|
{
|
|
int i, count = 0, finished = 0, value, tmp;
|
|
int chain[60];
|
|
|
|
value = n;
|
|
chain[count] = value;
|
|
|
|
while(!finished)
|
|
{
|
|
tmp = 0;
|
|
count++;
|
|
|
|
/* Generate the next number of the chain by taking
|
|
* the digits of the current value, calculating the
|
|
* factorials and adding them.*/
|
|
while(value != 0)
|
|
{
|
|
tmp += factorial(value % 10);
|
|
value /= 10;
|
|
}
|
|
|
|
/* If the chain length for the new value has already been
|
|
* calculated before, use the saved value (only chains for
|
|
* values smaller than N are saved).*/
|
|
if(tmp < N && chains[tmp] != 0)
|
|
{
|
|
return count + chains[tmp];
|
|
}
|
|
|
|
value = tmp;
|
|
|
|
/* If the current value is already present in the chain,
|
|
* the chain is finished.*/
|
|
for(i = 0; i < count; i++)
|
|
{
|
|
if(chain[i] == value)
|
|
{
|
|
finished = 1;
|
|
}
|
|
}
|
|
|
|
chain[count] = value;
|
|
}
|
|
|
|
chains[n] = count;
|
|
|
|
return count;
|
|
}
|