How to generate numbers upto 18 digits, sum of whose reciprocals is a whole number [closed]

by

Some thoughts to get you started:

  • Your number can’t contain zeros.
  • You can always add ones to a valid number and it will still be valid.
  • You don’t need to generate numbers. Generate lists of digits instead. If you keep the list in ascending order, you will automatically solve to problem of how to eliminate permutations.
  • Each of the true fractions 1/2 to 1/9 can be represented as an expanded fraction with the common denominator 2520.

So the following approach might work:

  • Start with an empty array and the sum 0.
  • Now call your generating function recursively. In each recursion, check wether the sum is divisible by 2520 without remainder. If so, print that number, and also print all numbers padded with ones at the front until you have 18 digits. So for 236 print 236, 1236, 11236 and so on until 111 111 111 111 111 236.
  • If your array has length 18, don’t recurse further. Otherwise, call your function after adding each of the digits 2 to 9 to your list, but don’t use digits that are smaller than the last digit in the list to keep the list sorted.
  • Don’t recalculate the sum, but instead keep a running sum: When you recurse, add the corresponding numerator to the sum: 1260 for 2, 840 for 3, 630 for 4 and so on.

This bottom-up approach is a lot faster than examining all possible numbers. The following program will print all 14,137 valid numbers (unordered, i.e. in order of generation) in the fraction of a 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) {
        for (int j = 0; j < NDIGIT - n + 1; j++) {
            for (int i = 0; i < j; i++) putchar('1');
            for (int i = 0; i < n; i++) putchar(set[i] + '0');
            putchar('\n');
        }
    }

    if (n < NDIGIT) {
        int i0 = n ? set[n - 1] : 2;

        for (int i = i0; i < 10; i++) {
            set[n] = i;
            rec(set, n + 1, sum + num[i]);
        }
    }
}

int main()
{
    int set[NDIGIT];

    rec(set, 0, 0);

    return 0;
}

If you need sorted output, convert the set to a long integer, perhaps uint64_t from <stdint.h> and store it in an array instead of printing them right away. Then sort the array and print the numbers.

More Related Contents:

  1. Recursive and non-recursive traversal of three degree tree
  2. Why this C code makes infinite loop?
  3. Finding target sum of two numbers in array
  4. The most efficient way to implement an integer based power function pow(int, int)
  5. Efficient Algorithm for Bit Reversal (from MSB->LSB to LSB->MSB) in C
  6. What integer hash function are good that accepts an integer hash key?
  7. hash function for string
  8. How to reverse a singly linked list using only two pointers?
  9. Unique random number generation in an integer array [duplicate]
  10. Calculating factorial of large numbers in C
  11. Combine Gyroscope and Accelerometer Data
  12. Building a logarithm function in C without using float type
  13. How can I simplify this working Binary Search code in C?
  14. Power by squaring for negative exponents
  15. Explain this snippet which finds the maximum of two integers without using if-else or any other comparison operator?
  16. C How to “draw” a Binary Tree to the console [closed]
  17. How to do unsigned saturating addition in C?
  18. Traverse Matrix in Diagonal strips
  19. C – How to implement Set data structure?
  20. Correctness of Sakamoto’s algorithm to find the day of week
  21. Why prefer start + (end – start) / 2 over (start + end) / 2 when calculating the middle of an array?
  22. Rolling median in C – Turlach implementation
  23. Rolling median algorithm in C
  24. Find maximum of three number in C without using conditional statement and ternary operator
  25. Algorithm to find all the exact divisors of a given integer
  26. Which is better way to calculate nCr
  27. Finding the intersecting node from two intersecting linked lists
  28. Merging two sorted linked lists
  29. Extend a line segment a specific distance
  30. QuickSort and Hoare Partition

Leave a Comment