cp's OEIS Frontend

The multiplicative order of -5 modulo a(n) is A385231(n).

Contained in primes congruent to 1, 3, 7, 9 modulo 20 (primes p such that -5 is a quadratic residue modulo p, A139513), and contains primes congruent to 3, 7 modulo 20 (A122870).

Conjecture: this sequence has density 1/3 among the primes.

From Charles R Greathouse IV, Feb 13 2009: (Start)

Essentially the same as A014662.

Also primes p for which p^2 divides 2^n+1 for some n. If p | 2^g + 1, then 2^g = kp - 1 for some k, so 2^gp = (kp - 1)^p = (-1)^p + (-1)^(p-1) * kp * (p choose 1) + ... and so 2^gp = -1 (mod p^2). (End)

Is there an odd term besides 1? Numbers 2^a(i)-1 form set difference of sequences A103289 and A096399.

Odd terms > 1 exist, but there are none < 10^7. If k > 1 is an odd term, then 2^k-1 must have more than 900000 distinct prime factors and all of them must be members of A014663. - David Wasserman, Apr 15 2008

Since all primes after the first are odd, a(n) > 1 for n > 1.

a(n) = 2 if and only if A014664(n) is even, or equivalently prime(n) is not in A014663. - Robert Israel, Dec 08 2016

If prime(n) = A000668(k), then a(n) = A000043(k). - Robert Israel, Dec 20 2016

Numbers k that 2^k - 1 is in A023196.

Are there any odd terms? This is a subsequence of A103291. Is the number 1 the only term where they differ? This is so if there is no least deficient number of the form 2^n-1 besides 1.

For each n in the sequence, 2n is also in the sequence: sigma[2^(2n)-1] = sigma[(2^n+1)(2^n-1)] >= (2^n+1)*sigma(2^n-1) because for each divisor d|2^n-1 there is (at least) the divisor (2^n+1)d |[(2^n+1)(2^n-1)]. Inserting sigma(2^n-1) >=2(2^n-1) yields (2^n+1)*sigma(2^n-1)>=(2^n+1)*2*(2^n-1)=2*[2^(2n)-1] qed. - R. J. Mathar, Aug 07 2007

From David Wasserman, May 16 2008: (Start)

Odd members exist. One such n is the lcm of the first 4416726 members of A139686, which has 6864499 digits. To show that n is a member, it's not necessary to exactly compute sigma(2^n-1).

The function f(x) = sigma(x)/x is multiplicative and has the property that for any a, b > 1, f(ab) > f(a). So it suffices to find some y such that f(y) >= 2 and y divides 2^n-1. In this case, y is the product of the first 4416726 members of A014663 and has 35260810 digits. (A014663(4416726) = 278379727.)

To see that this works, note that if a divides b, then 2^a-1 divides 2^b-1. For 1 <= i <= 4416726, A014663(i) divides 2^A139686(i)-1 by definition and A139686(i) divides n, so 2^A139686(i)-1 divides 2^n-1 and therefore A014663(i) divides 2^n-1. Then we can compute that f(y) = Product_{i = 1..4416726} (1 + 1/A014663(i)) is > 2.

The members of A014663 are the only primes that can divide 2^n-1 with n odd. Any powers of these primes are also possible divisors.

By including powers, we can construct a much smaller y. I found a y with 7057382 digits, omega(y) = 969004 and bigomega(y) = 969440. This y is close to the minimum possible. The least n such that y divides 2^n-1 is an odd number with 1472897 digits.

However, minimizing y is not the way to minimize n. We can get a smaller n by skipping primes p such that the order of 2 mod p is divisible by a large prime. This increases the number and size of the prime factors needed to make f(y) >= 2 and the time needed to find them.

The least odd n that I've found has 28375 digits. The corresponding y has 305621222 digits, omega(y) = 31903142 and bigomega(y) = 32796897. To find these prime factors, I searched up to A014663(96433108) = 7154804519.

I believe that the smallest odd member has between 10000 and 20000 digits, but the largest lower bound I can prove has 8 digits: f(p^i) is bounded above by 1 + 1/(p-1) and Product_{i=1..c} (1 + 1/(A014663(i)-1)) < 2 if c < 968858, so y must be at least Product_{i=1..968858} A014663(i), which has 7054790 digits.

Then n must be large enough that 2^n-1 >= y, yielding a lower bound of 23435503. I don't see any way to increase this significantly. (End)

The corresponding sequence for primes is A014663.

These pseudoprimes seem to be relatively rare: among the 118968378 base-2 Fermat pseudoprimes below 2^64 only 6292535 are terms of this sequence.

These pseudoprimes appear in a theorem by Rotkiewicz and Makowski (1966) about pseudoprimes that are products of two Mersenne numbers (see A367229).

Without the restriction to Mersenne numbers that are larger than 1 all the composite Mersenne numbers (A065341) will be terms.

Szymiczek (1964) proved that if p is a prime == 7 (mod 8) (A007522) and t = 2^phi((p-1)/2), then M(p)*M(t) is a Fermat pseudoprime to base 2, where phi is the Euler totient function (A000010) and M(n) = 2^n-1 = A000225(n) is the n-th Mersenne number. The smallest pseudoprime that is generated by this rule, for p = 7 and t = 2^phi((7-1)/2) = 4, is M(7) * M(4) = 1905. The next two, corresponding to p = 23 and 31, have 316 and 87 digits, respectively.

Rotkiewicz and Makowski (1966) proved that if p is a prime or a Fermat pseudoprime to base 2 such that o(p), the multiplicative order of 2 modulo p, is odd (A014663 for primes, A367230 for pseudoprimes), then for each positive k <= p/o(o(p)), if t = 2^(k*o(o(p))) then M(p)*M(t) is a Fermat pseudoprime to base 2. For example, for p = 7, p/o(o(7)) = 7/2, so for k = 1, 2 and 3 the resulting pseudoprimes are 1905, 8322945 and 2342736497361113055105, respectively.