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,1

Links

Table of n, a(n) for n=1..55.

Formula

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

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 *)

Prog

(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

Crossrefs

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

Cf. A001915, A001916.

Sequence in context: A064452 A085647 A072901 * A162409 A226494 A242920

Adjacent sequences: A371808 A371809 A371810 * A371812 A371813 A371814

Keyword

nonn

Author

Juri-Stepan Gerasimov, Apr 06 2024

Status

approved