# Thread: Find an integer n for which (1+2cos(π/9))^n rounded to nearest integer is divisib...

1. ## Find an integer n for which (1+2cos(π/9))^n rounded to nearest integer is divisib...

Find an integer n for which (1+2cos(pi/9))^n rounded to the nearest integer is divisible by 1 billion.

2. Originally Posted by oleholeh
Find an integer n for which (1+2cos(pi/9))^n rounded to the nearest integer is divisible by 1 billion.

I think negative integers n must be disallowed, otherwise it is trivially easy...

3. 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.)

4. If it helps, someone told me a hint, which is that the smallest possible n is very large, like in the magnitude of 10 digits or so.

Please continue cracking this problem! Much appreciated!

5. Not sure whether this would be of use

Trigonometry Angles--Pi/9 -- from Wolfram MathWorld

Seems to me an interesting and tough problem

6. I would probably write a computer program to solve it. For efficiency, I'd probably use Euclid's algorithm to check for divisibility.

7. 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.)

8. Do you have any way to check answers? I got

Spoiler:

n = 169531249

Java
Code:
import java.util.ArrayList;

public class NonagonRecursion {
static ArrayList<Long> nums = new ArrayList<Long>();
static long n = 6;
static final long M = 1000000000;

public static void main(String[] args) {
long t = time();
for(;;n++) {
long next = (3*nums.get(2) - nums.get(0)) % M;
if(next < 0) next += M;
if(next == 0) {
System.out.println(n);
break;
}
nums.remove(0);
}
System.out.println("Elapsed: " + (time()-t)/1000.0 + " seconds");
}

public static long time() {
return System.currentTimeMillis();
}
}
Output
Code:
169531249
Elapsed: 5.543 seconds
Also, I'd like to know where you got this problem.

9. 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.

Do you have any way to check answers? I got
I will ask my friend when I get a chance
Also, I'd like to know where you got this problem.
From my friend ^^

Could you explain a bit on what you did in the program?

10. Another interesting thing about 1+2cos(pi/9) is that it is a root of the equation x^3-3x^2+1=0

11. Originally Posted by oleholeh
Another interesting thing about 1+2cos(pi/9) is that it is a root of the equation x^3-3x^2+1=0
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.

Originally Posted by oleholeh
From my friend ^^
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..

Originally Posted by oleholeh
Could you explain a bit on what you did in the program?
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.

12. Just one more question: did you do the recursions with the rounded values?

13. Originally Posted by oleholeh
Just one more question: did you do the recursions with the rounded values?
Yes, the recursion produces an integer sequence to match the (last nine digits of the) rounded values.

14. A post by Opalg in the following thread is relevant:

http://www.mathhelpforum.com/math-he...on-152447.html