Displaying 1-10 of 24 results found.
25326001, 161304001, 960946321, 1157839381, 3215031751, 3697278427, 5764643587, 6770862367, 14386156093, 15579919981, 18459366157, 19887974881, 21276028621, 27716349961, 29118033181, 37131467521, 41752650241, 42550716781, 43536545821
COMMENTS
These first 13 numbers are the only ones less than 25*10^9 which are simultaneously strong pseudoprimes to bases 2, 3 and 5. Taken from the same table - which indicates (only) whether they are also strong pseudoprime (spsp) or pseudoprime (psp) to base 7, 11 and/or 13: 161304001 is spsp to 11; 3215031751 is spsp to base 7 and is psp to both bases 11 and 13; 5764643587 is spsp to base 13; 14386156093 is psp to bases 7, 11 and 13. 15579919981 is psp to base 7 and spsp to base 11; 19887974881 is psp to base 7; and 21276028621 is psp to bases 11 and 13.
REFERENCES
P. Ribenboim, The Little Book of Big Primes. Springer-Verlag, NY, 1991, pp. 82-83.
LINKS
Pomerance, C., Selfridge, J.L. and Wagstaff, Jr., S.S. The pseudoprimes to 25*10^9, Mathematics of Computation 35, 1980, pp. 1003-1026.
Strong pseudoprimes to base 2.
+10
75
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 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 base 7.
+10
15
25, 325, 703, 2101, 2353, 4525, 11041, 14089, 20197, 29857, 29891, 39331, 49241, 58825, 64681, 76627, 78937, 79381, 87673, 88399, 88831, 102943, 109061, 137257, 144901, 149171, 173951, 178709, 188191, 197633, 219781, 227767, 231793, 245281
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
Strong pseudoprimes to base 4.
+10
10
341, 1387, 2047, 3277, 4033, 4371, 4681, 5461, 8321, 8911, 10261, 13747, 14491, 15709, 15841, 19951, 29341, 31621, 42799, 49141, 49981, 52633, 60787, 65077, 65281, 74665, 80581, 83333, 85489, 88357, 90751, 104653, 123251, 129921, 130561, 137149
CROSSREFS
Cf. A020136 (base 4), A001262 (base 2), A020229 (base 3), A020231 (base 5), A020232 (base 6), A020233 (base 7), A020234 (base 8), A020235 (base 9), A020236 (base 10), A020237 (base 11), A020238 (base 12).
Strong pseudoprimes to base 6.
+10
9
217, 481, 1111, 1261, 2701, 3589, 5713, 6533, 11041, 14701, 20017, 29341, 34441, 39493, 43621, 46657, 46873, 49141, 49661, 58969, 74023, 74563, 76921, 83333, 87061, 92053, 94657, 94697, 97751, 97921, 109061, 115921, 125563, 128627, 151387, 173377
Strong pseudoprimes to base 8.
+10
7
9, 65, 481, 511, 1417, 2047, 2501, 3277, 3641, 4033, 4097, 4681, 8321, 11041, 15841, 16589, 19561, 24311, 24929, 29341, 41441, 42799, 45761, 49141, 52429, 52633, 54161, 55969, 56033, 59291, 61337, 65281, 66197, 74023, 74665, 77161, 80581, 85489, 87061
Strong pseudoprimes to base 9.
+10
7
91, 121, 671, 703, 1541, 1729, 1891, 2821, 3281, 3367, 3751, 5551, 7381, 8401, 8911, 10585, 11011, 12403, 14383, 15203, 16471, 16531, 18721, 19345, 23521, 24661, 24727, 28009, 29341, 30857, 31621, 32791, 38503, 44287, 46999, 47197, 49051, 49141, 53131
Number of witnesses for strong pseudoprimality of 2n+1, i.e., number of bases b, 1 <= b <= 2n, in which 2n+1 is a strong pseudoprime.
+10
7
2, 4, 6, 2, 10, 12, 2, 16, 18, 2, 22, 4, 2, 28, 30, 2, 2, 36, 2, 40, 42, 2, 46, 6, 2, 52, 2, 2, 58, 60, 2, 6, 66, 2, 70, 72, 2, 2, 78, 2, 82, 6, 2, 88, 18, 2, 2, 96, 2, 100, 102, 2, 106, 108, 2, 112, 2, 2, 2, 10, 2, 4, 126, 2, 130, 18, 2, 136, 138, 2, 2, 6, 2, 148, 150, 2, 2, 156, 2, 2
COMMENTS
Number of integers b, 1 <= b <= 2n, such that if 2n = 2^k*m with odd m, then the sequence (b^m, b^(2*m), ..., b^(2^k*m)) modulo 2n+1 satisfies the Rabin-Miller test.
The subsequence related to composite 2n+1 is characterized with records in A195328 and associated 2n+1 tabulated in A141768. Let N = 2n+1 = product_{i=1..s} p_i^r_i be the prime factorization of the odd 2n+1. Related odd parts q and q_i are defined by N-1=2^k*q and p_i-1 = 2^(k_i)*q_i, with sorting such that k_1 <= k_2 <=k_3... Then a(n) = (1+sum_{j=0..k1-1} 2^(j*s)) *product_{i=1..s} gcd(q,qi).
Reduces to A006093 if 2n+1 is prime. This might be correlated with 2* A195508(n). (End)
REFERENCES
Paulo Ribenboim, The Little Book of Bigger Primes, 2nd ed., Springer-Verlag, New York, 2004, p. 98.
FORMULA
For k = 2*n+1, a(k) = k - 1 if k is prime, otherwise, a(k) = (1 + 2^(omega(k)*nu(k)) - 1)/(2^omega(k)-1)) * Product_{p|k} gcd(od(k-1), od(p-1)), where omega(m) is the number of distinct prime factors of m ( A001221), od(m) is the largest odd divisor of m ( A000265) and nu(m) = min_{p|m} A007814(p-1). - Amiram Eldar, Nov 08 2019
MAPLE
rabinmiller := proc(n, a); k := 0; mu := n-1; while irem(mu, 2)=0 do k := k+1; mu := mu/2 od; G := a&^mu mod(n); h := 0; if G=1 then RETURN(1) else while h<k-1 and G&^2 mod n <>1 do h := h+1; G := G&^2 mod n; od; if h<k and G<> n-1 then RETURN(0) else RETURN(1) fi; if G=1 then RETURN(1); fi; fi; end; compte := proc(n) local l; RETURN(sum('rabinmiller(2*n+1, l)', 'l'=1..2*n)); end;
n/2^padic[ordp](n, 2) ;
end proc:
a := proc(n)
B := 1;
s := 0 ;
k1 := 10000000000000 ;
for pf in ifactors(n)[2] do
pi := op(1, pf) ;
ki := ilog2((pi-1)/qi) ;
k1 := min(k1, ki) ;
B := B*igcd(q, qi) ;
s := s+1 ;
end do:
1+add(2^(j*s), j=0..k1-1) ;
return B*% ;
end proc:
seq(a(2*n+1), n=1..60) ;
MATHEMATICA
o[n_] := (n-1)/2^IntegerExponent[n-1, 2]; a[n_?PrimeQ] := n-1; a[n_] := Module[{p = FactorInteger[n][[;; , 1]]}, om = Length[p]; Product[GCD[o[n], o[p[[k]]]], {k, 1, om}] * (1 + (2^(om * Min[IntegerExponent[#, 2]& /@ (p - 1)]) - 1)/(2^om - 1))]; Table[a[n], {n, 3, 121, 2}] (* Amiram Eldar, Nov 08 2019 *)
AUTHOR
J.-F. Guiffes (guiffes.jean-francois(AT)wanadoo.fr), Jun 11 2002
Search completed in 0.020 seconds
| 