<< problem 118 - Pandigital prime sets | Square remainders - problem 120 >> |

# Problem 119: Digit power sum

(see projecteuler.net/problem=119)

The number 512 is interesting because it is equal to the sum of its digits raised to some power: 5 + 1 + 2 = 8, and 8^3 = 512.

Another example of a number with this property is 614656 = 28^4.

We shall define a_n 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 a_2 = 512 and a_10 = 614656.

Find a_30.

# Algorithm

A simple but extremely slow brute-force program revealed that a_30 has more than 10 digits:

I was iterating through numbers from 10 to 10,000,000,000 and didn't find enough terms a_i:

81, 512, 2401, 4913, 5832, 17576, 19683, 234256, 390625, 614656, 1679616, 17210368, 34012224, 52521875, 60466176, 205962976, 612220032, 8303765625, ...

Then I turned the whole problem upside-down: there are 90 two-digit numbers but only 18 different digit sums.

Even better: there are 9000 four-digit numbers but only 36 different digit sums !

Actually each digit is always between 0 and 9 therefore the maximum digit sum is \sum_i{digit_i} = 9i.

My program looks at all potential digit sums from 1 to 9*20 (I thought that maybe a_30 < 10^20, and that's actually true).

For each potential digit sum, I call them `base`

in my code, all exponents are computed until base^{exponent} overflows.

If digitSum(base^{exponent}) = base then a solution has been found.

Solutions will be found in a "random" order, so I add them to a sorted `std::set`

and read its 30th element.

## Modifications by HackerRank

The search space is much bigger: all numbers up to 10^100 (that's a Googol) have to be printed.

Even worse, numbers can be encoded in any base from 2 to 1000.

My `BigNum`

class was already able to store its digits in arbirary bases - but I always had powers of 10 in my mind.

Addition and multiplication is reduced to in-place operations to avoid slow memory allocations.

Pretty simple but effective is `BigNum::convert`

which converts a `BigNum`

to a different base.

# My code

… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too.

The code contains `#ifdef`

s to switch between the original problem and the Hackerrank version.

Enable `#ifdef ORIGINAL`

to produce the result for the original problem (default setting for most problems).

#include <iostream>
#include <set>
#include <climits>
//#define ORIGINAL

#ifdef ORIGINAL
// add all digits (base 10)

unsigned int digitSum(unsigned long long x)
{
unsigned int result = 0;
while (x > 0)
{
result += x % 10;
x /= 10;
}
return result;
}
int main()
{
std::set<unsigned long long> solutions;
// based on my experiments with BigNum I knew that the result fits in 64 bit
// which is about 10^20, each digit <= 9, therefore their sum <= 20*9
unsigned int MaxBase = 20 * 9;
// base is the sum of all digits
for (unsigned int base = 2; base <= MaxBase; base++)
{
unsigned int exponent = 1;
// step-by-step: base^exponent, then base^(exponent+1), ...
unsigned long long current = base;
while (current < ULLONG_MAX / base) // 1^64 - 1
{
auto sum = digitSum(current);
// digit sum equals base ? (note: single-digit numbers excluded)
if (sum == base && current >= 10)
solutions.insert(current);
// next iteration
current *= base;
exponent++;
}
}
// sorted results
auto i = solutions.begin();
// skip 30 - 1 = 29 elements
std::advance(i, 30 - 1);
// print the 30th
std::cout << *i << std::endl;
return 0;
}
#else
#include <vector>
// store single digits with lowest digits first
// e.g. 1024 is stored as { 4,2,0,1 } (when base = 10)

struct BigNum : public std::vector<unsigned int>
{
unsigned int maxDigit;
// store a non-negative number
BigNum(unsigned long long x = 0, unsigned int base = 10)
: maxDigit(base)
{
do
{
push_back(x % maxDigit);
x /= maxDigit;
} while (x > 0);
}
// add two big numbers
void operator+=(const BigNum& other)
{
// add in-place, make sure it's big enough
if (size() < other.size())
resize(other.size(), 0);
unsigned int carry = 0;
for (unsigned int i = 0; i < size(); i++)
{
carry += operator[](i);
if (i < other.size())
carry += other[i];
else
if (carry == 0)
return;
if (carry < maxDigit)
{
// no overflow
operator[](i) = carry;
carry = 0;
}
else
{
// yes, we have an overflow
operator[](i) = carry - maxDigit;
carry = 1;
}
}
if (carry > 0)
push_back(carry);
}
// multiply a big number by an integer
void operator*=(unsigned int factor)
{
unsigned long long carry = 0;
for (size_t i = 0; i < size(); i++)
{
carry += operator[](i) * (unsigned long long)factor;
operator[](i) = carry % maxDigit;
carry /= maxDigit;
}
// store remaining carry in new digits
while (carry > 0)
{
push_back(carry % maxDigit);
carry /= maxDigit;
}
}
// compare two big numbers
bool operator<(const BigNum& other) const
{
if (size() < other.size())
return true;
if (size() > other.size())
return false;
for (int i = (int)size() - 1; i >= 0; i--)
{
if (operator[](i) < other[i])
return true;
if (operator[](i) > other[i])
return false;
}
return false;
}
// convert to a different radix
BigNum convert(unsigned int newRadix) const
{
BigNum result(0, newRadix);
for (auto i = rbegin(); i != rend(); i++)
{
result *= maxDigit;
result += *i;
}
return result;
}
};
// add all digits

unsigned int digitSum(const BigNum& x)
{
unsigned int result = 0;
for (auto digit : x)
result += digit;
return result;
}
int main()
{
std::set<BigNum> solutions;
unsigned int radix = 10;
std::cin >> radix;
// do not exceed 10^100
BigNum googol(1, 10);
for (unsigned int digits = 1; digits <= 100; digits++)
googol *= 10;
// convert to current radix
BigNum max = googol.convert(radix);
// analyze all base^exponent below 10^100
// base is the sum of digits
for (unsigned int base = 2; base < (radix-1)*max.size(); base++)
{
unsigned int exponent = 1;
// step-by-step: base^exponent, then base^(exponent+1), ...
BigNum current(base, radix);
// still below a googol
while (current < max)
{
auto sum = digitSum(current);
// digit sum equals base ? single-digit numbers excluded
if (sum == base && current.size() >= 2)
{
// store result in decimal notation
BigNum decimal = current.convert(10);
solutions.insert(decimal);
}
// next iteration
current *= base;
exponent++;
}
}
// sorted results
for (auto i : solutions)
{
// print digits (note: they are stored in reverse)
for (auto j = i.rbegin(); j != i.rend(); j++)
std::cout << *j;
std::cout << " ";
}
return 0;
}
#endif

This solution contains 27 empty lines, 34 comments and 7 preprocessor commands.

# Interactive test

You can submit your own input to my program and it will be instantly processed at my server:

This live test is based on the Hackerrank problem.

This is equivalent to`echo 2 | ./119`

Output:

*Note:* the original problem's input `10`

__cannot__ be entered

because just copying results is a soft skill reserved for idiots.

*(this interactive test is still under development, computations will be aborted after one second)*

# Benchmark

The correct solution to the original Project Euler problem was found in less than 0.01 seconds on a Intel® Core™ i7-2600K CPU @ 3.40GHz.

(compiled for x86_64 / Linux, GCC flags: `-O3 -march=native -fno-exceptions -fno-rtti -std=c++11 -DORIGINAL`

)

See here for a comparison of all solutions.

**Note:** interactive tests run on a weaker (=slower) computer. Some interactive tests are compiled without `-DORIGINAL`

.

# Changelog

May 13, 2017 submitted solution

May 13, 2017 added comments

# Hackerrank

see https://www.hackerrank.com/contests/projecteuler/challenges/euler119

My code solves **20** out of **20** test cases (score: **100%**)

# Difficulty

Project Euler ranks this problem at **30%** (out of 100%).

Hackerrank describes this problem as **easy**.

*Note:*

Hackerrank has strict execution time limits (typically 2 seconds for C++ code) and often a much wider input range than the original problem.

In my opinion, Hackerrank's modified problems are usually a lot harder to solve. As a rule thumb: brute-force is never an option.

# Links

projecteuler.net/thread=119 - **the** best forum on the subject (*note:* you have to submit the correct solution first)

Code in various languages:

Python: www.mathblog.dk/project-euler-119-sum-of-digits-raised-power/ (written by Kristian Edlund)

Java: github.com/nayuki/Project-Euler-solutions/blob/master/java/p119.java (written by Nayuki)

Scala: github.com/samskivert/euler-scala/blob/master/Euler119.scala (written by Michael Bayne)

# Heatmap

green problems solve the original Project Euler problem and have a perfect score of 100% at Hackerrank, too.

yellow problems score less than 100% at Hackerrank (but still solve the original problem).

gray problems are already solved but I haven't published my solution yet.

blue problems are solved and there wasn't a Hackerrank version of it at the time I solved it or I didn't care about it because it differed too much.

*Please click on a problem's number to open my solution to that problem:*

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 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |

101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 |

126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 |

151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 |

176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 | 194 | 195 | 196 | 197 | 198 | 199 | 200 |

201 | 202 | 203 | 204 | 205 | 206 | 207 | 208 | 209 | 210 | 211 | 212 | 213 | 214 | 215 | 216 | 217 | 218 | 219 | 220 | 221 | 222 | 223 | 224 | 225 |

226 | 227 | 228 | 229 | 230 | 231 | 232 | 233 | 234 | 235 | 236 | 237 | 238 | 239 | 240 | 241 | 242 | 243 | 244 | 245 | 246 | 247 | 248 | 249 | 250 |

My username at Project Euler is

**stephanbrumme**while it's stbrumme at Hackerrank.

<< problem 118 - Pandigital prime sets | Square remainders - problem 120 >> |