A244628 - OEIS

%I #62 Mar 09 2022 01:01:54

%S 476971,877099,1302451,1325843,1397419,1441091,1507963,1530787,

%T 1907851,2004403,3090091,3116107,5256091,5919187,7883731,9371251,

%U 11081459,11541307,12263131,13057787,13338371,15976747,17134043,18740971,19404139,20261251,21623659,22075579,24214051

%N Composite numbers n such that n == 3 (mod 8) and 2^((n-1)/2) == -1 (mod n).

%C This sequence contains the n mod 8 = 3 pseudoprimes to the following modified Fermat primality criterion:

%C Conjecture 1: if p is a 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 modified primality test has far fewer pseudoprimes than the 2^(n-1) mod n = 1 test and thus has a much higher probability of success. The number of pseudoprimes up to 10^k for the two tests are:

%C    10^3 0     0

%C    10^4 0     2

%C    10^5 0     5

%C    10^6 2    14

%C    10^7 16   48

%C This sequence appears to be a subset of the composites in A175865.

%C The n mod 8 = 3 pseudoprimes are much rarer than the n mod 8 = 5 pseudoprimes. There are 16 terms < 10^7. If the additional constraints 3^(n-1) mod n = 1 and 5^(n-1) mod n = 1 are added, no terms remain.

%C Number of terms < 10^k: 0, 0, 0, 0, 0, 2, 16, 50, 132, ..., . - _Robert G. Wilson v_, Jul 21 2014

%C Number of terms < 10^k for k=5..15: 0, 2, 16, 50, 132, 341, 876, 2330, 6234, 16625, 44885. - _Jens Kruse Andersen_, Jul 27 2014

%C It appears that the terms of the sequence are also the composite numbers of A294912. - _Hilko Koning_, Dec 05 2019

%C Also composite numbers 2k+1 with k odd such that 2k+1 | 2^k+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="/A244628/b244628.txt">Table of n, a(n) for n = 1..10000</a> (first 132 terms from Robert G. Wilson v)

%p for n from 3 to 10^8 by 8 do if Power(2,(n-1)/2) mod n =  n -1 and not isprime(n) then print(n) fi od

%t fQ[n_] := !PrimeQ@ n && PowerMod[2, (n - 1)/2, n] == n - 1; k = 3; lst = {}; While[k < 10^8, If[fQ@ k, AppendTo[lst, k]]; k += 8]; lst (* _Robert G. Wilson v_, Jul 21 2014 *)

%Y Cf. A003629, A070179, A175865.

%K nonn

%O 1,1

%A _Gary Detlefs_, Jul 02 2014