[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
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**
| |