The challenge

The number 89 is the first integer with more than one digit that fulfills the property partially introduced in the title of this challenge. What’s the use of saying “Eureka”? Because this sum gives the same number.

In effect: 89 = 8^1 + 9^2

The next number in having this property is 135.

See this property again: 135 = 1^1 + 3^2 + 5^3

We need a function to collect these numbers, that may receive two integers a, b that defines the range [a, b] (inclusive) and outputs a list of the sorted numbers in the range that fulfills the property described above.

Let’s see some cases (input -> output):

1
2
3

1, 10 -> [1, 2, 3, 4, 5, 6, 7, 8, 9]

1, 100 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 89]

If there are no numbers of this kind in the range [a, b] the function should output an empty list.

1

90, 100 --> []

The solution in C

Option 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <stddef.h>
#include <math.h>

typedef unsigned long long ull;

ull *sum_dig_pow(ull a, ull b, ull *results, size_t *length) {
    int place = 0;
    for (int i = a; i <= b; i++) {
        int k = 0;
        k = log10(i) + 1;
        if (pow((i % 10), k) > i) i = i + (10 - (i % 10));
        else {
            int op = i;
            int sum = 0;
            for (int m = k; m > 0; m--) {
                sum += pow(op % 10, m);
                op /= 10;
            }
            if (sum == i) {
                results[place] = i;
                place++;
            }
        }
    }
    *length = place;
    return results;
}

Option 2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include <stddef.h>

typedef unsigned long long ull;

ull *sum_dig_pow(ull a, ull b, ull *r, size_t *rl)
{
  // A032799
  static const ull A[20] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 89, 135, 175, 518, 598, 1306, 1676, 2427, 2646798, 12157692622039623539ull};
  size_t i;
  
  for(*rl = i = 0; i < 20 && A[i] <= b; i++) {
    if(a <= A[i]) { r[(*rl)++] = A[i]; }
  }
  
  return r;
}

Option 3:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

typedef unsigned long long ull;

ull *sum_dig_pow (ull a, ull b, ull *results, size_t *length) {
  char str [snprintf (NULL, 0, "%llu", b) + 1];
  
  for (*length = 0; a <= b; a++) {
    sprintf (str, "%llu", a);
    
    ull sum = 0;
    for (size_t digit = 0; digit < strlen (str); digit++)
      sum += (ull) pow (*(str + digit) - '0', digit + 1);
    
    if (sum == a)
      *(results + (*length)++) = a;
  }
  
  return results;
}

Test cases to validate our solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

#include <criterion/criterion.h>
#include <stddef.h>
#include <stdio.h>

typedef unsigned long long ull;

ull *sum_dig_pow(ull a, ull b, ull *results, size_t *length);
void tester(ull a, ull b, size_t e_len, ull expected[e_len]);

Test(sum_dig_pow, Sample_Tests) {
  {
    ull a = 1; ull b = 10;
    const ull expected[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    tester(a, b, 9, (ull *)expected);
  }
  {
    ull a = 1; ull b = 100;
    const ull expected[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 89};
    tester(a, b, 10, (ull *)expected);
  }
  {
    ull a = 10; ull b = 100;
    const ull expected[1] = {89};
    tester(a, b, 1, (ull *)expected);
  }
  {
    ull a = 90; ull b = 100;
    const ull *expected = NULL;
    tester(a, b, 0, (ull *)expected);
  }
  {
    ull a = 90; ull b = 150;
    const ull expected[1] = {135};
    tester(a, b, 1, (ull *)expected);
  }
  {
    ull a = 50; ull b = 150;
    const ull expected[2] = {89, 135};
    tester(a, b, 2, (ull *)expected);
  }
  {
    ull a = 10; ull b = 150;
    const ull expected[2] = {89, 135};
    tester(a, b, 2, (ull *)expected);
  }
}

void tester(ull a, ull b, size_t exp_len, ull expected[exp_len]) {
    ull results[exp_len];
    for(size_t i=0; i<exp_len; i++) {
        results[i] = rand() - rand();
    }
    size_t sub_len = 0;
    ull *submitted = sum_dig_pow(a, b, (ull *)results, &sub_len);
    if(sub_len != exp_len) {
        cr_assert_fail(
            "< Incorrect Output Length >\n \nSubmitted: %zu\nExpected:  %zu\n \n",
                                             sub_len,        exp_len
        );
    }
    for(size_t i=0; i<exp_len; i++) {
        if(submitted[i] != expected[i]) {
            char sub_str[7 * sub_len + 1];
            size_t s = 0, p = sprintf(sub_str, "{");
            while(s < sub_len)
                p += sprintf(sub_str + p, "%llu, ", submitted[s++]);
            sprintf(sub_str + p - 2, "}");          
            char exp_str[7 * exp_len + 1];
            size_t e = 0, q = sprintf(exp_str, "{");
            while(e < exp_len)
                q += sprintf(exp_str + q, "%llu, ", expected[e++]);
            sprintf(exp_str + q - 2, "}");
            cr_assert_fail(
                "< Incorrect Value(s) >\n \na = %llu\nb  = %llu\n \nSubmitted: %s\nExpected:  %s\n \n",
                                            a,        b,            sub_str,       exp_str
            );
        }
    }
    cr_assert(1);
}