Results 1 to 14 of 14

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

  1. #1
    Newbie
    Joined
    Jul 2010
    Posts
    20

    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.

    I heard this problem could be solved by linear algebra. Please help me solve this!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by oleholeh View Post
    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!
    I think negative integers n must be disallowed, otherwise it is trivially easy...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    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.)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jul 2010
    Posts
    20
    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!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Not sure whether this would be of use

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

    Seems to me an interesting and tough problem
    Follow Math Help Forum on Facebook and Google+

  6. #6
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    5
    Awards
    2
    I would probably write a computer program to solve it. For efficiency, I'd probably use Euclid's algorithm to check for divisibility.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    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.)
    Last edited by undefined; July 26th 2010 at 07:41 AM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    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();
            nums.add(24L);
            nums.add(69L);
            nums.add(198L);
            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);
                nums.add(next);
            }
            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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Jul 2010
    Posts
    20
    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?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Jul 2010
    Posts
    20
    Another interesting thing about 1+2cos(pi/9) is that it is a root of the equation x^3-3x^2+1=0
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by oleholeh View Post
    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.

    Quote Originally Posted by oleholeh View Post
    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..

    Quote Originally Posted by oleholeh View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    Jul 2010
    Posts
    20
    Just one more question: did you do the recursions with the rounded values?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by oleholeh View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    A post by Opalg in the following thread is relevant:

    http://www.mathhelpforum.com/math-he...on-152447.html
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Work hours rounded to the nearest quarter
    Posted in the Algebra Forum
    Replies: 8
    Last Post: July 14th 2011, 09:37 AM
  2. nearest integer function
    Posted in the Math Challenge Problems Forum
    Replies: 8
    Last Post: June 10th 2010, 09:55 PM
  3. Integer roots of integer polynomials
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 3rd 2009, 01:39 PM
  4. Raise integer to positive integer power
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 21st 2009, 01:20 PM
  5. Find Next Integer
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 24th 2007, 12:26 PM

Search Tags


/mathhelpforum @mathhelpforum