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

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.

Posted by Kristian

14 comments

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?

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;

}

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

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.

Pretty much same 😀

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

Jean-Marie Hachey

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)

Jean-Marie Hachey

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

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.

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.

Antonio Sanchez

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;
      }
   }
}
Antonio Sanchez

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;
   }

}
Dhiren Chugh

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]);
}

}
}

Even Peng

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 Reply