OFFSET
1,1
COMMENTS
Old name was: Fermat pseudoprimes to base 2 of the form 8*p*n + p^2, where p is prime and n natural.
For p = 5 the formula becomes 40*n + 25. From the first 15 pseudoprimes divisible by 5, 12 are of the form 40*n + 25 (beside 3 of them which are of the form 40*n + 5). Conjecture: there are no pseudoprimes to base 2 of the form 40*n + 15.
Note: it can be seen that a pseudoprime can be written in this formula in more than one way: e.g., 561 = 8*3*23 + 3^2 = 8*11*5 + 11^2 = 8*17*2 + 17^2 or 1905 = 8*3*79 + 3^2 = 8*5*47 + 5^2.
Conjecture: If a Fermat pseudoprime to base 2 can be written as 8*p*n + p^2, where n is an integer and p one of its prime factors, then it can be written this way for any of its prime factors. Checked for all pseudoprimes from the sequence above.
Conjecture: If a Fermat pseudoprime to base 2 with two prime factors can be written as 8*p1*n + p1^2, where n is a natural number and p1 one of its two prime factors, then it can also be written as 8*p2*(-n) + p2^2, where p2 is the other prime factor. Checked for 4033 = 37*109(n = 9), 4369 = 17*257(n = 30), 4681 = 31*151(n = 15), 8321 = 53*157(n = 13), 18721 = 97*193(n = 12), 23377 = 97*241(n = 18), 31417 = 89*353(n = 33), 31609 = 73*433 (n = 45), 65281 = 97*673(n = 72), 85489 = 53*1613 (n = 195).
Conjecture: If a Fermat pseudoprime to base 2 cannot be written as 8*p*n + p^2, where n is an integer and p one of its prime factors, then it cannot be written this way for any of its prime factors. Checked for the following pseudoprimes: 341, 645, 1387, 2047, 2701, 2821, 3277, 4371, 5461, 7957, 10261, 13741, 13747, 13981, 14491, 15709, 19951, 29341, 31621, 42799, 49141, 49981, 55245, 60701, 60787, 63973, 65077, 68101, 72885, 80581, 83333.
Note: from the first 72 pseudoprimes, 39 can be written this way.
All three conjectures are true (obvious from new characterization). - Charles R Greathouse IV, Dec 07 2014
LINKS
Amiram Eldar, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Fermat Pseudoprime.
Eric Weisstein's World of Mathematics, Poulet Number.
MAPLE
select(t -> 2 &^ t mod t = 2 and not isprime(t), [seq(1+8*j, j=0..10^5)]); # Robert Israel, Dec 07 2014
MATHEMATICA
Select[8 * Range[10^4] + 1, PowerMod[2, # - 1, #] == 1 && CompositeQ[#] &] (* Amiram Eldar, Mar 30 2021 *)
PROG
(PARI) is(n)=n%8==1 && Mod(2, n)^n==2 && !isprime(n) \\ Charles R Greathouse IV, Dec 07 2014
CROSSREFS
KEYWORD
nonn
AUTHOR
Marius Coman, Oct 30 2012
EXTENSIONS
Corrected by Charles R Greathouse IV, Dec 07 2014
New name from Charles R Greathouse IV, Dec 07 2014
STATUS
approved