Problem 356

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
User avatar
BostonBear
Posts: 17
Joined: Thu Apr 28, 2011 3:48 am
Location: Saugus, MA

Problem 356

Post by BostonBear » Sun Oct 30, 2011 6:55 am

I've been calculating the roots of the given polynomial. which I realize is just the easy part of the battle.

however with Python, I am having issues calculating proper answers for n=19 and above.. i've tried Newton's method and the trigonometric method and I get the same answers. Yet when I plug them into the original equation, my answers are off. for example, instead of 0 I get 3 for n=19 when I plug the root into the polynomial. Obviously this is a rounding error. By using python on a mac does that mean this problem is impossible for me to solve on this machine? It gets worse as I work my way up to n = 30. I had installed mpmath at one point but for some reason it just decided not to work any longer. Using python am I doomed to failure trying to solve this problem or do I need or do I need to install something like numpy to have a chance with this problem. At first I thought this would be a piece of cake but now I think its a pain in the u know what. Any suggestions? they'd be greatly appreciated.

Mike

sivakd
Posts: 217
Joined: Fri Jul 17, 2009 8:37 am
Location: California, USA
Contact:

Re: Problem 356 and precision issues

Post by sivakd » Sun Oct 30, 2011 7:04 am

There are a few solutions in Python. People even solved it using C/C++. Yeah, it wasn't as piece of a cake as it seemed, but this is once again about knowing the right method to solve this.
Image
puzzle is a euphemism for lack of clarity

CJKay93
Posts: 3
Joined: Sun Oct 30, 2011 2:00 pm

Re: Problem 356 and precision issues

Post by CJKay93 » Sun Oct 30, 2011 3:55 pm

I'm hardly a mathematician, but I've been working on this for the past day or so and I'm having some real problems.
I am having some major breakdown trying to get my head around how accurate all the arithmetic in this question needs to be to get the correct answer. My program can successfully calculate each largest root (checked against Wolfram Alpha), but the part I think I am going wrong on is trying to sum a_i^987654321.

It seems logical to me that the sum need only be the sum of the last 8 digits of a_i, considering the following example...
Assuming we want the last 2 digits:
21^1 = 21
21^2 = 441
21^3 = 90261
21^4 = 194481

21 + 41 + 61 + 81 = 204
Which proves the last 2 digits of 21^1 + 21^2 + 21^3 + 21^4 are 0 and 4:
21^1 + 21^2 + 21^3 + 21^4 = 204204 (the 2 before 04 is coincidence)

