A371811 Semiprimes q*p such that the congruence 2^x == q (mod p) is solvable, where q < p.

6, 10, 14, 15, 22, 26, 33, 34, 38, 39, 46, 55, 57, 58, 62, 65, 69, 74, 77, 82, 86, 87, 91, 94, 95, 106, 111, 118, 122, 133, 134, 141, 142, 143, 145, 146, 158, 159, 166, 177, 178, 183, 185, 194, 201, 202, 203, 205, 206, 209, 213, 214, 218, 221, 226

Offset: 1

Author

Juri-Stepan Gerasimov, Apr 06 2024

Keywords

• nonn

Crossrefs

Subsequence of A006881. Apart from the first term, A100484 is a subsequence.

Cf. A001915, A001916.

Programs

Maple

filter:= proc(n) local F,p,q,x;
  F:= ifactors(n)[2];
  if F[..,2] <> [1,1] then return false fi;
  p:= max(F[..,1]); q:= min(F[..,1]);
  [msolve(2^x = q, p)] <> []
end proc:
select(filter, [$6 .. 1000]); # Robert Israel, Apr 10 2024

Mathematica

okQ[n_] := Module[{f, p, q, s},
   f = FactorInteger[n];
   If[f[[All, 2]] != {1, 1}, False,
   {q, p} = f[[All, 1]];
   s = Solve[Mod[2^x, p] == q, x, Integers];
   s != {}]];
Select[Range[6, 1000], okQ] (* Jean-François Alcover, May 03 2024 *)

PARI

list(lim)=my(v=List()); forprime(p=3,lim\2, forprime(q=2,min(p-1,lim\p), if(znlog(q, Mod(2, p)) != [], listput(v,p*q)))); Set(v) \\ Charles R Greathouse IV, Apr 10 2024

Python

from itertools import count, islice
from sympy import factorint, discrete_log
def A371811_gen(startvalue=1): # generator of terms >= startvalue
    for n in count(max(startvalue,1)):
        f = factorint(n)
        if len(f) == 2 and max(f.values())==1:
            q, p = sorted(f.keys())
            try:
                discrete_log(p,q,2)
            except:
                continue
            yield n
A371811_list = list(islice(A371811_gen(),20)) # Chai Wah Wu, Apr 10 2024

Formula

Trivial bounds: n log n / log log n << a(n) << n log n. - Charles R Greathouse IV, Apr 10 2024