Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 0 down vote accepted

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.

share|improve this answer
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. –  N. S. Dec 16 '11 at 14:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.