Find an integer n for which (1+2cos(pi/9))^n rounded to the nearest integer is divisible by 1 billion.
I heard this problem could be solved by linear algebra. Please help me solve this!
Since no one's chiming in, I'll mention that perhaps some form of fast exponentiation could lead to a solution. (I do not have a solution, and not much time to devote to finding one.)
Not sure whether this would be of use
Trigonometry Angles--Pi/9 -- from Wolfram MathWorld
Seems to me an interesting and tough problem
There seems to be something special about the number 1+2cos(pi/9). According to observation as opposed to rigorous proof, I find that if we let a(n) = [(1+2cos(pi/9))^n], where [k] means nearest integer of k, the sequence {a_n} approaches an integer sequence whose successive ratios a(n)/a(n-1) of course approach 1+2cos(pi/9), and from experimentation, a(n) = 2*a(n-1) + 2*a(n-2) + sum(i=0, n-3, a(i)). The relation seems to hold starting from n=5. Testing on PARI/GP, I'm not sure what happens around n=60 because precision loss seems to kick in, would have to reset precision or use a different CAS or something. (But my guess right now is that it holds for all n > 4.)
After some manipulation, this just becomes a(n) = 3*a(n-1) - a(n-3), holding for n > 5.
Assuming this is true, calculating a(n) mod 10^9 for n having 10 digits could run in a "reasonable" amount of time just by brute force, although this seems pretty inelegant. Perhaps matrix multiplication can be used in the manner of this, which could provide a tie-in with linear algebra and fast exponentiation. (Just thinking out loud.)
This is very similar to a hint my friend gave me.Perhaps matrix multiplication can be used in the manner of this, which could provide a tie-in with linear algebra and fast exponentiation. (Just thinking out loud.)
I will ask my friend when I get a chanceDo you have any way to check answers? I got
From my friend ^^Also, I'd like to know where you got this problem.
Could you explain a bit on what you did in the program?
Well that makes sense, it corresponds with the recursion I found... relates to characteristic polynomial.. I have experience with these in the context of solving problems, but my theoretical knowledge could be better. But as to why it is a root.. I remember seeing solutions to cubics that looked similar, but I can't say for sure it was the same situation, it was so long ago, and I should definitely brush up.
Would you mind asking your friend where he/she got the problem? I'm interested in finding more like it! I'm running out of Project Euler problems to solve..
So it's a basic iterative algorithm, it assumes my recursion is correct (and you mentioning the root of the cubic confirms this), then it uses a list (ArrayList) to keep the last three terms in memory, then from this calculates the next term, then updates the list.
The other part is that we only care about the last 9 digits at any given time. So we use the % or "mod" operator which gives the remainder when divided by (in this case) 10^9. Sometimes though we get a negative number and have to add 10^9 in order to get it in the desired range, 0 to 10^9 - 1. If you study modular arithmetic/congruence it will be pretty apparent, you might need to work with a few examples before it sinks in. (I don't know your experience/knowledge level.) We are done when the last 9 digits are 0, that is, our term is congruent to 0 mod 10^9.
So for example, if we want to know the last three digits of 7^6 but don't want to calculate 7^6 directly, we can take mod 10^3 at each operation and come up with the desired result:
7^3 = 343
343 * 7 = 2401, discard all but last three digits
401 * 7 = 2807, discard all but last three digits
807 * 7 = 5649
so the answer to that example is 649.
The rest is just knowing how to read Java syntax, like the loop structure.
A post by Opalg in the following thread is relevant:
http://www.mathhelpforum.com/math-he...on-152447.html