Problem 356
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.
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
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
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.
 BostonBear
 Posts: 17
 Joined: Thu Apr 28, 2011 3:48 am
 Location: Saugus, MA
Problem 356
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
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
Re: Problem 356 and precision issues
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.
puzzle is a euphemism for lack of clarity
Re: Problem 356 and precision issues
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.
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.
Re: Problem 356 and precision issues
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.
See how fast this deviates?
So the answer cannot be calculated with floating point aritmetic.
Re: Problem 356 and precision issues
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.
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.

 Posts: 20
 Joined: Sun Sep 25, 2011 10:20 pm
Re: Problem 356 and precision issues
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.
Re: Problem 356 and precision issues
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.CJKay93 wrote:So what, are we meant to floor or round a_i before a_i^987654321?
puzzle is a euphemism for lack of clarity
Re: Problem 356 and precision issues
Oh, well in that case that's what I've no idea what I'm doing wrong lol.sivakd wrote: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.CJKay93 wrote:So what, are we meant to floor or round a_i before a_i^987654321?
EDIT: Never mind, I deciphered what you wrote and I think I caught on .
 BostonBear
 Posts: 17
 Joined: Thu Apr 28, 2011 3:48 am
 Location: Saugus, MA
Re: Problem 356 and precision issues
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....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.
Re: Problem 356
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 powerraising a given root alone because we lack the precision to do it.
Re: Problem 356
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.
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.
Re: Problem 356
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.
puzzle is a euphemism for lack of clarity
Re: Problem 356
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!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.
ex ~100%'er... until the gf came along.
Re: Problem 356
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^34*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^34*x^2+2:
(%o2) [x=((sqrt(3)*%i)/21/2)*((sqrt(101)*%i)/3^(3/2)+37/27)^(1/3)+(16*((sqrt(3)*%i)/21/2))/(9*((sqrt(101)*%i)/3^(3/2)+37/27)^(1/3))+4/3,x=((sqrt(3)*%i)/21/2)*((sqrt(101)*%i)/3^(3/2)+37/27)^(1/3)+
(16*((sqrt(3)*%i)/21/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.
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.
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^34*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^34*x^2+2:
(%o2) [x=((sqrt(3)*%i)/21/2)*((sqrt(101)*%i)/3^(3/2)+37/27)^(1/3)+(16*((sqrt(3)*%i)/21/2))/(9*((sqrt(101)*%i)/3^(3/2)+37/27)^(1/3))+4/3,x=((sqrt(3)*%i)/21/2)*((sqrt(101)*%i)/3^(3/2)+37/27)^(1/3)+
(16*((sqrt(3)*%i)/21/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.
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.
 Marcus_Andrews
 Administrator
 Posts: 1459
 Joined: Wed Nov 09, 2011 5:23 pm
Re: Problem 356
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.
Re: Problem 356
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)
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
Re: Problem 356
I've got 63249407 for floor(a2^123456789). Others are the same.
Re: Problem 356
Thanks! There was an 'nonexception'...