In 1969 I investigated the series of complex (Gaussian) integers: s[n] = (1+i)^n - 1. At that time I could only find the first few primes. Even now, there seem to be no references in the math literature or on the internet to this series, which has so many beautiful aspects. It is best thought of as the complex counterpart of the Mersenne series. As with the Mersennes, n must be prime else s[n] is composite. For n = 2, s[n] = (1+i)^2 - 1 = 2*i - 1, with modulus (2*i-1)*(-2*i-1) = 5, which is prime. If n is odd, let n = 2*m+1, m >= 0. Then the modulus of s[n] is: A[n] = ((1+i)^n-1)*((1-i)^n-1) = (2^m)^2 + (2^m + (-1)^(m*(m+1)/2))^2. It is easy to prove that any prime factor of A[n] is of the form 4*k*n+1. For n = 3, i.e. m = 1, A[n] = 2^2 + (2^2+(-1)^1)^2 = 4 + 9 = 13, which is prime. For odd n >= 5, i.e. m >= 2, I have proved that a necessary and sufficient condition for A[n] to be prime is: R[m]^m = -1 mod A[n], where R[m] = 2^m-(-1)^((m*(m+1)/2)^2. This is similar to the Lucas-Lehmer test, and can be programmed in just the same way. The time for "mod A[n]" modulus reduction is only marginally longer than in the Mersenne case, and is anyway negligible compared with the time for FFT squaring. Over the last year I have devoted 1 or 2 Intel PCs to the search for primes of this form, and have to date found the first 33:- Seq n A[n] Digits 1 2 5 1 2 3 2^3+2^2+1 2 3 5 2^5+2^3+1 2 4 7 2^7-2^4+1 3 5 11 2^11+2^6+1 4 6 19 2^19+2^10+1 6 7 29 2^29+2^15+1 9 8 47 2^47-2^24+1 15 9 73 2^73-2^38+1 22 10 79 2^79-2^40+1 24 11 113 2^113-2^57+1 35 12 151 2^151-2^76+1 46 13 157 2^157+2^79+1 48 14 163 2^163+2^82+1 50 15 167 2^167-2^84+1 51 16 239 2^239-2^120+1 72 17 241 2^241-2^121+1 73 18 283 2^283+2^142+1 86 19 353 2^353-2^177+1 107 20 367 2^367-2^184+1 111 21 379 2^379+2^190+1 115 22 457 2^457-2^229+1 138 23 997 2^997+2^499+1 301 24 1367 2^1367-2^684+1 412 25 3041 2^3041-2^1521+1 916 26 10141 2^10141+2^5071+1 3,053 27 14699 2^14699+2^7350+1 4,425 28 27529 2^27529-2^13765+1 8,288 29 49207 2^49207-2^24604+1 14,813 30 77291 2^77291+2^38646+1 23,267 31 85237 2^85237+2^42619+1 25,659 32 106693 2^106693+2^53347+1 32,118 33 160423 2^160423-2^80212+1 48,293 The first 32 were found by my own implementation of the above algorithm; the 33rd was shown as "PRP" on 22 August 2000 by a beta release of Chris Nash's superb PrimeForm/GW, and then confirmed to be prime by my program. The exponents increase in very much the same manner as the Mersenne ones. The logic behind the conjecture by Wagstaff and others that the geometic mean of the ratio of successive terms should be approximated by 2^(e^(-gamma)) applies to this series equally, and is about equally well exemplified, thereby enhancing confidence in its validity. (A _proof_ of the conjecture, is, of course, far out of reach.) I hereby solicit the aid of those in GIMPS et al. to extend this series of primes! Regards Mike Oakes _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt
