A001916 -id:A001916 - cp's OEIS frontend

A001915 Primes p such that the congruence 2^x == 3 (mod p) is solvable.

2, 5, 11, 13, 19, 23, 29, 37, 47, 53, 59, 61, 67, 71, 83, 97, 101, 107, 131, 139, 149, 163, 167, 173, 179, 181, 191, 193, 197, 211, 227, 239, 263, 269, 293, 307, 311, 313, 317, 347, 349, 359, 373, 379, 383, 389, 409, 419, 421, 431, 443, 461, 467, 479, 491, 499, 503, 509, 523

Offset: 1

N. J. A. Sloane

The sequence is known to be infinite [Polya] - thanks to Pieter Moree and Daniel Stefankovic for this comment, Dec 21 2009.

M. Kraitchik, Recherches sur la Théorie des Nombres. Gauthiers-Villars, Paris, Vol. 1, 1924, Vol. 2, 1929, see Vol. 1, p. 63.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Xianwen Wang, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
G. Polya, Arithmetische Eigenschaften der Reihenentwicklungen rationaler Funktionen, J. reine und angewandte Mathematik (Crelle), Volume 1921, Issue 151, Pages 1-31.

Cf. A001916, A050259, A123988.

N:= 1000: # to search the first N primes
{2} union select(t -> numtheory[mlog](3,2,p) <> FAIL, {seq(ithprime(n),n=2..N)});
# Robert Israel, Feb 15 2013

Select[Prime[Range[120]], MemberQ[Table[Mod[2^x-3, #], {x, 0, #}], 0]&] (* Jean-François Alcover, Aug 29 2011 *)
Monitor[aaa=Reap[Do[p=Prime[m];sol=MultiplicativeOrder[2,p,{3}];If[IntegerQ[sol],Sow[p]],{m,1000}]],{m}];tmp=Transpose[{1+Range[Length[aaa[[2,1]]]],aaa[[2,1]]}] (* Xianwen Wang, Jul 22 2025 *)

isok(p) = isprime(p) && sum(k=0, (p-1), Mod(2, p)^k == 3); \\ Michel Marcus, Mar 12 2017

is(n)=isprime(n) && (n==2 || #znlog(3, Mod(2, n))) \\ Charles R Greathouse IV, Aug 15 2018

Better description from Joe K. Crump (joecr(AT)carolina.rr.com), Dec 11 2000

More terms from David W. Wilson, Dec 12 2000

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

Original entry on oeis.org

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

Juri-Stepan Gerasimov, Apr 06 2024

nonn

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

Cf. A001915, A001916.

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

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

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

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

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

cp's OEIS Frontend

A001915 Primes p such that the congruence 2^x == 3 (mod p) is solvable.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Extensions

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

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula