82 lines
2.6 KiB
C
82 lines
2.6 KiB
C
#include <stdio.h>
|
|
|
|
const int digits[] = { 0,1,2,3,4,5,6,7,8,9 };
|
|
|
|
// calculates factorial of a number
|
|
int factorial(int n) {
|
|
return n == 0 ? 1 : n * factorial(n - 1);
|
|
}
|
|
|
|
// returns sum of squares of digits of n
|
|
unsigned int sum_square_digits(unsigned int n) {
|
|
int i,num=n,sum=0;
|
|
// process digits one at a time until there are none left
|
|
while (num > 0) {
|
|
// peal off the last digit from the number
|
|
int digit=num % 10;
|
|
num=(num - digit)/10;
|
|
// add it's square to the sum
|
|
sum=sum+digit*digit;
|
|
}
|
|
return sum;
|
|
}
|
|
|
|
// builds all combinations digits 0-9 of length len
|
|
// for each of these it will perform iterated digit squaring
|
|
// and for those which result in 89 add to a counter which is
|
|
// passed by pointer.
|
|
long choose_sum_and_count_89(int * got, int n_chosen, int len, int at, int max_types, int *count89)
|
|
{
|
|
int i;
|
|
long count = 0;
|
|
int digitcounts[10];
|
|
for (i=0; i < 10; i++) {
|
|
digitcounts[i]=0;
|
|
}
|
|
if (n_chosen == len) {
|
|
if (!got) return 1;
|
|
|
|
int sum=0;
|
|
for (i = 0; i < len; i++) {
|
|
int digit=digits[got[i]];
|
|
digitcounts[digit]++;
|
|
sum=sum + digit * digit;
|
|
}
|
|
if (sum == 0) {
|
|
return 1;
|
|
}
|
|
if ((sum != 1) && (sum != 89)) {
|
|
while ((sum != 1) && (sum != 89)) {
|
|
sum=sum_square_digits(sum);
|
|
}
|
|
}
|
|
if (sum == 89) {
|
|
int count_this_comb=factorial(len);
|
|
for (i=0; i<10; i++) {
|
|
count_this_comb/=factorial(digitcounts[i]);
|
|
}
|
|
(*count89)+=count_this_comb;
|
|
}
|
|
|
|
return 1;
|
|
}
|
|
|
|
for (i = at; i < max_types; i++) {
|
|
if (got) got[n_chosen] = i;
|
|
count += choose_sum_and_count_89(got, n_chosen + 1, len, i, max_types, count89);
|
|
}
|
|
return count;
|
|
}
|
|
|
|
int main(void)
|
|
{
|
|
int chosen[10];
|
|
int count=0;
|
|
// build all unique 8 digit combinations which represent
|
|
// numbers 0-99,999,999 and count those
|
|
// whose iterated digit squaring sum to 89
|
|
// case 0, 100,000,000 are ignored since they don't sum to 89
|
|
choose_sum_and_count_89(chosen, 0, 8, 0, 10, &count);
|
|
printf("%d\n",count);
|
|
return 0;
|
|
}
|