cp's OEIS Frontend

These are composite numbers n such that b^(n-1) == 1 (mod n) and abs(b^((n-1)/2) mod n) <> 1 for every b coprime to n.

Note that if p is an odd prime, then n^((p+1)/2) == +-n (mod p) for all n.

a(n) is the least Euler weak pseudoprime to base n, as A000790(n) is the least Fermat weak pseudoprime to base n.

This sequence is bounded, namely a(n) <= 1729, the smallest absolute Euler pseudoprime, because n^((1729+1)/2) == n (mod 1729) for every n, see A033181.

The set A = {a(n)} of terms contains all odd semiprimes pq < 1729 such that p-1 | q-1. Other numbers in the set are 561, 645, 1065, 1247, and 1729. Probably complete. Cf. A108574.

This sequence is periodic with a very long period P = LCM(A) = p#*q#/2^2, where p and q are the largest primes such that p^2 < 1729 and 3q < 1729. Such primes are p = 41 and q = 571, so the period P = 41#*571#/4 (248 digits) is much longer than period of the (Fermat) primary pretenders.

Problem: is P the fundamental period of this sequence?

Records of a(n) are 9, 341, 561, 703, 793, 1145, 1263, 1477, and 1729; for n = 0, 2, 383, 1822, 3308, 4702, 10103, 12252, and 21821. - Amiram Eldar, Jul 24 2019

If this sequence is bounded, then it is periodic with period P = LCM(A), where A is the set of all (pairwise distinct) terms.

Note that n^((1729+1)/2) == n (mod 1729) for every n >= 0, where 1729 is the smallest absolute Euler pseudoprime (A033181).

Thus a(n) <= 1729. So, as said, this sequence is periodic.

What is its period?

If the largest term of this sequence is indeed 1729, it should be expected that its period P may be longer than the period of Euler primary pretenders (A309316), namely P > 41#*571#/4 (248 digits).

There are very few composite numbers in this sequence: The probability of catching a pseudoprime number (A001567) with this definition is estimated at 1 in 263 billion.

Composite numbers in the sequence include the Carmichael numbers 131314855918751, 23282264781147191, 70122000249565031, 104782993259720471, 583701149409931151, 870012810301712351. - Robert Israel, Nov 28 2017

With the exception of the pseudoprimes, it seems that this is a subsequence of A139035. Primes of this form (A139035) have two special properties. 1. There exists a smallest m of the form m = (A139035 - 1)/2 such that 2^m == 1 (mod A139035). 2. m is odd. The core of this definition is based on these two properties. The term 2^((k-1)/2) == 1 (mod n) is based on the first property, while the term k == 3 (mod 4) is based on the second property. The terms 3^((k-1)/2) == 1 (mod n) and 5^((k-1)/2) == 1 (mod n) I just tried freely to Fermat.

Prime terms are congruent to 71 or 119 modulo 120. - Jianing Song, Nov 22 2018 [This is because 2, 3, and 5 must be quadratic residues modulo every prime number in this sequence. - Jianing Song, Sep 01 2024]

From Jianing Song, Sep 03 2024: (Start)

Compare this sequence to the sequence of absolute Euler pseudoprimes (A033181): odd composite numbers k such that a^((k-1)/2) == +-1 (mod k) for every a coprime to k. Such numbers k satisfy 2*psi(k) | (k-1), where psi = A002322, so we must have k == 1 (mod 4).

All terms in this sequence are congruent to 7 modulo 8. In fact, taking the Jacobi symbol modulo k (which only depends on the remainder modulo k) of both sides of 2^((k-1)/2) == 1 (mod k) yields (2/k)^((k-1)/2) = 1. Since k == 3 (mod 4), we have that (k-1)/2 is odd, so (2/k) = 1, which means that k == 7 (mod 8). (End)

Those numbers given above by Robert Israel are all congruent to 71 modulo 120. There are no known composite terms congruent to 119 modulo 120; cf. A294092. - Bill McEachen and Jianing Song, Sep 05 2024

As is well known, for an odd prime p, a prime q is a quadratic residue modulo p if and only if q^((p-1)/2) == 1 (mod p). Hence the above definition of these pseudoprimes.

Such pseudoprimes n which are both "residue" and "non-residue", obviously to different bases q(n) and b(n), are particularly interesting: 29341, 49141, 1251949, 1373653, 2284453, ... These five numbers are in A244626.

Note that the absolute Euler pseudoprimes are odd composite numbers n such that b^((n-1)/2) == 1 (mod n) for every base b that is a quadratic residue modulo n and coprime to n. There are no odd composite numbers n such that b^((n-1)/2) == -1 (mod n) for every base b that is a quadratic non-residue modulo n and coprime to n. The absolute Euler-Jacobi pseudoprimes do not exist.

If this sequence is bounded, then it is periodic with period P = LCM(A), where A is the set of all (pairwise distinct) terms.

Note that n^((1729+1)/2) == n (mod 1729) for every n >= 0, where 1729 is the smallest absolute Euler pseudoprime (A033181).

Thus a(n) <= 1729. So, as said, this sequence is periodic.

What is its period?

The period P of this sequence may be longer than the period of Euler primary pretenders (A309316), namely P > 41#*571#/4 (248 digits).

For n > 0, a(n) = n if and only if 2n+1 is prime.

If a(n) < n, then 2n+1 is composite.

Theorem: a(n) > n if and only if 2n+1 is an absolute Euler pseudoprime.

Conjecture: if 2n+1 is an absolute Euler pseudoprime, then a(n) = phi(2n+1).

For n > 0, a(n) = n if and only if 2n+1 is prime.

Note that a(n) < n if and only if 2n+1 is composite.

Conjecture: if 2n+1 is an absolute Euler pseudoprime, then a(n) = 0.

Odd numbers k such that A071294((k-1)/2) = A000010(k)/4.

For each odd composite number m > 9 the number of witnesses <= phi(m)/4. For numbers in this sequence the ratio reaches the maximal possible value 1/4.

The semiprime terms of this sequence are of the form (2*m+1)*(4*m+1) where 2*m+1 and 4*m+1 are primes and m is odd.