       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

```

• Prev by Date: Re: dual y-axis plotting - is it possible in mathematica?
• Next by Date: Re: dynamic popupmenu help needed
• Previous by thread: 2-defensive prime number
• Next by thread: Wolfram Lightweight Grid Manager--available free to Premier Service subscribers and sites