|
%I #58 Mar 09 2022 01:01:18
%S 3277,29341,49141,80581,88357,104653,196093,314821,458989,489997,
%T 800605,838861,873181,1004653,1251949,1373653,1509709,1678541,1811573,
%U 1987021,2269093,2284453,2387797,2746477,2909197,3400013,3429037,3539101,3605429,4360621,4502485,5590621,5599765
%N Composite numbers k congruent to 5 (mod 8) such that 2^((k-1)/2) mod k = k-1.
%C This sequence contains the n mod 8 = 5 pseudoprimes to the following modified Fermat primality criterion:
%C Conjecture 1: if p is an odd prime congruent to {3,5} (mod 8) then 2^((p-1)/2) mod p = p-1.
%C This conjecture has been tested to 10^8.
%C This criterion produces far fewer pseudoprimes than the 2^(n-1) mod n = 1 test and thus has a higher probability of success. The number of pseudoprimes for the two tests up to 10^k are:
%C 10^5 5 26 19.23%
%C 10^6 13 78 16.66%
%C 10^7 40 228 17.54%
%C There are 40 terms < 10^7. If an additional constraint 3^(n-1) mod n = 1 and 5^(n-1) mod n = 1 is added, only 4 terms remain: (29341, 314821, 873181, 9863461).
%C This sequence appears to be a subset of A175865, A001262, A047713, A020230.
%C Number of terms below 10^k for k = 5..15: 5, 13, 40, 132, 369, 975, 2534, 6592, 17403, 45801, 122473. The corresponding numbers for 2^(n-1) mod n = 1: 26, 78, 228, 637, 1718, 4505, 11645, 29902, 76587, 197455, 513601. - _Jens Kruse Andersen_, Jul 13 2014
%C Also composite numbers 2n+1 with n even such that 2n+1 | 2^n+1. - _Hilko Koning_, Jan 27 2022
%C Conjecture 1 is true. With p = 2k+1 then 2^k mod (2k+1) == 2k. So 2k+1 | 2k-2^k. Prime numbers 2k+1 == +-3 (mod 8) are the prime numbers such that 2k+1 | 2^k+1 (Comments A007520). A reflection across the x-axis and +1 translation across the y-axis of the graph (2k-2^k) / (2k+1) gives the graph (2^k+1) / (2k+1). So the k values of both 2k+1 | 2k-2^k and 2k+1 | 2^k+1 are identical. - _Hilko Koning_, Feb 04 2022
%H Jens Kruse Andersen, <a href="/A244626/b244626.txt">Table of n, a(n) for n = 1..10000</a>
%p for n from 5 to 10^7 by 8 do if 2^((n-1)/2) mod n = n-1 and not isprime(n) then print(n) fi od;
%Y Cf. A001567, A003629, A070179.
%K nonn
%O 1,1
%A _Gary Detlefs_, Jul 02 2014
%E a(18) corrected by _Jens Kruse Andersen_, Jul 13 2014
|