For anyone that is stuck on that part, there are ways of getting the last two digits of n^e without actually calculating n^e (I presume I can't mention the method on here)

So, I'm past getting the last 8 digits of each a_i^987654321, but the result I am getting is still apparently wrong (13499170 from 1313499170), and I'm wondering if I've missed something or misread the question... please help! I've been racking my brains for hours. :(
Image

User avatar
hk
Administrator
Posts: 10482
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: Problem 356 and precision issues

Post by hk » Sun Oct 30, 2011 7:52 pm

And now try the same with the integer part of 20.999^n, writing out the full answer first.
See how fast this deviates?
So the answer cannot be calculated with floating point aritmetic.
Image

CJKay93
Posts: 3
Joined: Sun Oct 30, 2011 2:00 pm

Re: Problem 356 and precision issues

Post by CJKay93 » Sun Oct 30, 2011 8:16 pm

So what, are we meant to floor or round a_i before a_i^987654321? I've just done what the problem seems to want.
Then again, I've never really studied any number theory in my life so I had to do a lot of research just to find out how to get the roots of the equation.
Image

mynameisalreadytaken
Posts: 20
Joined: Sun Sep 25, 2011 10:20 pm

Re: Problem 356 and precision issues

Post by mynameisalreadytaken » Sun Oct 30, 2011 9:10 pm

It's up to you to find a way to solve the problem. It's the point of the problem, that a simple brute force approach doesn't work.
Image

sivakd
Posts: 217
Joined: Fri Jul 17, 2009 8:37 am
Location: California, USA
Contact:

Re: Problem 356 and precision issues

Post by sivakd » Sun Oct 30, 2011 9:29 pm

CJKay93 wrote:So what, are we meant to floor or round a_i before a_i^987654321?
No, the problem statement requires not taking floor/round of a_i before the power. So, for example, for the given a_2 of 3.86619826..., if the power had been 5, the result of floor(a_2^5) would be 863 and not 243.
Image
puzzle is a euphemism for lack of clarity

CJKay93
Posts: 3
Joined: Sun Oct 30, 2011 2:00 pm

Re: Problem 356 and precision issues

Post by CJKay93 » Sun Oct 30, 2011 10:37 pm

sivakd wrote:
CJKay93 wrote:So what, are we meant to floor or round a_i before a_i^987654321?
No, the problem statement requires not taking floor/round of a_i before the power. So, for example, for the given a_2 of 3.86619826..., if the power had been 5, the result of floor(a_2^5) would be 863 and not 243.
Oh, well in that case that's what I've no idea what I'm doing wrong lol.
EDIT: Never mind, I deciphered what you wrote and I think I caught on :P.
Image

User avatar
BostonBear
Posts: 17
Joined: Thu Apr 28, 2011 3:48 am
Location: Saugus, MA

Re: Problem 356 and precision issues

Post by BostonBear » Sun Oct 30, 2011 10:50 pm

hk wrote:And now try the same with the integer part of 20.999^n, writing out the full answer first.
See how fast this deviates?
So the answer cannot be calculated with floating point aritmetic.
Thanks HK, that's what's been bugging me all along, since I found out that whilst using Newton's method to determine the roots, that even a tiny deviation in the 10th decimal place caused my answer to deviate sharply. Plus I noticed that with the exception of probability problems on here, most problems involve integers. That being said, now I have no idea how to make this work, back to the drawing board....

Duality
Posts: 6
Joined: Sun Oct 23, 2011 3:30 am

Re: Problem 356

Post by Duality » Mon Oct 31, 2011 3:11 pm

Even with mpmath and hundreds of decimal places of precision, your answers are going to be wildly off, it would seem. That's what makes this problem so odd. You need to get some rather specific digits and yet we can't get access to them directly by just power-raising a given root alone because we lack the precision to do it.

quilan
Posts: 182
Joined: Fri Aug 03, 2007 10:08 pm

Re: Problem 356

Post by quilan » Tue Nov 08, 2011 7:19 pm

So, I've been completely unsuccessfully ramming my head against this problem for weeks now and I'm curious about one thing:

Is the typical method of solution specific to the nature of the root of a cubic? Or could you come up with a method to solve (for instance) $ \lfloor1.1^a\rfloor (mod \; b) $ and extrapolate?

I've tried dozens upon dozens of methods & so far nothing's yielded anything that could be remotely viable (even trigonometric approaches!). Hrmm.
ex ~100%'er... until the gf came along.
Image

sivakd
Posts: 217
Joined: Fri Jul 17, 2009 8:37 am
Location: California, USA
Contact:

Re: Problem 356

Post by sivakd » Wed Nov 09, 2011 7:56 am

I am hoping this is not going to give out much. For me, the research I did to solve problem 318 helped in solving this.
Image
puzzle is a euphemism for lack of clarity

quilan
Posts: 182
Joined: Fri Aug 03, 2007 10:08 pm

Re: Problem 356

Post by quilan » Wed Nov 09, 2011 10:30 pm

sivakd wrote:I am hoping this is not going to give out much. For me, the research I did to solve problem 318 helped in solving this.
I could kiss you right now. I'm as blind & dumb as a bat, I swear to god. I have no idea how I missed behavior that obvious! I'll have it solved shortly!
ex ~100%'er... until the gf came along.
Image

limburger
Posts: 1
Joined: Sun Nov 06, 2011 10:20 pm

Re: Problem 356

Post by limburger » Fri Dec 02, 2011 6:46 am

Were this actually a problem that could be solved in floating point, it would be a one liner in J - it will give you numeric roots for any polynomial, and the creation of the 30 polynomials, solving them, and so forth is just that simple - I could post the code fragment here and it would not help anyone, because it is a floating point solution (as is the "hint" in the problem). There is a primitive operator for that. :-)

But I kept on thinking about it, and it became clear that it could not be solved with floating point - because once you took the floating point number to that power, precision would kill you. So I figured, "Maybe a standard way of solving these polynomials will leave me with an exact solution that will allow me to stick with integers - if I am taking a root to a power, I should be able to peel the radical off of the internal term without losing the "integerness", somehow. It also looks (in J) like the solutions become integer at some point, and I am going to guess that that is an artifact of J's rounding, x.9to 20 digits is being internally rounded to x+1 as an integer. So the hint to look at that other problem might allow one to derive what the combination of roots might be.

I tried solving the equations in wxmaxima, just a simple: solve([x^3-4*x^2+2=0], [x]); Of all my computer algebra systems or devices I have installed, wxmaxima is the only one that will try to solve this other than numerically.

This is the result of the exact solution for x^3-4*x^2+2:

(%o2) [x=(-(sqrt(3)*%i)/2-1/2)*((sqrt(101)*%i)/3^(3/2)+37/27)^(1/3)+(16*((sqrt(3)*%i)/2-1/2))/(9*((sqrt(101)*%i)/3^(3/2)+37/27)^(1/3))+4/3,x=((sqrt(3)*%i)/2-1/2)*((sqrt(101)*%i)/3^(3/2)+37/27)^(1/3)+
(16*(-(sqrt(3)*%i)/2-1/2))/(9*((sqrt(101)*%i)/3^(3/2)+37/27)^(1/3))+4/3,x=((sqrt(101)*%i)/3^(3/2)+37/27)^(1/3)+16/(9*((sqrt(101)*%i)/3^(3/2)+37/27)^(1/3))

Easier to see as an image - my it was painful to make the image public, upload it to Picasa, crop it, and figure out how to get the proper link - the "link to this picture" link that picasa will give you is not useful for an imbed. I hope I got it right.

Image

WxMaxima gives a "realroots" of 129728087r33554432 which, when substituted back into the polynomial, does not result in zero, it gets as close as 1.25e_7. The J suggestion when I use exact integers is 4432741612622r1146537583343 which gets as far as 2.22e_15, about twice as good. But neither is actually exact.

I've written one of these brain dumps on a Euler problem about three times. That is, sort of a brain dump - it is as much for me as it is for you. But in the past, I had to worry about the amount I knew and spoilers I might give, since I had a possibly worthwhile approach, and in some way, I had to not post spoilers or worthwhile information, according to the forum rules. Here I can say that I honestly have no worthwhile information - none at all. I had suspected strongly that the solution had to be integer in nature, I see absolutely no way to approach that, and I saw the pointer to the other problem, and that leaves me nowhere. I look at the above "solution" and I don't see any hope of making it into an integer by, say, taking the above structure to a power until the radicals (which appear in about three forms) are cleared. I could post the code I have and it would simply be a nothing. In the past, by the time I finished one of these dumps, it helped - I had an approach that I got just by doing the dump, and the associated research. This may be one of those problems I am not destined to solve. I looked at the other relative problem, I'm not seeing an approach to that either.

User avatar
Marcus_Andrews
Administrator
Posts: 1459
Joined: Wed Nov 09, 2011 5:23 pm

Re: Problem 356

Post by Marcus_Andrews » Fri Dec 02, 2011 6:40 pm

Without spoiling too much, I'll just say that there is something about the problem that you're aware of but haven't investigated. Put all of that work to the side for the moment and see what else you could use. :)
Image

JiminP
Posts: 14
Joined: Sun Nov 06, 2011 3:07 am
Location: Seoul, South Korea

Re: Problem 356

Post by JiminP » Wed Oct 03, 2012 11:45 am

I found how to solve this problem, but my answer is wrong... :(

Are all of these correct? (a5=a_5, a5^42=(a_5)^42)
  • floor(a5^4) = 1047935
  • Last 8 digits of floor(a1^123456789) = 73387676
  • Last 8 digits of floor(a2^123456789) = 97149439
  • Last 8 digits of floor(a30^123456789) = 63746303
(Of course I know it's 987654321 in the problem)
Image

ffff0
Posts: 50
Joined: Sun Aug 21, 2011 5:26 am
Location: Moscow, Russian Federation

Re: Problem 356

Post by ffff0 » Thu Oct 04, 2012 12:24 pm

I've got 63249407 for floor(a2^123456789). Others are the same.
Image

JiminP
Posts: 14
Joined: Sun Nov 06, 2011 3:07 am
Location: Seoul, South Korea

Re: Problem 356

Post by JiminP » Thu Oct 04, 2012 6:30 pm

Thanks! There was an 'non-exception'...
Image

Post Reply