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

%I #20 May 03 2024 12:13:01

%S 6,10,14,15,22,26,33,34,38,39,46,55,57,58,62,65,69,74,77,82,86,87,91,

%T 94,95,106,111,118,122,133,134,141,142,143,145,146,158,159,166,177,

%U 178,183,185,194,201,202,203,205,206,209,213,214,218,221,226

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

%F Trivial bounds: n log n / log log n << a(n) << n log n. - _Charles R Greathouse IV_, Apr 10 2024

%p filter:= proc(n) local F,p,q,x;

%p F:= ifactors(n)[2];

%p if F[..,2] <> [1,1] then return false fi;

%p p:= max(F[..,1]); q:= min(F[..,1]);

%p [msolve(2^x = q, p)] <> []

%p end proc:

%p select(filter, [$6 .. 1000]); # _Robert Israel_, Apr 10 2024

%t okQ[n_] := Module[{f, p, q, s},

%t f = FactorInteger[n];

%t If[f[[All, 2]] != {1, 1}, False,

%t {q, p} = f[[All, 1]];

%t s = Solve[Mod[2^x, p] == q, x, Integers];

%t s != {}]];

%t Select[Range[6, 1000], okQ] (* _Jean-François Alcover_, May 03 2024 *)

%o (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

%o (Python)

%o from itertools import count, islice

%o from sympy import factorint, discrete_log

%o def A371811_gen(startvalue=1): # generator of terms >= startvalue

%o for n in count(max(startvalue,1)):

%o f = factorint(n)

%o if len(f) == 2 and max(f.values())==1:

%o q, p = sorted(f.keys())

%o try:

%o discrete_log(p,q,2)

%o except:

%o continue

%o yield n

%o A371811_list = list(islice(A371811_gen(),20)) # _Chai Wah Wu_, Apr 10 2024

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

%Y Cf. A001915, A001916.

%K nonn

%O 1,1

%A _Juri-Stepan Gerasimov_, Apr 06 2024