A394571 - OEIS

%I #7 Apr 09 2026 17:49:32

%S 4,16,17,19,22,24,25,31,32,34,38,40,43,46,49,52,57,59,61,64,66,70,71,

%T 72,76,77,79,82,84,87,91,93,94,97,100,101,104,106,107,108,109,110,117,

%U 121,122,123,124,126,127,129,133,136,137,139,143,144,145,147,148,149

%N 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.

%C 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.

%C 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.

%C 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.

%C 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.

%H Felix Huber, <a href="/A394571/b394571.txt">Table of n, a(n) for n = 1..10000</a>

%F Intersection of A047845 and A094550.

%F Disjoint from A001912.

%e 4 is a term, since 2*4 + 1 = 9 = 3^2 and 4*4^2 + 1 = 65 = 5*13 are both composite.

%e 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.

%p A394571 := proc(n)

%p     option remember;

%p     local k;

%p     if n = 1 then return 4; end if;

%p     for k from A394571(n - 1) + 1 do

%p         if not isprime(2*k + 1) and not isprime(4*k^2 + 1) then

%p             return k

%p         end if;

%p     end do;

%p end proc:

%p seq(A394571(n), n = 1 .. 61);

%Y Supersequence of A391762.

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

%K nonn,easy

%O 1,1

%A _Felix Huber_, Apr 03 2026