A394571 Positive integers k such that (2*k)^m + 1 is composite for every m >= 1 that is not a power of 2 with value >= 4.

4, 16, 17, 19, 22, 24, 25, 31, 32, 34, 38, 40, 43, 46, 49, 52, 57, 59, 61, 64, 66, 70, 71, 72, 76, 77, 79, 82, 84, 87, 91, 93, 94, 97, 100, 101, 104, 106, 107, 108, 109, 110, 117, 121, 122, 123, 124, 126, 127, 129, 133, 136, 137, 139, 143, 144, 145, 147, 148, 149

Offset

1,1

Comments

Positive integers k such that both 2*k + 1 and 4*k^2 + 1 are composite. Proof: If 2*k + 1 is composite, then for every odd m >= 1, (2*k)^m + 1 is divisible by 2*k + 1 (since for odd t, x^t + 1 is divisible by x + 1). If m is even, write m = 2^r*v with r >= 1 and v odd. Then (2*k)^m + 1 = ((2*k)^(2^r))^v + 1. If v >= 3 (i.e., m not a power of 2), this is composite by the same odd-exponent factorization. If v = 1 (so m = 2^r), then for r = 1 we get (2*k)^2 + 1 = 4*k^2 + 1 (composite by assumption); for r >= 2, we are in the x^2 + 1 case with m >= 4. Thus only powers of 2 with value >= 4 can be exceptions.

If m is a power of 2 with value >= 4, any prime divisor p must satisfy p == 1 (mod 4), since we are in the x^2 + 1 form.

The terms (2*k)^(2^j) + 1 are composite for all j >= 2 if either (a) 2*k is a perfect power with an odd exponent t >= 3, in which case (2*k)^(2^j) + 1 = (b^(2^j))^t + 1 is divisible by b^(2^j) + 1; or (b) 2*k = 2^r with r > 2 and r not a power of 2, so r has an odd factor s >= 3 and (2*k)^(2^j) + 1 = (2^(r/s))^(s*2^j) + 1 is divisible by (2^(r/s))^(2^j) + 1.

For k in this sequence that are not in A391762: For some such k (e.g., 17, 22, 24, ...), a small j >= 2 making (2*k)^(2^j) + 1 prime is easy to find. For others (e.g., 19, 25, 31, ...), finding such a j may be difficult, or no such j may exist.

Links

Felix Huber, Table of n, a(n) for n = 1..10000

Formula

Intersection of A047845 and A094550.

Disjoint from A001912.

Example

4 is a term, since 2*4 + 1 = 9 = 3^2 and 4*4^2 + 1 = 65 = 5*13 are both composite.
17 is a term, since 2*17 + 1 = 35 = 5*7 and 4*17^2 + 1 = 1157 = 13*89 are both composite. Note that (2*17)^4 + 1 = 1336337 is prime; however, m = 4 is a power of 2 with value >= 4, so a prime at that exponent does not disqualify 17.

Maple

A394571 := proc(n)
    option remember;
    local k;
    if n = 1 then return 4; end if;
    for k from A394571(n - 1) + 1 do
        if not isprime(2*k + 1) and not isprime(4*k^2 + 1) then
            return k
        end if;
    end do;
end proc:
seq(A394571(n), n = 1 .. 61);

Crossrefs

Supersequence of A391762.

Cf. A000079, A000215, A001912, A002144, A002522, A008586, A016825, A047845, A070265, A094550, A121944.

Sequence in context: A140299 A119007 A043052 * A037409 A178364 A034121

Adjacent sequences: A394568 A394569 A394570 * A394572 A394573 A394574

Keyword

nonn,easy

Author

Felix Huber, Apr 03 2026

Status

approved