c - How to generate numbers upto 18 digits, sum of whose reciprocals is a whole number -

i looking way generate series of numbers sum of reciprocals whole number?

for eg - 11 (1/1 + 1/1 = 2 whole number), 122 (1/1+1/2+1/2 whole number), 236 (1/2 + 1/3 + 1/6 whole number) , likewise.

also want avoid repeat of same combination or permutation of digits. example, if 122 printed, don't want print 212 , 221.

i want know how approach problem

some thoughts started:

• your number can't contain zeros.
• you can add ones valid number , still valid.
• you don't need generate numbers. generate lists of digits instead. if keep list in ascending order, automatically solve problem of how eliminate permutations.
• each of true fractions 1/2 1/9 can represented expanded fraction common denominator 2520.

so following approach might work:

• start empty array , sum 0.
• now call generating function recursively. in each recursion, check wether sum divisible 2520 without remainder. if so, print number, , print numbers padded ones @ front until have 18 digits. 236 print 236, 1236, 11236 , on until 111 111 111 111 111 236.
• if array has length 18, don't recurse further. otherwise, call function after adding each of digits 2 9 list, don't use digits smaller last digit in list keep list sorted.
• don't recalculate sum, instead keep running sum: when recurse, add corresponding numerator sum: 1260 2, 840 3, 630 4 , on.

this bottom-up approach lot faster examining possible numbers. following program print 14,137 valid numbers (unordered, i.e. in order of generation) in fraction of second:

#include <stdlib.h> #include <stdio.h>  #define ndigit 18  void rec(int set[], int n, int sum) {     static int num[10] = {         0, 2520, 1260, 840, 630, 504, 420, 360, 315, 280     };      if (sum % 2520 == 0) {         (int j = 0; j < ndigit - n + 1; j++) {             (int = 0; < j; i++) putchar('1');             (int = 0; < n; i++) putchar(set[i] + '0');             putchar('\n');         }     }      if (n < ndigit) {         int i0 = n ? set[n - 1] : 2;          (int = i0; < 10; i++) {             set[n] = i;             rec(set, n + 1, sum + num[i]);         }     } }  int main() {     int set[ndigit];      rec(set, 0, 0);      return 0; } 

if need sorted output, convert set long integer, perhaps uint64_t <stdint.h> , store in array instead of printing them right away. sort array , print numbers.