Programming Praxis

8 Responses to “Eureka”

1. Zack said

   September 24, 2019 at 9:19 AM

   Here is my take on it using Julia 1.1.1: https://pastebin.com/vw8CzNVC

   To be honest, I was expecting a few more Eureka numbers in this range. Anyway, good drill to warm up for some more challenging coding. Cheers!
2. kernelbob said

   September 24, 2019 at 3:05 PM

   >>> def is_eureka(n):
   ...     return sum(int(d)**i for (i, d) in enumerate(str(n), 1)) == n
   ... 
   >>> is_eureka(89)
   True
   >>> [i for i in range(1000000) if is_eureka(i)]
   [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 89, 135, 175, 518, 598, 1306, 1676, 2427]
   >>> len([i for i in range(1000000) if is_eureka(i)])
   18
   
3. bookofstevegraham said

   September 24, 2019 at 11:26 PM

   Here is my solution using Klong:

           l::1+&{[i]; i::0; x=+/{(1:$"",x)^i::i+1}'$x}'!1000000; .p(l); .p(#l);"Done"
   [1 2 3 4 5 6 7 8 9 10 90 136 176 519 599 1307 1677 2428]
   18
   "Done"
   
4. bookofstevegraham said

   September 24, 2019 at 11:51 PM

   I really should have proofread before I changed my solution starting with 1, to a solution starting with 0:

   Klong version

   Right
           l::1+&{[i]; i::0; x=+/{(1:$"",x)^i::i+1}'$x}'1+!999999; .p(l); .p(#l);""
   [1 2 3 4 5 6 7 8 9 89 135 175 518 598 1306 1676 2427]
   17
   ""
   ---
   Wrong
           l::1+&{[i]; i::0; x=+/{(1:$"",x)^i::i+1}'$x}'!1000000; .p(l); .p(#l);"Done"
   [1 2 3 4 5 6 7 8 9 10 90 136 176 519 599 1307 1677 2428]
   18
   "Done"
   ---
   Right
           l::&{[i]; i::0; x=+/{(1:$"",x)^i::i+1}'$x}'!1000000; .p(l); .p(#l); "Done"
   [0 1 2 3 4 5 6 7 8 9 89 135 175 518 598 1306 1676 2427]
   18
   "Done"
   
5. Daniel said

   September 25, 2019 at 2:55 AM

   Here’s a solution in C.

   #include <stdbool.h>
   #include <stdio.h>
   #include <stdlib.h>
   
   // exponentiation by squaring
   int ipow(int x, int y) {
     int result = 1;
     while (true) {
       if (y & 1) result *= x;
       y >>= 1;
       if (!y) break;
       x *= x;
     }
     return result;
   }
   
   bool is_eureka(int x) {
     int n = 0;  // number of digits
     int y = x;
     while (x) {
       ++n;
       x /= 10;
     }
     x = y;
     int sum = 0;
     for (int i = n; i > 0; --i) {
       int z = x % 10;
       sum += ipow(z, i);
       x /= 10;
     }
     return sum == y;
   }
   
   int main(void) {
     int count = 0;
     for (int i = 0; i < 1000000; ++i) {
       if (is_eureka(i)) ++count;
     }
     printf("%d\n", count);
     return EXIT_SUCCESS;
   }
   

   Output:

   18
   
6. Globules said

   September 28, 2019 at 6:57 AM

   Here’s a quick and dirty Haskell version.

   {-# LANGUAGE ScopedTypeVariables #-}
   
   import Data.List (foldl', unfoldr)
   import Data.Tuple (swap)
   
   -- The list of a number's digits.  The least significant digits are first.  The
   -- empty list represents 0.
   toDigits :: Integral a => a -> [a]
   toDigits n = unfoldr step n
     where step 0 = Nothing
           step i = Just $ swap $ i `quotRem` 10
   
   -- True iff n is a eureka number, where n is assumed to be >= 0.
   isEureka :: Integral a => a -> Bool
   isEureka n = let m = foldl' step 0 $ zip [1..] $ reverse $ toDigits n
                in m == n
     where step s (pow :: a, base :: a) = s + base^pow
   
   main :: IO ()
   main = do
     print $ length $ filter isEureka [0..999999 :: Int]
   

   $ ./eureka
   18
   
7. Paul said

   September 30, 2019 at 2:46 PM

   On the OEIS page on this series MAPLE code was given to calculate all these numbers faster. I translated the code into Python. It finds all numbers within 10 minutes an takes about 45 minutes to try all the numbers up to 22 digits (the maximum possible). The code uses a branch and bound strategy. The commented code and the output is on Ideone.

   def eureka1(ndigits):
       b = [[x ** (j+1) - x * 10 ** (ndigits - (j+1)) for x in range(10)]
            for j in range(ndigits)]
       smin = [min(bi) for bi in b]  # min value for every row of b
       smax = [max(bi) for bi in b]  # max value for every row of b
       perm = sorted(range(ndigits), key=lambda j: smax[j]-smin[j], reverse=True)
       scmin = [sum(smin[perm[i]] for i in range(j+1, ndigits)) for j in range(ndigits)]
       scmax = [sum(smax[perm[i]] for i in range(j+1, ndigits)) for j in range(ndigits)]
       b = [b[j] for j in perm]
   
       def branch():
           Q = [(0, 0, [])]
           while Q:
               pos, sofar, num = Q.pop()
               x0 = 1 if perm[pos] == 0 else 0
               for x in range(x0, 10):
                   current = sofar + b[pos][x]
                   if scmin[pos] <= -current <= scmax[pos]:
                       if pos == ndigits-1:
                           yield num + [x]
                       else:
                           Q.append((pos+1, current, num + [x]))
   
       for num in branch():
           decimal = sum(d*10**(ndigits-perm[i]-1) for i, d in enumerate(num))
           print(decimal)
   
   for ndigits in range(1, 25):
       eureka1(ndigits)
   
8. matthew said

   September 30, 2019 at 8:24 PM

   @Paul – thanks for posting that, I’d looked at the OEIS Maple code but couldn’t make head or tail of it, though I suspected it was doing something clever as you have revealed.