Francois R. Grieu - cp's OEIS frontend

A374976 Odd k with p^k mod k != p for all primes p.

1, 9, 27, 63, 75, 81, 115, 119, 125, 189, 207, 209, 215, 235, 243, 279, 299, 319, 323, 387, 407, 413, 423, 515, 517, 531, 535, 551, 567, 575, 583, 611, 621, 623, 667, 675, 707, 713, 729, 731, 747, 767, 779, 783, 799, 815, 835, 851, 869, 893, 899, 917, 923, 927

Offset: 1

Francois R. Grieu, Jul 26 2024

nonn

Alternatively: 1, and odd composites not a pseudoprime to any prime base.

The sequence contains no primes, no pseudoprimes to any prime base (A001567, A005935, A005936, A005938, A020139, A020141...), and no Carmichael numbers (A002997).

			k=3 (resp. 5, 7) is not in the sequence because for prime p=2 it holds p^k mod k = 2 which is p.
k=9 is in the sequence because for prime p=2 (resp. 3, 5, 7) it holds p^k mod k = 8 (resp. 0, 8, 1) which is not p, and for all other primes p it holds p>=k therefore p^k mod k can't be p.

Francois R. Grieu, Table of n, a(n) for n = 1..10000

Cf. A000040, A001567, A005935, A005936, A005938, A020139, A020141, A020145, A002997.

