login
A371811
Semiprimes q*p such that the congruence 2^x == q (mod p) is solvable, where q < p.
3
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
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.
Sequence in context: A064452 A085647 A072901 * A162409 A226494 A242920
KEYWORD
nonn
AUTHOR
STATUS
approved