From: johnbcos@iol.ie (John B. Cosgrave) Subject: Re: primes of the form 2^k+2^i+1 Date: 5 Oct 99 22:59:32 GMT Newsgroups: sci.math.numberthy Dear Mingzhi Zhang, and colleagues, The recent letter from Mingzhi Zhang (below) was of interest to me for many reasons, but for one special reason which I would like to explain (and which I hope may interest some of you). In the Zhang case where one lets k = 2*i, forming the numbers 2^(2*i) + 2^i + 1, one finds three primes from setting i = 1, 3 and 9 (and for *no* other values of 'i' up to...). Those primes are 7, 73 and 262657. Earlier this year I stumbled upon those three primes while I was preparing some routine notes for my students in connection with Proth's theorem: " let n = s*(2^i) + 1 and s < 2^i; then 'n' is prime if (and only if) there is an integer 'a' such that a^((n-1)/2) = -1 mod n ," which I was about to teach my students (most of whom are training to be primary school teachers). I knew they would have a difficulty with the standard proof (in which the condition "s < 2^i" is used in rather an awkward way), and while seeking a way to make the theorem more accessible to them, I noticed the improved condition "s <= 2^i + 1" still forced the conclusion that 'n' be prime, and with the bonus of a more natural proof. (I have notes on this up on my web site.) Having done that, I was keen that my students see some numbers proved to be prime, using the 2-extra-cases improved version. Thus I sought to find primes of the form s*(2^i) + 1 with: 1. s = 2^i, or 2. s = 2^i + 1 Case 1 leads to numbers of the form (2^i)*(2^i) + 1 = 2^(2*i) + 1 (leading only to the regular Fermat primes - since primes of the form 2^k + 1 are necessarily Fermat primes - about which so little is known). Case 2 leads to numbers of the form (2^i + 1)*2^i + 1 = 2^(2*i) + 2^i + 1 [the k = 2*i, Mingzhi Zhang case - m(2i, i) - above]. In the course of investigating primes of that latter special form I fell upon a [to me] cornucopia of delights: a. 2^(2*i) + 2^i + 1 is prime for i = 1, 3 and 9 (any others?) and passes the Lucas-Fermat test to the base 2 for i = 3^n (n = 0, 1, 2, 3, ... ). That immediately suggested a form of generalised Fermat number, namely numbers of the form: 2^(2*(3^n)) + 2^(3^n) + 1, which was the more compelling when one thought of the simply proved: b. If (2^(2*i) + 2^i + 1) is prime then 'i' is necessarily of the form 3^n (analogous to the elementary: if 2^i + 1 is prime then 'i' is necessarily of the form 2^n). c. The numbers 2^(2*(3^n)) + 2^(3^n) + 1 are values of the irreducible quadratic x^2 + x + 1, evaluated at x = 2^(3^n), and a further obvious generalisation was to consider values of x^(p - 1) + x^(p - 2) + ... + x + 1 ('p' prime to make it irreducible), evaluated at x = 2^(p^n). Notation. Let 'p' be the r-th prime, and let F[n, r] = x^(p - 1) + x^(p - 2) + ..... + x + 1, evaluated at x = 2^(p^n). Note. The numbers {F[n, 1]} (n = 0, 1, 2, 3, 4, 5, ...) are the classic Fermat numbers, the numbers {F[0, r]} (r = 1, 2, 3, 4, 5, ...) are the classic Mersenne numbers. The numbers {F[n, r]} (which I believed to be new) behave exactly *like* Fermat numbers, in that: A. Let 'x' and 'm' be natural numbers such that x^((p - 1)*m) + x^((p - 2)*m) + ..... + x^m + 1 is prime, then m = p^n for some n = 0, 1, 2, 3, 4, 5,... . B. The numbers {F[n, r]} are pairwise relatively prime. C. F[n, r] passes the Lucas-Fermat test to the base 2 (this is what I consider most important), and for fixed 'r' they satisfy the functional equation: F[0, r]*F[1, r]*...*F[n, r] = 2^(p^(n+1)) - 1 Nomenclature. For *fixed* 'r,' refer to the numbers {F[n, r]} as the generalised Fermat numbers of rank 'r'; I think of them as going vertically. For *fixed* 'n', refer to the numbers {F[n, r]} as the generalised Fermat numbers of level 'n'; I think of them as going horizontally. Thus the Fermat and Mersenne numbers may be *thought of* as forming the left and bottom sides of a doubly-infinite matrix of numbers {F[n, r]}, n = 0, 1, 2, 3, 4,... , r = 1, 2, 3, 4,... . Comments and questions. The classic Fermat numbers are the above generalised ones of rank 1, and - as is only too well known - they consist of 5 consecutive primes, followed by the unknown... . The consensus appears to be that there are only 5 Fermat primes, and everyone is familiar with the basis for that. But what about the ones of rank 2? They commence: 7, 73, 262657, 18014398643699713, ... [three primes at the start, followed by a composite, followed by ... ? Are *all* the others composite?] And the ones of rank 3? They commence: 31, 1082401, 1267650638007162390353805312001, ... [one prime at the start, followed by two composites, followed by ... ? Are *all* the others composite?] The principal question that I asked myself earlier this year was: do these ranks of generalised Fermat numbers behave in the same *apparent* way as the classic Fermat numbers; namely: If F[n, r] is composite is F[n+1, r] also composite? In other words, does each rank of Fermat numbers - including those of rank 1, the Fermat numbers themselves - commence with a number of primes (possibly none), followed *entirely* by composites? In connection with that question I wrote an elementary paper - "Could there exist a sixth Fermat prime? I believe it is *not impossible*? - which I submitted to the MAA Monthly on March 19th this year. The essential point I tried to make (in an entirely *elementary* paper - one which I wrote with ordinary students in mind, and not advanced researchers) in my paper was that I had identified that at rank r = 17, the number F[0, 17] = 2^59 - 1 is *composite,* *but* the (1031-digit) number F[1, 17] is *prime,* [rather it *appeared* to be prime, and I asked if it could be proved to be prime...] and I sought to make the (I believe) fair point that if such a thing could happen at the 17th rank then it was possible that it could happen at *any* rank, and in particular it could happen at the first rank, and hence the title of my paper... . The following day I circulated an e-mail to a small number of friends and colleagues about this matter, and some interesting correspondence ensued. In particular I heard from Yves Gallot by return that my generalisation was to be found in an unpublished paper of Wilfrid Keller (which gave credit to Shanks, Ligh and Jones for the generalisation), and a few days later I heard from Francois Morain that he had proved that F[1, 17] is prime. My Monthly paper was eventually rejected, and I am not attempting to resubmit it anywhere. I have today constructed a 'Fermat 6' corner to my College web site (from my home page just click on the 'Fermat 6' button), in which I have expanded on the above. There you may access a greatly shortened version of my original Maple worksheet (also in html format for those of you who don't use Maple), together with my Fermat paper, and the texts of e-mails (including a later one in which I proposed a new conjecture for testing primality of Mersenne numbers, and more generally for F[n, r]). If you do check it out, I hope you will find something of interest there. Best wishes, John # John B. Cosgrave, Mathematics Department, # St. Patrick's College, Drumcondra, # Dublin 9, IRELAND. # # [St. Patrick's College is a College of Dublin City University] # # Home e-mail: johnbcos@iol.ie # College e-mail: John.Cosgrave@spd.ie # My College Web site: http://www.spd.dcu.ie/johnbcos # # Is 2^p - 1 prime for infinitely many p? (I hope so.) # Is 2^(2^n) + 1 prime for some n > 4? (Surely at least one?) # Is Pi^e transcendental? (Probably.) # Is 2^sqrt(2) + 3^sqrt(3) irrational? (Almost certainly.) # Is zeta(3) a rational multiple of Pi^3? (Hardly.) ---------- > From: zamiz > To: NMBRTHRY@LISTSERV.NODAK.EDU > Subject: primes of the form 2^k+2^i+1 > Date: 04 October 1999 13:09 > > Dear colleagues, > Fermat considered the primes of the form 2^k+1. Unfortunately, there > > are only 5 known Fernat primes up to now. If we consider the numbers of > the form m(k,i)=2^k+2^i+1, 0 find primes. > Let we estimate f(n)---the number of primes of the form m(k,i) where > > k<=n,0 As J. Conway noted, for sufficiently large k, we have > (1-epsilon)*2^k/k*ln2 Hypothesis. Primes are distributed in the odd numbers m(k,i),(1 > as are distributed in all odd numbers in the interval [2^k,2^(k+1)]. > If we assume this hypothesis, we can expect there are 2/ln2 primes > of the form m(k,i) for a given sufficiently large k. Therefore, > f(n)~2n/ln2. Let R(n)=f(n)/n, R(n) should be close to the constant > 2/ln2=2.885390082.... > After short computation, we obtained the following result which > supports the estimation above. > n 50 100 150 200 > 250 > R(n) 2.5800 2.7700 2.8267 2.9500 2.9560 > n 300 350 400 450 > 500 > R(n) 2.9000 2.9057 2.8925 2.8822 2.8500 > Hence, we have > Conjecture f(n)~2n/ln2. > But, where is the proof or disproof ? > ---------------------------------- > Mingzhi Zhang > Mathematics Department > Sichuan University > Chengdu > Sichuan Province 610064 > P.R.China ============================================================================== From: Dave Rusin Subject: Re: Proth's Theorem Date: Fri, 3 Sep 1999 23:43:52 -0500 (CDT) Newsgroups: [missing] To: rlr@earth.sun.galaxy Keywords: Proth's theorem: N prime iff for some a, N | (a^((N-1)/2) + 1) You wrote: > >Can someone give the effective limits of a in Proth's Theorem? >Let N = k*2^n+1 and 2^n > k , and the theorem states: >If an integer a exists such that a^((N-1)/2) mod N = -1 >then N is prime. But what value a can take is not stated. >is 0 < a < N? I think Proth's theorem is just as you stated it: "If there exists an integer..."; any integer will do. Of course if a works, so does (a mod N), so we might as well assume 0 < a < N. But is that really your questions? Certainly the converse is true (N prime => there is a primitive root a which has the desired property; again we may assume 0 < a < N) but people desire smaller bounds on a so that this theorem can be used as a primality test effectively. On the strength of the Riemann hypothesis I think one can show there is a primitive root less than log(N) (or maybe C*log(N) for some C; I can't recall) but proven bounds are not so good yet. [deletia -- djr] PS - you might find some useful information at index/11Y05.html