Cases[Range[1, 930, 2], k_/; (For[p=2, p=k)]

A337119 Primes p such that b^(p-1) == 1 (mod p-1) for all b coprime to p-1.

Original entry on oeis.org

2, 3, 5, 7, 13, 17, 19, 37, 41, 43, 61, 73, 97, 101, 109, 127, 157, 163, 181, 193, 241, 257, 313, 337, 379, 401, 421, 433, 487, 541, 577, 601, 641, 661, 673, 757, 769, 881, 883, 937, 1009, 1093, 1153, 1201, 1249, 1297, 1321, 1361, 1459, 1601, 1621, 1801, 1861, 1873, 2017, 2029, 2053, 2161, 2269, 2341, 2437, 2521, 2593

Offset: 1

Francois R. Grieu, Aug 17 2020

nonn

Equivalently: primes p to p-1 a Novák-Carmichael number A124240.
These p are such that for all x in [0,p), and all b coprime to p-1, x^(b^(p-1)) == x (mod p), this follows from the FLT.
Equivalently, primes p such that for all primes q | p-1, q-1 | p-1. Primes such that p-1 is in A124240. No prime of the form 12k+11 is in this sequence. - Paul Vanderveen, Apr 02 2022
Primes p such that B^(b^(p-1)-1) == 1 (mod p^2) for every B coprime to p and for every b coprime to (p-1)*p. - Thomas Ordowski, Sep 01 2024

			7 is in the sequence because it is prime, 1 and 5 are the integers (mod 6) coprime to 6; 1^6 mod 6 = 1; and 5^6 mod 6 = 1.
11 is not in the sequence because 3 is coprime to 10; and 3^10 mod 10 = 9 <> 1.

Michael S. Branicky, Table of n, a(n) for n = 1..10000 (terms 1..300 from Harvey P. Dale)

Cf. A124240.

a={}; For[p=2,p<2600, p=NextPrime[p],b=p-1; While[--b>0&&(GCD[b,p-1]!=1||PowerMod[b,p-1,p-1]==1)];If[b==0,AppendTo[a,p]]];a
bcpQ[n_]:=Module[{b=Select[Range[n-2],CoprimeQ[n-1,#]&]},AllTrue[ b,PowerMod[ #,n-1,n-1]==1&]]; Select[Prime[Range[400]],bcpQ] (* Harvey P. Dale, Jan 01 2022 *)

from math import gcd
from sympy import isprime
def ok(n):
    if not isprime(n): return False
    return all(pow(b, n-1, n-1) == 1 for b in range(2, n) if gcd(b, n-1)==1)
print([k for k in range(2594) if ok(k)]) # Michael S. Branicky, Apr 02 2022

A316970 Reducible binary polynomials P of degree n>0 with P dividing the polynomial X^(2^n-1)+1, evaluated at X=2 (pseudo-primes in the ring GF(2)[X]).

Original entry on oeis.org

83, 101, 127, 279, 443, 465, 1137, 1207, 1219, 1395, 1453, 1503, 1547, 1561, 1653, 1667, 1787, 1897, 1903, 1975, 2013, 4111, 4169, 4191, 4231, 4255, 4377, 4415, 4445, 4585, 4599, 4673, 4681, 4699, 4763, 4779, 4819, 4849, 4867, 4881, 4895, 4917, 5013, 5021, 5113, 5167, 5173, 5187, 5207, 5339, 5389, 5433, 5447

Offset: 1

Francois R. Grieu, Jul 17 2018

nonn

If a binary polynomial P of degree n is irreducible, then demonstrably P divides the polynomial X^(2^n-1)+1.
All irreducible polynomials A014580 pass this test, requiring O(n^3) bit operations and O(n) bits with classical algorithms.
Polynomials which pass this test but are not irreducible form the sequence.
Analog for GF(2)[X] of Fermat pseudoprimes A001567.
When P includes the constant term 1 (as all primitive polynomials do), the test is equivalent to X^(2^n)=X(mod P), which is easier to compute.

			83, that is 1010011 in binary, represents the polynomial P(X)=X^6+X^4+X+1 of degree n=6. It is in the sequence because X^63+1 == 0 (mod P), and P is reducible since P(X)=(X+1)(X^2+X+1)(X^3+X+1) in GF(2)[X].

Francois R. Grieu, Test of irreducibility of a binary polynomial, Math StackExchange July 2018.
Index entries for sequences related to polynomials in ring GF(2)[X]

Cf. A014580. Subsequence of A091242.

For[p=3,p<5449,p+=2,P=0;Y=1;m=p;While[m>0,If[OddQ[m],P+=Y;m-=1];Y*=x;m/=2];If[PolynomialRemainder[x^(2^Exponent[P,x]-1),P,x,Modulus->2]==1&&!IrreduciblePolynomialQ[P,Modulus->2],Print[p]]]

A301643 Strong pseudo safe-primes: numbers n = 2m+1 with 2^m == +-1 (mod n) and m a strong pseudoprime A001262.

Original entry on oeis.org

715523, 2651687, 2882183, 10032383, 14924003, 15640403, 30278399, 32140859, 45698963, 86727203, 129210083, 202553159, 257330639, 271938803, 274831643, 294056003, 307856267, 332164619, 413008067, 437894243, 447564527, 494832203, 654796019, 689552603, 735119003

Offset: 1

Francois R. Grieu, Mar 25 2018

nonn

Equivalently, numbers n = 2m+1 that are not safe primes A005385 even though n and m are strong probable primes (that is, prime or strong pseudoprime A001262). That follows from a result by Fedor Petrov.

All known terms are prime, including the 542622 less than 2^65 (obtained by post-processing Jan Feitsma and William Galway's table).

			n = 715523 is in the sequence because n = 2m+1 with m = 357761, and 2^m mod n = 715522 which is among 1 or n-1 (the latter), and m is a strong pseudoprime A001262. The latter holds because m = 131*2731 is composite, and m passes the strong probable prime test. The latter holds because when writing m-1 as d*(2^s) with d odd, it holds that 2^d mod m = 1 or there exists an r with 0 <= r < s and 2^(d*(2^r)) == -1 (mod m); specifically, d = 2795, s = 7, 2^2795 mod 357761 = 357760 = m-1, thus 2^(d*(2^r)) == -1 (mod m) for r = 0.

Jan Feitsma, The pseudoprimes below 2^64
William Galway, Tables of pseudoprimes and related data [Includes a file with pseudoprimes up to 2^64.]
Fedor Petrov, The question's congruence and m prime imply n prime, MathOverflow.

Subsequence of A300193.

Cf. A001262, A005385.

For[m=3,(n=2m+1)<13^8,m+=2,If[MemberQ[{1,n-1},PowerMod[2,m,n]]&&(d=m-1;t=1;While[EvenQ[d],d/=2;++t];If[(x=PowerMod[2,d,m])!=1,While[--t>0&&x!=m-1,x=Mod[x^2,m]]];t>0)&&!PrimeQ[m],Print[n]]]

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; } \\ after A001262
isok(n) = if (n%2, my(m = (n-1)/2, r = Mod(2, n)^m); ((r==1) || (r==-1)) && is_A001262(m)); \\ derived from Michel Marcus, May 07 2018

A300193 Pseudo-safe-primes: numbers n = 2m+1 with 2^m congruent to n+1 or 3n-1 modulo m*n, but m composite.

Original entry on oeis.org

683, 1123, 1291, 4931, 16963, 25603, 70667, 110491, 121403, 145771, 166667, 301703, 424843, 529547, 579883, 696323, 715523, 854467, 904103, 1112339, 1175723, 1234187, 1306667, 1444523, 2146043, 2651687, 2796203, 2882183, 3069083, 3216931, 4284283, 4325443

Offset: 1

Francois R. Grieu, Mar 05 2018

nonn

The definition's congruence is verified if n is a safe prime A005385 with m the corresponding Sophie Germain prime A005384; and for a few other n, which form the sequence.
If that congruence is verified and m is prime, then n is prime (follows from a result by Fedor Petrov).
That congruence is equivalent to the combination: 2^m == +-1 (mod n) and 2^m == 2 (mod m).
Composite n are Euler pseudoprimes A006970, and strong pseudoprimes A001262 if m is odd. The smallest is a(6534) = (2^47+1)/3 = 46912496118443 = 283*165768537521 (cf. A303448). See Peter Košinár link.
Even m belong to A006935. The first is a(986) = 252435584573, m = 126217792286 (cf. A303008).

			n = 683 = 2*341+1 is in the sequence because 2^341 == 2048 == 3*n-1 (mod 341*683) and m = 341 = 11*13 is composite.
n = 301703 = 2*150851+1 is in the sequence because 2^150851 == 301704 == n+1 (mod 150851*301703) and m = 150851 = 251*601 is composite.
n = 5 = 2*2+1 is not in the sequence because m = 2 is prime.

Francois R. Grieu, Table of n, a(n) for n = 1..2796 (terms <2^42).
Peter Košinár, Report of a composite n, Math StackExchange, Mar 06 2018.
Fedor Petrov, Proof that the congruence and m prime imply n prime, MathOverflow.

Cf. A005385, A005384, A000040, A001262, A001567, A006935, A006970.

For[m=1,(n=2m+1)<4444444,++m,If[MemberQ[{n+1,3n-1},PowerMod[2,m,m*n]] &&!PrimeQ[m], Print[n]]] (* Francois R. Grieu, Mar 19 2018 *)

isok(n) = {if ((n % 2) && (m=(n-1)/2) && !isprime(m), v = lift(Mod(2, m*n)^m); if ((v == n+1) || (v == 3*n-1), return (1));); return (0);} \\ Michel Marcus, Mar 06 2018

A132448 First primitive polynomial over GF(2) of degree n, X^n suppressed.

Original entry on oeis.org

1, 3, 3, 3, 5, 3, 3, 29, 17, 9, 5, 83, 27, 43, 3, 45, 9, 39, 39, 9, 5, 3, 33, 27, 9, 71, 39, 9, 5, 83, 9, 175, 83, 231, 5, 119, 63, 99, 17, 57, 9, 63, 89, 101, 27, 303, 33, 183, 113, 29, 75, 9, 71, 125, 71, 149, 45, 99, 123, 3, 39, 105, 3, 27, 27, 365, 39, 163

Offset: 1

Francois R. Grieu, Aug 22 2007

nonn

More precisely: minimum value for X=2 of polynomials P[X] with coefficients in GF(2) such that X^n+P[X] is primitive. Applications include maximum-length linear feedback shift registers with efficient implementation in software.

			a(11)=5, or 101 in binary, representing the GF(2)[X] polynomial X^2+1, because X^11+X^2+1 is primitive, contrary to X^11, X^11+1, X^11+X^1, X^11+X^1+1 and X^11+X^2.

Francois R. Grieu, Table of n, a(n) for n = 1..400 (using Joerg Arndt's table).
Joerg Arndt, Binary primitive polynomials with lowest-most possible set bits
Index entries for sequences operating on GF(2)[X]-polynomials

2^n+a(n) is the smallest member of A091250 at least 2^n. A132447(n) = a(n)+2^n and gives the corresponding primitive polynomial. Cf. A132450, similar, with restriction to at most 5 terms. Cf. A132452, similar, with restriction to exactly 5 terms. Cf. A132454, similar, with restriction to minimal number of terms.

i2px[i_]:=If[i>1,BitAnd[i,1]+i2px[BitShiftRight[i,1]]x,i ];s={1};For[n=2,n<69,++n,For[i=3,!PrimitivePolynomialQ[i2px[i]+x^n,2],i+=2];AppendTo[s,i]];s (* Francois R. Grieu, Jan 15 2021 *)

More terms from Francois R. Grieu, Jan 12 2021

A132449 First primitive GF(2)[X] polynomial of degree n with at most 5 terms.

Original entry on oeis.org

3, 7, 11, 19, 37, 67, 131, 285, 529, 1033, 2053, 4179, 8219, 16427, 32771, 65581, 131081, 262183, 524327, 1048585, 2097157, 4194307, 8388641, 16777243, 33554441, 67108935, 134217767, 268435465, 536870917, 1073741907, 2147483657

Offset: 1

Francois R. Grieu, Aug 22 2007

nonn

More precisely: minimum value for X=2 of primitive GF(2)[X] polynomials of degree n with at most 5 terms. Applications include maximum-length linear feedback shift registers with efficient implementation in both hardware and software. The limitation to 5 terms occurs first for a(32), which is 4294967493 representing X^32+X^7+X^6+X^2+1, rather than 4294967471 representing X^32+X^7+X^5+X^3+X^2+X^1+1. Proof is needed that there exists a primitive GF(2)[X] polynomial P[X] of degree n and at most 5 terms for all positive n.

			a(5)=37, or 100101 in binary, representing the GF(2)[X] polynomial X^5+X^2+1, because it has degree 5 and no more than 5 terms and is primitive, contrary to X^5, X^5+1, X^5+X^1, X^5+X^1+1 and X^5+X^2.

Index entries for sequences operating on GF(2)[X]-polynomials

Subset of A091250. A132450(n) = a(n)-2^n, giving a more compact representation. Cf. A132447, similar, with no restriction on number of terms. Cf. A132451, similar, with restriction to exactly 5 terms. Cf. A132453, similar, with restriction to minimal number of terms.

A132450 First primitive GF(2)[X] polynomials of degree n with at most 5 terms, X^n suppressed.

Original entry on oeis.org

1, 3, 3, 3, 5, 3, 3, 29, 17, 9, 5, 83, 27, 43, 3, 45, 9, 39, 39, 9, 5, 3, 33, 27, 9, 71, 39, 9, 5, 83, 9, 197, 83, 281, 5, 387, 83

Offset: 1

Francois R. Grieu, Aug 22 2007

More precisely: minimum value for X=2 of GF(2)[X] polynomials P[X] with at most 4 terms such that X^n+P[X] is primitive. Applications include maximum-length linear feedback shift registers with efficient implementation in both hardware and software. The limitation of the number of terms occurs first for a(32), which is 197 representing X^7+X^6+X^2+1, rather than 175 representing X^7+X^5+X^3+X^2+X^1+1. Proof is needed that there exists a primitive GF(2)[X] polynomial P[X] of degree n and at most 5 terms for all positive n.

			a(11)=5, or 101 in binary, representing the GF(2)[X] polynomial X^2+1, because X^11+X^2+1 has no more than 5 terms and X is primitive, contrary to X^11, X^11+1, X^11+X^1, X^11+X^1+1 and X^11+X^2.

Index entries for sequences operating on GF(2)[X]-polynomials

2^n+a(n) belongs to A091250. A132449(n) = a(n)+2^n and gives the corresponding primitive polynomial. Cf. A132448 (similar, with no restriction on number of terms). Cf. A132452 (similar, with restriction to exactly 5 terms).

A132451 First primitive GF(2)[X] polynomials of degree n with exactly 5 terms.

Original entry on oeis.org

0, 0, 0, 0, 47, 91, 143, 285, 539, 1051, 2071, 4179, 8219, 16427, 32791, 65581, 131087, 262183, 524327, 1048659, 2097191, 4194361, 8388651, 16777243, 33554447, 67108935, 134217767, 268435539, 536870935, 1073741907, 2147483663

Offset: 1

Francois R. Grieu (f(AT)grieu.com), Aug 22 2007

nonn

More precisely: minimum value for X=2 of primitive GF(2)[X] polynomials of degree n with exactly 5 terms, or 0 if no such polynomial exists. Applications include maximum-length linear feedback shift registers with efficient implementation in both hardware and software. Proof is needed that there exists a primitive GF(2)[X] polynomial P[X] of degree n and exactly 5 terms for all n>4.

			a(6)=91, or 1011011 in binary, representing the GF(2)[X] polynomial X^6+X^4+X^3+X^1+1, because it has degree 6 and exactly 5 terms and is primitive, contrary to X^6+X^3+X^2+X^1+1 and X^6+X^4+X^2+X^1+1.

Index entries for sequences operating on GF(2)[X]-polynomials

For n>4, a(n) belongs to A091250. A132452(n) = a(n)-2^n, giving a more compact representation. Cf. A132447, similar, with no restriction on number of terms. Cf. A132449, similar, with restriction to a most 5 terms. Cf. A132453, similar, with restriction to minimal number of terms.

A132452 First primitive GF(2)[X] polynomials of degree n with exactly 5 terms, X^n suppressed.

Original entry on oeis.org

15, 27, 15, 29, 27, 27, 23, 83, 27, 43, 23, 45, 15, 39, 39, 83, 39, 57, 43, 27, 15, 71, 39, 83, 23, 83, 15, 197, 83, 281, 387, 387, 83, 99, 147, 57, 15, 153, 89, 101, 27, 449, 51, 657, 113, 29, 75, 75, 71, 329, 71, 149, 45, 99, 149, 53, 39, 105, 51, 27, 27, 833, 39, 163, 101, 43, 43, 1545, 29

Offset: 5

Francois R. Grieu, Aug 22 2007

nonn

More precisely: minimum value for X=2 of GF(2)[X] polynomials P[X] of degree less than n and exactly 4 terms such that X^n+P[X] is primitive.
Applications include maximum-length linear feedback shift registers with efficient implementation in both hardware and software.
Proof is needed that there exists a primitive GF(2)[X] polynomial P[X] of degree n and exactly 5 terms for all n>4.

			a(11)=23, or 10111 in binary, representing the GF(2)[X] polynomial X^4+X^2+X^1+1, because X^11+X^4+X^2+X^1+1 has exactly 5 terms and it is primitive, contrary to X^11+X^3+X^2+X^1+1.

For n>4, 2^n+a(n) belongs to A091250. A132451(n) = a(n)+2^n and gives the corresponding primitive polynomial. Cf. A132448, similar, with no restriction on number of terms. Cf. A132450, similar, with restriction to at most 5 terms. Cf. A132454, similar, with restriction to minimal number of terms.

Edited and extended by Max Alekseyev, Feb 06 2010

cp's OEIS Frontend

User: Francois R. Grieu

A374976 Odd k with p^k mod k != p for all primes p.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A337119 Primes p such that b^(p-1) == 1 (mod p-1) for all b coprime to p-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

A316970 Reducible binary polynomials P of degree n>0 with P dividing the polynomial X^(2^n-1)+1, evaluated at X=2 (pseudo-primes in the ring GF(2)[X]).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A301643 Strong pseudo safe-primes: numbers n = 2m+1 with 2^m == +-1 (mod n) and m a strong pseudoprime A001262.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A300193 Pseudo-safe-primes: numbers n = 2m+1 with 2^m congruent to n+1 or 3n-1 modulo m*n, but m composite.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A132448 First primitive polynomial over GF(2) of degree n, X^n suppressed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A132449 First primitive GF(2)[X] polynomial of degree n with at most 5 terms.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A132450 First primitive GF(2)[X] polynomials of degree n with at most 5 terms, X^n suppressed.

Views

Author

Keywords

Comments

Examples