Project Euler 119: Investigating the numbers which are equal to sum of their digits raised to some power

Project Euler 119: Investigating the numbers which are equal to sum of their digits raised to some power

Written by on 20 October 2012

Topics: Project Euler

Problem 119 of Project Euler reads

The number 512 is interesting because it is equal to the sum of its digits raised to some power: 5 + 1 + 2 = 8, and 83 = 512. Another example of a number with this property is 614656 = 284.

We shall define an to be the nth term of this sequence and insist that a number must contain at least two digits to have a sum.

You are given that a2 = 512 and a10 = 614656.

Find a30.

To be honest I have a bit of a bad feeling about the solution for this as it is based a whole lot on heuristics and guess when choosing the parameters. But lets give it a spin and see where we end up.

I saw two approaches for this. Either we go through each number and see if their digit sum can be raised to a power such that it is equal to the number. Or we go the other way around and see raise smaller numbers to different powers and check their digit sum. I had a feeling that the number we are looking for here is pretty large. So taking the first approach would probably be infeasible due to the time of computation. So I took the other route.

We have already been over the code idea, so let us just go through it

 List<BigInteger> a = new List<BigInteger>();
            
for (int b = 2; b < 400; b++) {
    BigInteger value = b;
    for (int e = 2; e < 50; e++) {
        value *= b;

        if (DigitSum(value) == b) {
            a.Add(value);            
        }
        if (a.Count > 50) break;                    
    }
    if (a.Count > 50) break;                    
}

You can see now that I have chosen the limits for the base and exponent at random. Furthermore I have decided to find the first 50 numbers. The reason I decided to go above 30 is the fact that we cannot be sure to find them in the right order.

Just take the first three we find which are 74= 2401, 83= 512, 92= 81 which are a3, a2 and a1.

Wrapping up

In order to run this code we need the DigitSum method, which you can find in the source code. Running this piece of code can be done in just under 60ms. so it is pretty fast. And we will get the result

a30 is 248155780267521

I really wanted to provide a better solution for this one, but I had to give up. If we go the way with generating power we need to run into the billions squared in order to ensure that nothing is smaller than the actual solution.

So if you have a better solution for this, please let me know.

14 Comments For This Post I'd Love to Hear Yours!

  1. billy says:

    i gotta give it to ya man for sticking with it for so long. I need to get back on track but I got people tellin me to learn F# not C#. What;s your thoughts on this?

  2. Eman says:

    Hi, I have pretty much the same solution for this problem, just different limits.

    #include <iostream>
    #include <ctime>
    #include <algorithm>
    #include <vector>
    
    
    
    
    
    using namespace std;
    
    
    typedef unsigned long long Long;
    const Long LIMIT = (Long)-1 / 2;
    
    int sumOfDigits(Long number);
    
    int main()
    {
    
    
        time_t start = clock();
    
    
         
         
         
        vector<Long> values;
        for(Long number = 2; number < 100; number++)
        {
            for(Long power = number * number; power <= LIMIT && power != 0; power *= number)
            {
              
                if(sumOfDigits(power) == number)
                {
                    values.push_back(power);
                }
            }
        }
    
         
         sort(values.begin(), values.end());
         for(int i = 0;i<30;i++)
              cout<<values[i]<<endl;
    
        cout<<"Project Euler 119:\t"<<values[29]<<endl;
        cout<<"PROGRAM LAST:\t"<<(clock() - start)<<endl;
    
    
    }
    
    int sumOfDigits(Long number)
    {
    
        int sum = 0;
        while(number != 0)
        {
            sum += number % 10;
            number /=10;
        }
    
        return sum;
    
    }
    
  3. Kristian says:

    Hi Billy

    Thanks first of all, the thing that has got me going for so long is this website. The feedback I get is what have kept the spirit up. The answer the question whether to learn C# or F# is one of those “it depends” answers. I don’t think you can really that one is better than the other. They are different languages with different strengths. Learning both will give you a whole lot of insights in a lot of things.
    I can advice you to listen to .net rocks episode 803 there they discuss speaking multiple languages.

    /Kristian

  4. Kristian says:

    Hi Eman

    As I mentioned, the limits were chosen more or less randomly. So in that regard I am not really surprised yours a different. Otherwise nice solution.

  5. Eman says:

    Pretty much same 😀

  6. billy says:

    ok thank you Kristian. I am a big fan of podcasts :). I am listening now

  7. Jean-Marie Hachey says:

    Project Euler Problem 119 was posted on April 7, 2006.
    http://projecteuler.net/problem=119

    Thanks to Kristian for this impressive C# solution of this problem.

    Some results calculated with Kristian’s algorithm.

    a1=81 (9^2)
    a2=512 (8^3)
    a3=2401 (7^4)
    a4=4913 (17^3)
    a5=5832 (18^3)
    a6=17576 (26^3)
    a7=19683 (27^3)
    a8=234256 (22^4)
    a9=390625 (25^5)
    a10=614656 (28^4)
    a20=24794911296 (54^6)
    a30=248155780267521 (63^8)

  8. Jean-Marie Hachey says:

    Hi Kristian,

    Just 2 points concerning Project Euler Problem 119.

    ______

    Point 1 :

    Adding these 2 lines :
    Console.WriteLine(“Problem119”);
    Console.ReadLine();

    After this one :
    Console.WriteLine(“Solution took {0} ms”, clock.Elapsed.TotalMilliseconds);

    Will give access to the results for a period of time as long as required by the user.
    (Without this change, the results appear just a few ms on my computer).

    ___

    Point 2 :

    Actual line :

    int[] perm = new int[] {1,2,3,4,5,6,7,8,9};

    This simplified line gives the same results :

    int[] perm = new int[] {1};

    ______

    Thanks again for this code.
    More comments to come on the results.

    Jean-Marie

  9. Kristian says:

    Regarding point 1. On my computer the console stays up after the program has run. Which is why I never bothered to add something like that. Otherwise I would have to press the keyboard twice.

    Regarding point 2. It is because the variable is never used. It is a leftover from a previous problem. So the correct solution is to delete it all together. That is done now in the downloadable source code.

  10. Orchisama says:

    I have an idea about the limits. Let us assume that our base is x and the exponent is n. I had solved this on Hackerrank and they specifically mentioned the upper limit of x^n to be 10^100.

    So I worked with the constraints 10 < x^n < 10^100. If I knew the range of x, I could solve for n's range using logarithms. So I saw that the max value of sum of digits of x^n could be 9+9+….9 (99 times) = 891 (comes from upper limit 10^100). Since we are looking for a solution where (sum of digits of x^n) = x, and maximum sum of digits was 891, therefore x must be lesser than or equal to 891. I finally took the range of x as 2<=x<=891, and calculated n as:

    1/log x <= n <= 100/log x (logarithms have a base of 10).

    It worked for me, so I am guessing this method was correct, but you need to know the upper limit or take a guess.

  11. Antonio Sanchez says:

    You can generate numbers a^b in order by keeping track of “potential” next numbers in a priority queue, sorted in increasing order. Start with 2^2=4 in the queue, and the next smallest exponent k=3. The next number is either the top of the queue, or 2^k. If the top of the queue is smaller, check if it satisfies the digit-sum condition, and add (a+1)^b to the queue. Otherwise, add 3^k to the queue, and set k:=(k+1).

    This is much slower than your provided solution, since it constantly adds/removes from a priority queue. However, you are guaranteed to find the sequence in order, so can terminate as soon as you find 30 elements.

    typedef unsigned long long vtype;
    typedef pair<pair<size_t, size_t>, vtype> etype;
    
    void euler119(size_t N) {
       // increasing powers
       auto compare_second = [](const etype& e1, const etype& e2) { return e1.second > e2.second;};
       auto queue = priority_queue<etype, vector<etype>, decltype(compare_second)>(compare_second);
    
       // start with 2^2
       queue.push({{2, 2}, 4});
    
       // next possible exponent: 3
       etype nextk = {{2, 3}, 8};
    
       // output sequence
       vector<etype> seq;
       seq.reserve(N);
    
       // increment either base or exponent, finding next largest number
       while (seq.size() < N) {
          const etype& top = queue.top();
    
          size_t base;
          size_t exp;
          vtype val;
          if (top.second < nextk.second) {
             // entry in queue was smaller
             base = top.first.first;
             exp = top.first.second;
             val = top.second;
             queue.pop();
          } else {
             // 2^k was smaller
             base = nextk.first.first;
             exp = nextk.first.second;
             val = nextk.second;
             // next k
             nextk = {{2, exp+1}, pow<vtype>(2, exp+1)};
          }
          etype next = {{base+1, exp}, pow<vtype>(base+1, exp)};
          queue.push(std::move(next));
    
          auto dsum = digit_sum(val);
          if (dsum == base) {
             seq.push_back({{base, exp}, val});
             cout << base  << "^" << exp << "=" << val << std::endl;
          }
       }
    }
    
  12. Antonio Sanchez says:

    A better way to guarantee you don’t miss any numbers is to consider c=a^b in increasing number of digits of c. Start with k=2 digit numbers, and increase k until you have enough numbers in your sequence. You know the maximum base a is the maximum sum of k digits = 9k. The minimum base is always 2. The minimum exponent to generate a k-digit number is (k-1)/log10(a), and you keep increasing exponents until you have formed a k+1 digit number. Finally, you need to sort your sequence.

    typedef unsigned long long vtype;
    typedef pair<pair<size_t, size_t>, vtype> etype; // a^b=c
    
    void euler119b(size_t N) {
    
       vector<etype> seq;
       seq.reserve(2*N);  // reserve some extra room just in case
    
       // consider number of digits k
       // c = a^b;
       size_t k = 2;
       vtype maxc = 100;
       vtype minc = 10;
       while (seq.size() < N) {
    
          // maximum base is lesser of sum of k-digits or sqrt(maxc)
          size_t maxa = min<size_t>(k*9, sqrt(maxc)+1);
    
          // loop through possible bases
          for (size_t a=2; a<=maxa; ++a) {
             // exponent
             size_t minb = (k-1)/(log10(a)+1);  // conservative
             size_t b = minb;
             vtype c = pow<vtype>(a, minb);
             while (c < maxc) {
                if (c >= minc) {
                   auto dsum = digit_sum(c);
                   if (dsum == a) {
                      seq.push_back({{a, b}, c});
                   }
                }
                c *= a;
                ++b;
             }
          }
    
          // one more digit
          ++k;
          maxc *= 10;  
          minc *= 10;
       }
    
       // sorted order
       auto compare_second = [](const etype& e1, const etype& e2) { return e1.second < e2.second;};
       std::sort(seq.begin(), seq.end(), compare_second);
    
       for (const auto& e : seq) {
          cout << e.first.first  << "^" << e.first.second << "=" << e.second << std::endl;
       }
    
    }
    
  13. Dhiren Chugh says:

    I am getting the answer here. But the thing is the answer 248155780267521 does not lie in the right order.
    Here is my code. As I am a complete beginner , please ignore my style of coding.
    using System;

    class DigitPowerSum1
    {
    public static ulong[] nums= new ulong[30];
    public ulong[] DigPowSum()
    {

    ulong i, count = 0, powexp = 0, sum, j, p, ind = 0, a;
    ulong[] spd = new ulong[30];
    char[] c;
    string s = “”;

    for (i = 2; i <= 400 && count < 60; i++)
    {

    for (j = 2; j <= 200; j++)
    {
    powexp = (ulong)(Math.Pow(i, j));

    s = powexp + "";
    c = s.ToCharArray();
    sum = 0;
    for (int k = 0; k 0)
    {
    if (sum == i)
    {

    spd[ind] = i;
    nums[ind] = powexp;
    ind++;

    count++;

    }
    }

    if (count == 30)
    {
    break;
    }

    }
    }

    return spd;
    }
    }

    class Test
    {

    public static void Main()
    {
    DigitPowerSum1 obj = new DigitPowerSum1();
    ulong[] spd = obj.DigPowSum();

    ArraySorting obj1 = new ArraySorting();
    obj1.ArraySort(DigitPowerSum1.nums);
    obj1.ArraySort(spd);

    Console.WriteLine(spd[29]);
    Console.WriteLine(DigitPowerSum1.nums[29]);
    Console.WriteLine();
    for (int i = 0;i<= DigitPowerSum1.nums.Length-1;i++)
    {
    Console.WriteLine(DigitPowerSum1.nums[i]);
    }

    Console.WriteLine();

    for (int i = 0; i <= spd.Length – 1; i++)
    {
    Console.WriteLine(spd[i]);
    }

    }
    }

  14. Even Peng says:

    I have a solution and only takes about 135 us on my MBPR 15″ using Golang. Since highlight of Golang is not supported in this comment, please go to my github page.
    https://github.com/EvenPeng/Project-Euler-using-Golang/blob/master/p119.go

    I use a integer array to store the power of each base and base is its index. Since the power of 2 will always be the minimum values, I first update the power of 2 first in each round. Then, append the possible bases to the end of the array (line 46 – 52). Finally, update the array from 3 to the end of the array (line 54 – 63). The sequence is generated in ordered list.

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.