Re: 2-defensive prime number

*To*: mathgroup at smc.vnet.net*Subject*: [mg98458] Re: [mg98345] 2-defensive prime number*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Fri, 10 Apr 2009 04:53:54 -0400 (EDT)*References*: <200904080646.CAA19477@smc.vnet.net>

Tangerine Luo wrote: > 2-defensive odd number is defined as: > n=2k+1 is an odd number, k>0, if Mod[2^i+1,n] != 0 for any natural > number i , then n is 2-defensive odd number. If n is prime too, then n > is 2-defensive prime number. > > My questions are: > 1. Have 2-defensive odd numbers some special form? > 2. ratio = all 2-defensive odd numbers / all odd numbers >1/2 ? > ratio = all 2-defensive prime numbers / all odd prime numbers < > 1/2 ? > > > Euler's Theorem: If (a,m)=1, then m|a^EulerPhi[m] -1 > so , m | a^(i+EulerPhi[m]) - a^i for any natural number i. > therefor, if Mod[2^i+1,n] != 0 for i between [1, EulerPhi[n])] , then > n is 2-defensive odd number. > > for example, > 3|2^1+1 > > 5|2^2+1 > > 7 is 2 defensive prime number > > 9|2^3+1 > > 11|2^5+1 > > 13|2^6+1 > > 15 is 2 defensive odd number > ... > 23 is 2 defensive prime number > > My program code is: > > Table[ > For[i = 1, i < p, i++, > If[Mod[2^i + 1, p] == 0, Print[p, "|2^", i, "+1"]; Break[]] > ] > If[i == p, Print[p, " is 2 defensive number"]] > , > {p, Table[Prime[i], {i, 100}]}] Here is code that will be a bit faster in finding these. It covers the first 10,000 primes, takes around 450 seconds on my desktop machine. Timing[twodef10k = Reap[Do[ p = Prime[j]; res = 1; Catch[ Do [res = Mod[2*res,p]; If [res==p-1, Throw[False], If [res==1, Sow[p]; Throw[False]]],{p}]; ]; , {j, 10000}]][[2,1]];] Seems that the ratio in question might be stailizing around .29 or so. As for what is known about these, might want to check the OEIS entry and references therein: http://www.research.att.com/~njas/sequences/A072936 Here is code that is much faster. It uses built in MultiplicativeOrder, along with a remark about a 2004 result od D. Noe. Timing[twodef = Reap[Do[ p = Prime[j]; If [OddQ[MultiplicativeOrder[2,p]], Sow[p]]; , {j, 10000}]][[2,1]];] Daniel Lichtblau Wolfram Research

**References**:**2-defensive prime number***From:*Tangerine Luo <tangerine.luo@gmail.com>