Peter-Lawrence . Montgomery on Sat, 23 Sep 2000 05:21:14 +0200 (MET DST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Problem |
If F_n is a 13-th power, then (F_n mod p) is a 13-th residue (or 0) modulo all primes p. Choose 10 primes p_j == 1 mod 13, starting with 53, 79, 131, 157, ... If you know F_{2i-1} mod p_j and F_{2i-3} mod p_j, then F_{2i+1} == 3*F_{2i-1} - F_{2i-3} (mod p_j) Use F_{2i+1} mod p_j as an array subscript, where the array tells you whether the index a 13-th power mod p_j. If the test passes for all j, output 2i+1 as a possible solution. The test should take only a few seconds. I anticipate no solutions. Peter Montgomery ------------ > From: "James G. McLaughlin" <jgmclaug@math.uiuc.edu> This is probably not a bug question but I just do not know of the fastest way to get pari to do it. Let F_{1}=F_{2}=1 and F_{n+1}= F_{n} + F_{n-1} for n >= 2 (The Fibonacci sequence) I wish to test the sequence { F_{2*i+1} : 1 <= i <= 69,700 } for 13th powers. As you can imagine, as i gets up to 69,700, F_{2*i+1} gets very big (around 10^(23,000)). I have not been able to write a gp program that would do this in any reasonable time. I wrote a very simple program in magma that would have done it in around 3 - 4 hours (extrapolating) but it crashes around i = 52,000. Am I missing something very simple and can gp do this easily or is it also beyond gp to do this in a reasonable time?