Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

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>