A391762 - OEIS

%I #110 Apr 09 2026 19:06:50

%S 4,16,32,64,108,256,500,512,864,1024,1372,2048,2916,3888,4000,4096,

%T 5324,6912,8192,8788,10976,13500,16384,19652,27436,32000,37044,42592,

%U 48668,50000,55296,62500,65536,70304,78732,87808,97556,108000,119164,124416,131072,139968,143748,157216,171500,186624

%N Positive integers k such that both 2*k + 1 and 4*k^2 + 1 are composite, and either 2*k is a perfect power with odd exponent >= 3 or 2*k = 2^r with r > 2 and r not a power of 2.

%C All terms k in this sequence satisfy that (2*k)^m + 1 is composite for every m >= 1. Proof: (Start)

%C Let b = 2*k. Assume (i) 2*k + 1 and 4*k^2 + 1 are composite, and (ii) either b is a perfect power with odd exponent t >= 3, or b = 2^r with r > 2 and r not a power of 2 (so r has an odd factor s >= 3, hence b = (2^(r/s))^s).

%C Odd m: b^m + 1 is divisible by b + 1, which is composite by (i).

%C Even m: write m = 2^u*v with u >= 1 and v odd. If v >= 3 (so m is not a power of 2), then b^m + 1 = (b^(2^u))^v + 1 is divisible by b^(2^u) + 1. If v = 1 (so m = 2^u), then for u = 1 we have b^2 + 1 = 4*k^2 + 1 composite by (i); for u >= 2, by (ii) we can write b = c^t with odd t >= 3, hence b^(2^u) + 1 = (c^(2^u))^t + 1 is divisible by c^(2^u) + 1.

%C Therefore (2*k)^m + 1 is composite for all m >= 1. (End)

%C For k in A394571 that are not in this sequence: 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.

%e 4 is a term since 2*4 + 1 = 9 = 3^2 and 4*4^2 + 1 = 65 = 5*13 are both composite, and b = 2*4 = 8 = 2^3 is a power of 2 with r = 3 > 2, and 3 is not a power of 2.

%e 108 is a term since 2*108 + 1 = 217 = 7*31 and 4*108^2 + 1 = 46657 = 13*37*97 are both composite, and b = 2*108 = 216 = 6^3 is a perfect power with odd exponent 3.

%p A391762 := proc(n)

%p     option remember;

%p     local k, p, r, b;

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

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

%p         b := 2*k;

%p         if not isprime(b + 1) and not isprime(b^2 + 1) then

%p             if iperfpow(b, 'p') <> FAIL and type(p, integer) and p >= 3 and type(p, odd) then

%p                 return k

%p             else

%p                 r := ilog2(b);

%p                 if 2^r = b and r > 2 and not is(r, 2^integer) then

%p                     return k

%p                 end if

%p             end if

%p         end if

%p     end do;

%p end proc:

%p seq(A391762(n), n = 1 .. 56);

%Y Subsequence of A394571.

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

%K nonn

%O 1,1

%A _Felix Huber_, Apr 03 2026