0
$\begingroup$

I'm trying to solve the 30th euler problem. My code is working, but I'm not sure if it's luck or ingeniousness.

To be the most efficient, I want to reduce at the maximum the numbers to checks.

I feel a solution, but not sure if it's true.

Given p as the power to use, I want to know what is the greatest possible sum of all powers of each digit of any number.

I use the formula below :

max(sum(d(x) pow P ) = (p+1)*(9 pow p) 

because

P = 2 : 3 * (9^2) = 243 > 99  // works P = 3 : 4 * (9^3) = 2916 > 999 // works P = 4 : 5 * (9^4) = 32805 > 9999 // works 

However, I don't know if it's true whichever P is, or if it's a coincidence. And I reduce my range correctly.

PS: I have no mathematics background, apologize, if my notation is not academic

1 Answers 1

1

You are thinking in the right direction. There is no maximum for a given power $p$, as even for $p=1$ a $100$ digit number could have a sum of $900$. The formula is the maximum sum of the $p^{\text{th}}$ powers of the digits of an $n$ digit number is $n*9^p$. The point of your intuition, and an important one for this problem, is that for large enough $n$ (depending on $p$) this will be smaller than the number. Taking $n=8, p=4$, the maximum sum of the fourth powers of the digits of an $8$ digit number is $8*9^4=52488,$ which has less than $8$ digits, so there are no solutions with $8$ digits in $4^{\text{th}}$ powers.

  • 1
    In general you get $10^{n-1} \leq n*9^p$, so whenever $p \leq \log_9 \frac{10^{n-1}}{n}$ there are no solutions.2011-12-16