| Displaying 1-6 of 6 results found.
page
1
a(n) = A056915(n) mod 76057 mod 13.
+20
5
2, 7, 11, 10, 5, 9, 6, 3, 4, 0, 1, 12, 8, 8, 6, 10, 9, 6, 7, 10, 3, 6, 2, 9, 8, 1, 2, 2, 2, 8, 0, 5, 5, 2, 7, 11, 5, 2, 11, 0, 10, 8, 2, 7, 4, 10, 2, 0, 5, 12, 8, 11, 6, 7, 7, 11, 0, 5, 1, 12, 6, 4, 6, 7, 8, 1, 12, 0, 7, 2, 9
COMMENTS
A056915(n) mod 76057 mod 13 is a bijection from the set of the first 13 terms of A056915 to {0,1,2,3,4,5,6,7,8,9,10,11,12}.
One of the tests for primality described in the first reference when tests x and x is prime, searches a table T composed by the first 13 entries of A056915 to see if x is a strong pseudoprime to bases 2,3 and 5. A fast way to do that is to compute i = x mod 76057 mod 13, and compare x with T[i]. If x is not equal to T[i], x is prime. Terms computed using table by Charles R Greathouse IV. See A056915.
LINKS
C. Pomerance, J. L. Selfridge, and S. S. Wagstaff, Jr., The pseudoprimes to 25*10^9, Mathematics of Computation, 35, 1980, pp. 1003-1026.
3, 4, 13, 15, 8, 14, 9, 5, 0, 11, 16, 10, 2, 12, 7, 1, 6, 16, 3, 10, 5, 8, 7, 16, 6, 11, 13, 6, 10, 6, 11, 16, 9, 1, 1, 15, 5, 1, 14, 7, 15, 2, 14, 9, 2, 6, 14, 3, 3, 14, 12, 6, 2, 4, 10, 16, 6, 10, 9, 3, 3, 1, 7, 9, 11, 5
COMMENTS
A056915(n) mod 5228905 mod 17 is a bijection from the set of the first 17 terms of A056915 to {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}.
From an algorithm based on strong pseudoprimes to bases 2,3 and 5, and a table T with the first 17 terms of A056915, we can test if n is prime, odd n, 1 < n < 42550716781. When n is a prime, we check if n belongs to T. A fast way to do that is to compute i = n mod 5228905 mod 17 and compare n with T[i]. If n is not equal to T[i], n is prime. Terms computed using table by Charles R Greathouse IV. See A056915.
Strong pseudoprimes to base 2.
+10
77
2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751, 104653, 130561, 196093, 220729, 233017, 252601, 253241, 256999, 271951, 280601, 314821, 357761, 390937, 458989, 476971, 486737
REFERENCES
R. K. Guy, Unsolved Problems Theory Numbers, A12.
P. Ribenboim, The Book of Prime Number Records. Springer-Verlag, NY, 2nd ed., 1989, p. 95.
EXAMPLE
For k = 577, k-1 = 576 = 9*2^6. Since 2^(9*2^3) = 2^72 == -1 (mod 577), 577 passes the primality test, but since it is actually prime, it is not in the sequence.
For k = 3277, k-1 = 3276 = 819*2^2, and 2^(819*2) == -1 (mod 3277), so k passes the primality test, and k = 3277 = 29*113 is composite, so 3277 is in the sequence. (End)
MAPLE
A007814 := proc(n) padic[ordp](n, 2) ; end proc:
isStrongPsp := proc(n, b) local d, s, r; if type(n, 'even') or n<=1 then return false; elif isprime(n) then return false; else s := A007814(n-1) ; d := (n-1)/2^s ; if modp(b &^ d, n) = 1 then return true; else for r from 0 to s-1 do if modp(b &^ d, n) = n-1 then return true; end if; d := 2*d ; end do: return false; end if; end if; end proc: isA001262 := proc(n) isStrongPsp(n, 2) ; end proc:
for n from 1 by 2 do if isA001262(n) then print(n); end if; end do:
MATHEMATICA
sppQ[n_?EvenQ, _] := False; sppQ[n_?PrimeQ, _] := False; sppQ[n_, b_] := (s = IntegerExponent[n-1, 2]; d = (n-1)/2^s; If[PowerMod[b, d, n] == 1, Return[True], Do[If[PowerMod[b, d, n] == n-1, Return[True]]; d = 2*d, {s}]]); lst = {}; k = 3; While[k < 500000, If[sppQ[k, 2], Print[k]; AppendTo[lst, k]]; k += 2]; lst (* Jean-François Alcover, Oct 20 2011, after R. J. Mathar *)
PROG
(PARI)
isStrongPsp(n, b)={
my(s, d, r, bm) ;
if( (n% 2) ==0 || n <=1, return(0) ; ) ;
if(isprime(n), return(0) ; ) ;
s = valuation(n-1, 2) ;
d = (n-1)/2^s ;
bm = Mod(b, n)^d ;
if ( bm == Mod(1, n), return(1) ; ) ;
for(r=0, s-1,
bm = Mod(b, n)^d ;
if ( bm == Mod(-1, n),
return(1) ;
) ;
d *= 2;
) ;
return(0);
}
isA001262(n)={
isStrongPsp(n, 2)
}
{
for(n=1, 10000000000,
if(isA001262(n),
print(n)
) ;
) ;
(PARI) is_ A001262(n, a=2)={ (bittest(n, 0) && !isprime(n) && n>8) || return; my(s=valuation(n-1, 2)); if(1==a=Mod(a, n)^(n>>s), return(1)); while(a!=-1 && s--, a=a^2); a==-1} \\ M. F. Hasler, Aug 16 2012
Strong pseudoprimes to base 3.
+10
25
121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, 44287, 47197, 55969, 63139, 74593, 79003, 82513, 87913, 88573, 97567, 105163, 111361, 112141, 148417, 152551, 182527, 188191, 211411, 218791, 221761, 226801
MATHEMATICA
sppQ[n_?EvenQ, _] := False; sppQ[n_?PrimeQ, _] := False; sppQ[n_, b_] := (s = IntegerExponent[n-1, 2]; d = (n-1)/2^s; If[PowerMod[b, d, n] == 1, Return[True], Do[If[PowerMod[b, d*2^r, n] == n-1, Return[True]], {r, 0, s-1}]]); A020229 = {}; lst = {}; k = 3; While[k < 500000, If[sppQ[k, 3], Print[k]; AppendTo[lst, k]]; k += 2]; lst (* Jean-François Alcover, Oct 20 2011, after R. J. Mathar *)
PROG
(PARI) is_ A020229(n, b=3)={ bittest(n, 0) || return; ispseudoprime(n) && return; my(d=(n-1)>>valuation(n-1, 2)); Mod(b, n)^d==1 || until(n-1<=d*=2, Mod(b, n)^d+1 || return(1))} \\ M. F. Hasler, Jul 19 2012
Strong pseudoprimes to base 5.
+10
20
781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539, 38081, 40501, 44801, 53971, 79381, 100651, 102311, 104721, 112141, 121463, 133141, 141361, 146611, 195313, 211951, 216457, 222301, 251521, 289081, 290629, 298271, 315121
MATHEMATICA
nmax = 400000; sppQ[n_?EvenQ, _] := False; sppQ[n_?PrimeQ, _] := False; sppQ[n_, b_] := (s = IntegerExponent[n-1, 2]; d = (n-1)/2^s; If[ PowerMod[b, d, n] == 1, Return[True], Do[If[PowerMod[b, d*2^r, n] == n-1, Return[True]], {r, 0, s - 1}]]); A020231 = {}; n = 1; While[n < nmax, n = n+2; If[sppQ[n, 5] == True, Print[n]; AppendTo[ A020231, n]]]; A020231 (* Jean-François Alcover, Oct 20 2011, after R. J. Mathar *)
Strong pseudoprimes to bases 2, 3, 5 and 7.
+10
11
3215031751, 118670087467, 307768373641, 315962312077, 354864744877, 457453568161, 528929554561, 546348519181, 602248359169, 1362242655901, 1871186716981, 2152302898747, 2273312197621, 2366338900801, 3343433905957, 3461715915661, 3474749660383, 3477707481751, 4341937413061, 4777422165601, 5537838510751
PROG
(PARI) sprp(n, b)=my(s=valuation(n-1, 2), d=Mod(b, n)^(n>>s)); if(d==1, return(1)); for(i=1, s-1, if(d==-1, return(1)); d=d^2; ); d==-1
Search completed in 0.013 seconds
| 