A175865 -id:A175865 - cp's OEIS frontend

A244626 Composite numbers k congruent to 5 (mod 8) such that 2^((k-1)/2) mod k = k-1.

3277, 29341, 49141, 80581, 88357, 104653, 196093, 314821, 458989, 489997, 800605, 838861, 873181, 1004653, 1251949, 1373653, 1509709, 1678541, 1811573, 1987021, 2269093, 2284453, 2387797, 2746477, 2909197, 3400013, 3429037, 3539101, 3605429, 4360621, 4502485, 5590621, 5599765

Offset: 1

Gary Detlefs, Jul 02 2014

nonn

This sequence contains the n mod 8 = 5 pseudoprimes to the following modified Fermat primality criterion:
Conjecture 1: if p is an odd prime congruent to {3,5} (mod 8) then 2^((p-1)/2) mod p = p-1.
This conjecture has been tested to 10^8.
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:
   10^5    5   26     19.23%
   10^6   13   78     16.66%
   10^7   40  228     17.54%
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).
This sequence appears to be a subset of A175865, A001262, A047713, A020230.
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
Also composite numbers 2n+1 with n even such that 2n+1 | 2^n+1. - Hilko Koning, Jan 27 2022
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

Jens Kruse Andersen, Table of n, a(n) for n = 1..10000

Cf. A001567, A003629, A070179.

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;

a(18) corrected by Jens Kruse Andersen, Jul 13 2014

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

Original entry on oeis.org

476971, 877099, 1302451, 1325843, 1397419, 1441091, 1507963, 1530787, 1907851, 2004403, 3090091, 3116107, 5256091, 5919187, 7883731, 9371251, 11081459, 11541307, 12263131, 13057787, 13338371, 15976747, 17134043, 18740971, 19404139, 20261251, 21623659, 22075579, 24214051

Offset: 1

Gary Detlefs, Jul 02 2014

nonn

This sequence contains the n mod 8 = 3 pseudoprimes to the following modified Fermat primality criterion:
Conjecture 1: if p is a prime congruent to {3,5} mod 8 then 2^((p-1)/2) mod p = p-1.
This conjecture has been tested to 10^8.
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:
   10^3 0     0
   10^4 0     2
   10^5 0     5
   10^6 2    14
   10^7 16   48
This sequence appears to be a subset of the composites in A175865.
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.
Number of terms < 10^k: 0, 0, 0, 0, 0, 2, 16, 50, 132, ..., . - Robert G. Wilson v, Jul 21 2014
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
It appears that the terms of the sequence are also the composite numbers of A294912. - Hilko Koning, Dec 05 2019
Also composite numbers 2k+1 with k odd such that 2k+1 | 2^k+1. - Hilko Koning, Jan 27 2022
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

Jens Kruse Andersen, Table of n, a(n) for n = 1..10000 (first 132 terms from Robert G. Wilson v)

Cf. A003629, A070179, A175865.

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

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 *)

A224486 Numbers k such that 2*k+1 divides 2^k+1.

Original entry on oeis.org

1, 2, 5, 6, 9, 14, 18, 21, 26, 29, 30, 33, 41, 50, 53, 54, 65, 69, 74, 78, 81, 86, 89, 90, 98, 105, 113, 114, 125, 134, 138, 141, 146, 153, 158, 165, 173, 174, 186, 189, 194, 198, 209, 210, 221, 230, 233, 245, 249, 254, 261, 270, 273, 278, 281, 285, 293

Offset: 1

Jayanta Basu, Apr 07 2013

nonn

The numbers are called Curzon numbers by Tattersall (p. 85, exercise 43).

Sequence 2*a(n)+1 apparently is A175865 (certainly it is not A003629). - Joerg Arndt, Apr 07 2013

			5 is in the list since 2*5 + 1 = 11 divides 2^5 + 1 = 33.

James J. Tattersall, Elementary Number Theory in Nine Chapters, Second Edition, Cambridge University Press, 2005, p. 85.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Giovanni Resta, Curzon numbers, Numbers Aplenty.

Cf. A000051, A175865, A224499.

Select[Range[300], PowerMod[2, #, 2 # + 1] == 2 # &] (* Amiram Eldar, Oct 13 2020 *)

for(n=0, 10^3, my(m=2*n+1); if( Mod(2,m)^n==Mod(-1,m), print1(n, ", ") ) ); \\ Joerg Arndt, Apr 08 2013

A214151 Numbers k from the set == 5 (mod 6) with the property that 3^((3*k-1)/2) == 3 (mod k) and 2^((k-1)/2) == (k-1) (mod k).

Original entry on oeis.org

11, 59, 83, 107, 131, 179, 227, 251, 347, 419, 443, 467, 491, 563, 587, 659, 683, 827, 947, 971, 1019, 1091, 1163, 1187, 1259, 1283, 1307, 1427, 1451, 1499, 1523, 1571, 1619, 1667, 1787, 1811, 1907, 1931, 1979, 2003, 2027, 2099, 2243, 2267

Offset: 1

Alzhekeyev Ascar M, Jul 05 2012

nonn

All composites in this sequence are 2-pseudoprimes, see A001567, and strong pseudoprimes to base 2, A001262.
The subsequence of these composites begins: 1441091, 3587553971, 4528686251, 23260036451, 47535120323, 61070250323, 90474845819, 143193768587, 162016315907, 173868807611, 180998962187, 238364070323, 285370693931, 298577370323, ...
Perhaps this sequence contains all the terms of the sequence A107007 or A168539.

Harvey P. Dale, Table of n, a(n) for n = 1..1000

Subsequence of A176997.

Cf. A003629, A006970, A175865.

isA214151 := proc(n)
    if (n mod 6 = 5) and modp(2 &^ ((n-1)/2),n)  = n-1 and modp(3 &^ ((3*n-1)/2),n)  = 3 then
        true;
    else
        false;
    end if;
end proc:
for n from 5 by 6 do
    if isA214151(n) then
        print(n) ;
    end if;
end do: # R. J. Mathar, Jul 20 2012

Select[Range[5,2500,6],PowerMod[3,(3#-1)/2,#]==3&&PowerMod[2,(#-1)/2,#] == #-1&] (* Harvey P. Dale, Mar 14 2022 *)

for(n=0, 200, b=6*n+5; if(Mod(3, b)^((3*b-1)/2)==3, if(Mod(2, b)^((b-1)/2)==b-1 , print1(b, ", "))));

A270699 Integers n such that A084158(n) is divisible by n.

Original entry on oeis.org

1, 3, 5, 11, 13, 15, 19, 29, 35, 37, 43, 53, 59, 61, 67, 75, 83, 101, 107, 109, 119, 131, 139, 149, 157, 163, 173, 179, 181, 195, 197, 211, 227, 229, 251, 255, 269, 277, 283, 293, 307, 317, 331, 347, 349, 373, 375, 379, 389, 397, 419, 421, 435, 443, 455, 461, 467, 491, 499

Offset: 1

Altug Alkan, Mar 21 2016

For prime terms of this sequence, see A003629. Additionally, these prime numbers have the property that is in definition of A175865. Nonprime terms of this sequence are 1, 15, 35, 75, 119, 195, 255, 375, 435, 455, ...

			3 is a term because 1^2 + 2^2 + 5^2 = 30 is divisible by 3.
5 is a term because 1^2 + 2^2 + 5^2 + 12^2 + 29^2 = 1015 is divisible by 5.
13 is a term because A084158(13) = 1351523251 is divisible by 13.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A000129, A003629, A084158, A175865.

nn = 500; s = LinearRecurrence[{5, 5, -1}, {0, 1, 5}, nn + 1]; Select[Range@ nn, Divisible[s[[# + 1]], #] &] (* Michael De Vlieger, Mar 23 2016, after Harvey P. Dale at A270699 *)

is(n)=(Mod([0, 1, 0; 0, 0, 1; -1, 5, 5],n)^n*[0; 1; 5])[1, 1]==0 \\ Charles R Greathouse IV, Mar 21 2016

cp's OEIS Frontend

A244626 Composite numbers k congruent to 5 (mod 8) such that 2^((k-1)/2) mod k = k-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A224486 Numbers k such that 2*k+1 divides 2^k+1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

A214151 Numbers k from the set == 5 (mod 6) with the property that 3^((3*k-1)/2) == 3 (mod k) and 2^((k-1)/2) == (k-1) (mod k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A270699 Integers n such that A084158(n) is divisible by n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI