Problem 122

[APFetus]

Surprised there wasn't one for this yet. Problem 122 (View Problem) (link fixed by moderator)

I can't figure out what's wrong with my code. Any ideas? I've manually checked for all exponents up to 20 and it looks good.

Some checks:
Sum of 26 for the exponents up to (and including) 10.
Sum of 75 for the exponents up to (and including) 20.
The first exponent w/ 6 multiplications is 19.
The first exponent w/ 10 multiplications is 127.
All exponents equal to or below 200 can be solved with 10 multiplications.

I did my program in Java if someone would like to look over it.

[jaap]

All exponents equal to or below 200 can be solved with 10 multiplications.

This is not true, though your other statements were.

[APFetus]

Thanks jaap, I believe I see the problem. I wasn't tracking the actual path to arrive at a solution, only the list of its descendants.

Did you have to track all possible paths for each exponent? That seems fairly intensive as the number of paths get exponentially larger.

[Waldovski]

Can someone please tell me why the sequence for 77 isn't
77 55 44 22 11 9 6 3 2 1?

[rayfil]

Because it can be done in less than 10.

[Waldovski]

That is less than 10. It's 9. I know what it's supposed to be. You can easily get the answer from 3313 if you know what I mean. I just don't want to put the answer in before I've understood it. The algorithm I came up with gets every single value correct except 77 (and consequently 154). I don't understand why.

[TripleM]

He meant less than 9. The answer for that particular case happens to be posted in the forum for the problem; it shouldn't really be discussed on the public forum.

[utomaya]

Can someone please tell me why the sequence for 77 isn't
77 55 44 22 11 9 6 3 2 1?

There are some sequences shorter than yours
Here is one of them
1, 2, 4, 5, 9, 18, 36, 72, 77

[JMW1994]

How come I can find that you can actually compute n¹⁵ four rather than five times? I tend to get
n*n=n²
n²*n²=n⁴
n⁴*n⁴=n⁸
n⁸*n⁷=n¹⁵

Something must be wrong.

[TripleM]

How did you calculate n^7 without any extra multiplications?

[may3]

Waldovski wrote "" That is less than 10. It's 9. I know what it's supposed to be. You can easily get the answer from 3313 if you know what I mean. I just don't want to put the answer in before I've understood it. The algorithm I came up with gets every single value correct except 77 (and consequently 154). I don't understand why.""

I also facing the same problem and unable to figure out....
Can anyone please give some hint?????? please...........

[solarmew]

hmmmmmm... i have a theory about this, but something's not working ... not sure if the theory is wrong or the code...

could you tell me if the following are right?
sum of the first numbers 1-30 is 136
m(193) = 9

if they are, could I PM someone with the theory?

[dawghaus4]

hmmmmmm... i have a theory about this, but something's not working ... not sure if the theory is wrong or the code...

could you tell me if the following are right?
sum of the first numbers 1-30 is 136
m(193) = 9

if they are, could I PM someone with the theory?

The sum is incorrect.

m(193) is correct.

Tom

[RishadanPort]

Is m(1) considered 0 or 1?

I'm assuming 0 becomes you don't need any multiplication

[RobertStanforth]

Is m(1) considered 0 or 1?

I'm assuming 0 becomes you don't need any multiplication

Yes, your reasoning is correct.

[5040]

I have a problem. I made a program that computes powers, in a way I thought was fast. I'm more or less a beginner in programming. I started at the end of last year, then had a large gap between starting again recently. Point is, I'm not experienced enough, I don't think, and have probably made a mistake somewhere.

Anyway, I can compute m(193) in one less multiplication, than the accepted result of 9:
So here we have 2 to the power of 193.
2
8
8
64
4096
16777216
281474976710656
79228162514264337593543950336

which equals:
12554203470773361527671578846415332832204710888928069025792

Where am I going wrong?

[mdean]

I'm not entirely sure this is appropriate for this forum. First, I'm guessing that first 8 should be a 4. Secondly, I don't see how you get from the line before "which equals" to the line after. From what I can see, the line before has taken you 7 multiplications and I don't see how you're arriving at the result without at least 2 more.

[5040]

Never mind, guess I was a bit too tired. I put the print in the wrong place in the code. It should have been:

2*2
4*2
8^2
64^2
4096^2
16777216^2
281474976710656^2
79228162514264337593543950336^2
6277101735386680763835789423207666416102355444464034512896*2

So I get 9 multiplications.

[PierrotLeFou]

Maybe the statement was unclear for me.
Should I compute the sum of all M(k) for k = 1 to 200 included?
My answer for M(200) is 10 and for M(15) is 6 because I count the "1" at the beginning. Otherwise everything seems to be fine.
I'm surprized that my code is rather fast (I use a recursive solution).
edit: Indeed, I have to do the sum of all M(k) and I got the right answer.
I didn't check the execution time but it's very fast.