A090866 -id:A090866 - cp's OEIS frontend

A265759 Numerators of primes-only best approximates (POBAs) to 1; see Comments.

3, 2, 5, 13, 11, 19, 17, 31, 29, 43, 41, 61, 59, 73, 71, 103, 101, 109, 107, 139, 137, 151, 149, 181, 179, 193, 191, 199, 197, 229, 227, 241, 239, 271, 269, 283, 281, 313, 311, 349, 347, 421, 419, 433, 431, 463, 461, 523, 521, 571, 569, 601, 599, 619, 617

Offset: 1

Clark Kimberling, Dec 15 2015

Suppose that x > 0. A fraction p/q of primes is a primes-only best approximate (POBA), and we write "p/q in B(x)", if 0 < |x - p/q| < |x - u/v| for all primes u and v such that v < q. Note that for some choices of x, there are values of q for which there are two POBAs. In these cases, the greater is placed first; e.g., B(3) = (7/2, 5/2, 17/5, 13/5, 23/7, 19/7, ...).
See A265772 and A265774 for definitions of lower POBA and upper POBA. In the following guide, for example, A001359/A006512 represents (conjecturally in some cases) the Lower POBAs p(n)/q(n) to 1, where p = A001359 and q = A006512 except for first terms in some cases. Every POBA is either a lower POBA or an upper POBA.
x        Lower POBA       Upper POBA       POBA
1        A001359/A006512  A006512/A001359  A265759/A265760
3/2      A104163/A158708  A162336/A158709  A265761/A222565
2        A005383/A005382  A005385/A005384  A079149/A120628
3        A091180/A088878  A094525/A023208  A265763/A265764
4        A162857/A062737  A090866/A023212  A265765/A120639
5        A265766/A158318  A265767/A023217  A265768/A265769
6        A227756/A158015  A051644/A007693  A265770/A265771
sqrt(2)  A265772/A265773  A265774/A265775  A265776/A265777
sqrt(3)  A265778/A265779  A265780/A265781  A265782/A265783
sqrt(5)  A265784/A265785  A265786/A265787  A265788/A265789
sqrt(8)  A265790/A265791  A265792/A265793  A265794/A265795
tau      A265796/A265797  A265798/A265799  A265800/A265801
1/tau    A265799/A265798  A265797/A265796  A265806/A265807
pi       A265808/A265809  A265810/A265811  A265812/A265813
e        A265814/A265815  A265816/A265817  A265818/A265819

			The POBAs for 1 start with 3/2, 2/3, 5/7, 13/11, 11/13, 19/17, 17/19, 31/29, 29/31, 43/41, 41/43, 61/59, 59/61. For example, if p and q are primes and q > 13, then 11/13 is closer to 1 than p/q is.

Cf. A000040, A001359, A006512, A265759, A265760.

x = 1; z = 200; p[k_] := p[k] = Prime[k];
t = Table[Max[Table[NextPrime[x*p[k], -1]/p[k], {k, 1, n}]], {n, 1, z}];
d = DeleteDuplicates[t]; tL = Select[d, # > 0 &] (* lower POBA *)
t = Table[Min[Table[NextPrime[x*p[k]]/p[k], {k, 1, n}]], {n, 1, z}];
d = DeleteDuplicates[t]; tU = Select[d, # > 0 &] (* upper POBA *)
v = Sort[Union[tL, tU], Abs[#1 - x] > Abs[#2 - x] &];
b = Denominator[v]; s = Select[Range[Length[b]], b[[#]] == Min[Drop[b, # - 1]] &];
y = Table[v[[s[[n]]]], {n, 1, Length[s]}] (* POBA, A265759/A265760 *)
Numerator[tL]   (* A001359 *)
Denominator[tL] (* A006512 *)
Numerator[tU]   (* A006512 *)
Denominator[tU] (* A001359 *)
Numerator[y]    (* A265759 *)
Denominator[y]  (* A265760 *)

A023212 Primes p such that 4*p+1 is also prime.

Original entry on oeis.org

3, 7, 13, 37, 43, 67, 73, 79, 97, 127, 139, 163, 193, 199, 277, 307, 373, 409, 433, 487, 499, 577, 619, 673, 709, 727, 739, 853, 883, 919, 997, 1033, 1039, 1063, 1087, 1093, 1123, 1129, 1297, 1327, 1423, 1429, 1453, 1543, 1549, 1567, 1579, 1597, 1663, 1753

Offset: 1

David W. Wilson

nonn

If p > 3 is a Sophie Germain prime (A005384), p cannot be in this sequence, because all Germain primes greater than 3 are of the form 6k - 1, and then 4p + 1 = 3*(8k-1). - Enrique Pérez Herrero, Aug 15 2011
a(n), except 3, is of the form 6k+1. - Enrique Pérez Herrero, Aug 16 2011
According to Beiler: the integer 2 is a primitive root of all primes of the form 4p + 1 with p prime. - Martin Renner, Nov 06 2011
Chebyshev showed that 2 is a primitive root of all primes of the form 4p + 1 with p prime. - Jonathan Sondow, Feb 04 2013
Also solutions to the equation: floor(4/A000005(4*n^2+n)) = 1. - Enrique Pérez Herrero, Jan 12 2013
Prime numbers p such that p^p - 1 is divisible by 4*p + 1. - Gary Detlefs, May 22 2013
It appears that whenever (p^p - 1)/(4*p + 1) is an integer, then this integer is even (see previous comment). - Alexander R. Povolotsky, May 23 2013
4p + 1 does not divide p^n + 1 for any n. - Robin Garcia, Jun 20 2013
Primes in this sequence of the form 4k+1 are listed in A113601. - Gary Detlefs, May 07 2019
There are no numbers with last digit 1 in this list (i.e., members of A030430) because primes p == 1 (mod 10) lead to 5|(4p+1) such that 4p+1 is not prime. - R. J. Mathar, Aug 13 2019

Albert H. Beiler, Recreations in the theory of numbers, New York: Dover, (2nd ed.) 1966, p. 102, nr. 5.
P. L. Chebyshev, Theory of congruences, Elements of number theory, Chelsea, 1972, p. 306.

Enrique Pérez Herrero, Table of n, a(n) for n = 1..5000
Grigory Ryabov, On schurity of the dihedral group D_(2p), arXiv:2308.14209 [math.GR], 2023.
Rosemary Sullivan and Neil Watling, Independent divisibility pairs on the set of integers from 1 to n, INTEGERS, Vol. 13 (2013), Article A65.
Samuel S. Wagstaff, Jr., Sum of Reciprocals of Germain Primes, Journal of Integer Sequences, Vol. 24, No. 2 (2021), Article 21.9.5.

Cf. A001122, A005384, A043297, A088730.
Cf. A005098, A090866.
Cf. A182265, A182434.

[n: n in [0..1000] | IsPrime(n) and IsPrime(4*n+1)]; // Vincenzo Librandi, Nov 20 2010

isA023212 := proc(n)
    isprime(n) and isprime(4*n+1) ;
end proc:
for n from 1 to 1800 do
    if isA023212(n) then
        printf("%d,",n) ;
    end if;
end do: # R. J. Mathar, May 26 2013

Select[Range[2000], PrimeQ[#] && PrimeQ[4# + 1] &] (* Alonso del Arte, Aug 15 2011 *)
Join[{3}, Select[Range[7, 2000, 6], PrimeQ[#] && PrimeQ[4# + 1] &]] (* Zak Seidov, Jan 21 2012 *)
Select[Prime[Range[300]],PrimeQ[4#+1]&] (* Harvey P. Dale, Oct 17 2021 *)

forprime(p=2,1800,if(Mod(p,4*p+1)^p==1, print1(p", \n"))) \\ Alexander R. Povolotsky, May 23 2013

Sum_{n>=1} 1/a(n) is in the interval (0.892962433, 1.1616905) (Wagstaff, 2021). - Amiram Eldar, Nov 04 2021

Name edited by Michel Marcus, Nov 27 2020

A074781 Primes of the form p*2^k + 1 for any k and any prime p.

Original entry on oeis.org

3, 5, 7, 11, 13, 17, 23, 29, 41, 47, 53, 59, 83, 89, 97, 107, 113, 137, 149, 167, 173, 179, 193, 227, 233, 257, 263, 269, 293, 317, 347, 353, 359, 383, 389, 449, 467, 479, 503, 509, 557, 563, 569, 587, 593, 641, 653, 719, 769, 773, 797, 809, 839, 857, 863, 887

Offset: 1

Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Sep 07 2002

nonn

From Bernard Schott, Dec 14 2020: (Start)
Equivalently, primes p such that the ratio (p-1)/gpf(p-1) = 2^k where gpf(m) is the greatest prime factor of m, A006530.
Paul Erdős asked if there are infinitely many primes p in this sequence (see R. K. Guy reference). (End)

			3 = 2*2^0+1 is a term and 2/2 = 1 = 2^0.
7 = 3*2^1+1 is a term and 6/3 = 2 = 2^1.
13 = 3*2^2+1 is a term and 12/3 = 4 = 2^2.
41 = 5*2^3+1 is a term and 40/5 = 8 = 2^3.
113 = 7*2^4+1 is a term and 112/7 = 16 = 2^4.

Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section B46, p. 154.

T. D. Noe, Table of n, a(n) for n = 1..2000
Graeme L. Cohen, On a conjecture of Makowski and Schinzel, Colloquium Mathematicae, Vol. 74, No. 1 (1997), pp. 1-8.

Cf. A000079, A006093, A006530, A052126, A339464.
Cf. other ratios : A339463, A339465, A339466.
Subsequences: A039687, A051900, A058500 (this sequence without the Fermat primes), A090866, A147545,

alias(pf = NumberTheory:-PrimeFactors): gpf := n -> max(pf(n)):
is_a := n -> isprime(n) and pf((n-1)/gpf(n-1)) = {2}:
3, op(select(is_a, [$3..919])); # Peter Luschny, Dec 14 2020

Select[Range[3, 1000], PrimeQ[#] && !CompositeQ[(# - 1)/2^IntegerExponent[(# - 1), 2]] &] (* Amiram Eldar, Dec 28 2018 *)

A098006 (p-1)/2 - phi(p-1) as p runs through the odd primes.

Original entry on oeis.org

0, 0, 1, 1, 2, 0, 3, 1, 2, 7, 6, 4, 9, 1, 2, 1, 14, 13, 11, 12, 15, 1, 4, 16, 10, 19, 1, 18, 8, 27, 17, 4, 25, 2, 35, 30, 27, 1, 2, 1, 42, 23, 32, 14, 39, 57, 39, 1, 42, 4, 23, 56, 25, 0, 1, 2, 63, 50, 44, 49, 2, 57, 35, 60, 2, 85, 72, 1, 62, 16, 1, 63, 66, 81, 1, 2, 78, 40, 76, 29, 114, 47

Offset: 2

N. J. A. Sloane, Sep 08 2004

In the Luca-Walsh paper it is shown that there are infinitely many numbers not in this sequence. See A098047.

a(n)=0 for Fermat primes (A019434). a(n)=1 for safe primes (A005385). a(n)=2 for A090866. The least prime p for which (p-1)/2-phi(p-1)=n or 0 if there is no such prime is given by A134765(n). Sequence A134854(k) gives the least prime for which a(n)=2^(k-1). For k not a power of 2, it can be shown that if k is in this sequence, then it appears for a prime p <= 1+k^2. - T. D. Noe, Nov 13 2007

J. Browkin and A. Schinzel, On integers not of the form n-phi(n), Colloq. Math., 68 (1995), 55-58.
F. Luca and P. G. Walsh, On the number of nonquadratic residues which are not primitive roots, Colloq. Math., 100 (2004), 91-93.

T. D. Noe, Table of n, a(n) for n = 2..10000
T. D. Noe, Finding primes p for which (p-1)/2 - phi(p-1) = k

Cf. A000010, A051953, A098047, A176095 (p runs through the odd numbers).

a098006 n = a005097 (n-1) - a000010 (a006093 n)
-- Reinhard Zumkeller, Mar 26 2013

[(NthPrime(n)-1)/2 - EulerPhi(NthPrime(n)-1): n in [2..100]]; // Vincenzo Librandi, Jan 10 2017

A098006 := proc(n)
    local p;
    p := ithprime(n+1) ;
    (p-1)/2-numtheory[phi](p-1) ;
end proc:
seq(A098006(n),n=1..30) ; # R. J. Mathar, Jan 09 2017

Table[(Prime[n] - 1)/2 - EulerPhi[Prime[n] - 1], {n, 2, 85}] (* Robert G. Wilson v, Sep 09 2004 *)
Table[(n-1)/2-EulerPhi[n-1],{n,Prime[Range[2,100]]}] (* Harvey P. Dale, Oct 23 2016 *)

forprime(p=3,1e3,print1(p\2-eulerphi(p-1)", ")) \\ Charles R Greathouse IV, Feb 04 2013

a(n) = A005097(n-1) - A000010(A006093(n)); a(A159611(n)) = 0. - Reinhard Zumkeller, Mar 26 2013

A063640 Primes of form pqr + 1, where p, q and r are primes.

Original entry on oeis.org

13, 19, 29, 31, 43, 53, 67, 71, 79, 103, 131, 139, 149, 173, 191, 223, 239, 269, 283, 293, 311, 317, 367, 389, 419, 431, 439, 443, 499, 509, 557, 599, 607, 619, 643, 647, 653, 659, 683, 743, 773, 787, 797, 823, 827, 907, 947, 971, 1031, 1039, 1087, 1091

Offset: 1

Reinhard Zumkeller, Jul 21 2001

nonn

Odd primes p such that (p-1)/2 is a semiprime. - Robert G. Wilson v, Sep 01 2007

Harry J. Smith, Table of n, a(n) for n = 1..1000

A090866 is a subsequence.

Cf. A014612, A063639.

q:= n-> isprime(n) and numtheory[bigomega](n-1)=3:
select(q, [$2..1100])[];  # Alois P. Heinz, Mar 08 2023

Take[ Select[ Union@ Flatten@ Table[ Prime@p*Prime@q*Prime@r + 1, {p, 48}, {q, p}, {r, q}], PrimeQ@ # &], 53] (* Or *)
semiPrimeQ[x_] := Plus @@ Last /@ FactorInteger[x] == 2; Select[Prime@ Range@ 182, semiPrimeQ[(# - 1)/2] &] (* Robert G. Wilson v, Sep 01 2007 *)
2#+1&/@Select[Table[(n-1)/2,{n,Prime[Range[200]]}],PrimeOmega[#]==2&] (* Harvey P. Dale, Oct 11 2018 *)

n=0; for (m=1, 10^9, p=prime(m); if (bigomega(p - 1) == 3, write("b063640.txt", n++, " ", p); if (n==1000, break)) )  \\ Harry J. Smith, Aug 26 2009

A222008 Primes of the form 4^k + 1 for some k > 0.

Original entry on oeis.org

5, 17, 257, 65537

Offset: 1

Jonathan Sondow, Feb 04 2013

nonn

Same as Fermat primes 2^(2^m) + 1 for m >= 1. See A019434 for comments, etc.
Chebyshev showed that 3 is a primitive root of all primes of the form 2^(2*k) + 1 with k > 0. If the sequence is infinite, then Artin's conjecture ("every nonsquare integer n != -1 is a primitive root of infinitely many primes q") is true for n = 3.
As a(n) is a Fermat prime > 3, by Pépin's test a(n) has primitive root 3.
Conjecture: let p a prime number, a(n) is not congruent to p mod (p^2-3)/2. - Vincenzo Librandi, Jun 15 2014
This conjecture is false when p = a(n), but may be true for primes p != a(n). - Jonathan Sondow, Jun 15 2014
Primes p with the property that k-th smallest divisor of its squares p^2, for all 1 <= k <= tau(p^2), contains exactly k "1" digits in its binary representation. Corresponding values of squares p^2: 25, 289, 66049, 4295098369. Example: p = 257, set of divisors of p^2 = 66049 in binary representation: {1, 100000001, 10000001000000001}. Subsequence of A255401. - Jaroslav Krizek, Dec 21 2016

			4^1 + 1 = 5 is prime, so a(1) = 5. Also, 3^k == 3, 4, 2, 1 (mod 5) for k = 1, 2, 3, 4, resp., so 3 is a primitive root for a(1).

Albert H. Beiler, Recreations in the theory of numbers, New York, Dover, (2nd ed.) 1966, p. 102, nr. 3.
P. L. Chebyshev, Theory of congruences. Elements of number theory, Chelsea, 1972, p. 306.

P. L. Chebyshev, Theorie der Congruenzen, Mayer & Mueller, 1889, p. 306-313.
R. Fueter, Über primitive Wurzeln von Primzahlen, Comment. Math. Helv., 18 (1946), 217-223, p. 217.
Wikipedia, Pépin's test
Index entries for sequences related to Artin's conjecture
Index entries for primes by primitive root

Cf. A005596, A019334, A019434, A090866, A221981.

Select[Table[4^k + 1, {k, 10^3}], PrimeQ] (* Michael De Vlieger, Dec 22 2016 *)

a(n) = A019434(n+1) for n > 0.

A116518 Odd numbers k such that k and phi(k) have the same number of divisors.

Original entry on oeis.org

1, 3, 15, 255, 65535, 77805, 161595, 331695, 575025, 664335, 765765, 1601145, 2250885, 2380833, 2690415, 3271905, 3828825, 4107285, 5181813, 5778045, 5871285, 6007365, 6613425, 7448805, 9258795, 9787869, 9935055, 10503675, 10554705, 10724805, 11060595

Offset: 1

Max Alekseyev, Mar 24 2006

nonn

From Farideh Firoozbakht, Aug 28 2006: (Start)
For n < 6, the product of the first n Fermat primes is in the sequence because if m = 2^(2^n)-1 and n < 6 then d(m) = d(phi(m)) = 2^n.
(1). If p is a Sophie Germain prime greater than 3 then m = 69615*(2p+1) (A005385) is in the sequence because d(m) = d(phi(m)) = 96. 765765, 1601145, 3271905, 4107285, 5778045, 7448805, ... is the related subsequence.
(2). If p is a prime greater than 3 such that 4p+1 is prime then m = 700245*(4p+1) (A090866) is in the sequence because d(m) = d(phi(m)) = 160. 20307105, 37112985, 104336505, 121142385, ... is the related subsequence. (End)
It is an open question whether this sequence contains infinitely many terms; see Bellaouar et al., 2023. - Allen Stenger, Feb 16 2024

Donovan Johnson, Table of n, a(n) for n = 1..1000
Djamel Bellaouar, Abdelmadjid Boudaoud and Rafael Jakimczuk, Notes on the equation d(n) = d(phi(n)) and related inequalities, Math. Slovaca 73 (2023), no. 3, 613-632.

Subsequence of A070418. Cf. A005384.

Cf. A062821, A099774.

Select[Range[1,10510001,2],DivisorSigma[0,#]==DivisorSigma[ 0, EulerPhi[#]]&] (* Harvey P. Dale, Jan 30 2013 *)

forstep(n=1,10^8,2,if(numdiv(n)==numdiv(eulerphi(n)),print1(n,", ")))

A090865 Primes p such that (p-1)/2 is prime if p == 3 (mod 4) or (p-1)/4 is prime if p == 1 (mod 4).

Original entry on oeis.org

7, 11, 13, 23, 29, 47, 53, 59, 83, 107, 149, 167, 173, 179, 227, 263, 269, 293, 317, 347, 359, 383, 389, 467, 479, 503, 509, 557, 563, 587, 653, 719, 773, 797, 839, 863, 887, 983, 1019, 1109, 1187, 1229, 1283, 1307, 1319, 1367, 1439, 1487, 1493, 1523, 1619

Offset: 1

Benoit Cloitre, Feb 12 2004

nonn

G. C. Greubel, Table of n, a(n) for n = 1..10000

Subsequence of A058500.

Union of (A005385 \ {5}) and A090866.

Select[Prime[Range[256]], PrimeQ[(#-1)/(5-Mod[#, 4])]& ] (* Jean-François Alcover, Jul 16 2012 *)

forprime(p=1, 1619, if (((p%4==3) && isprime((p-1)/2)==1) || ((p%4==1) && isprime((p-1)/4)), print1(p, ", "))) \\ Jinyuan Wang, Feb 09 2019

A126330 Primes of the form 4p+3 where p is a prime.

Original entry on oeis.org

11, 23, 31, 47, 71, 79, 127, 151, 167, 191, 239, 271, 359, 431, 439, 599, 607, 631, 719, 727, 911, 919, 967, 1031, 1087, 1231, 1327, 1399, 1439, 1471, 1559, 1607, 1759, 1831, 1847, 1871, 1951, 1999, 2039, 2087, 2287, 2311, 2351, 2399, 2591, 2647, 2711, 2767

Offset: 1

J. M. Bergot, Mar 09 2007

nonn

Robert Israel, Table of n, a(n) for n = 1..10000

For the primes p see A023213.

Cf. A002145, A004767, A080148, A090866, A095278.

select(p -> isprime(p) and isprime((p-3)/4), [seq(p,p=7..10000,4)]); # Robert Israel, Aug 08 2019

Select[3 + 4Prime@Range[130], PrimeQ] (* Ray Chandler, Jun 29 2008 *)

Checked and extended by N. J. A. Sloane, Mar 10 2007

A158014 Primes p such that (p-1)/8 is also prime.

Original entry on oeis.org

17, 41, 89, 137, 233, 569, 809, 857, 1049, 1097, 1193, 1433, 1913, 2153, 2777, 3209, 3449, 3593, 3833, 3929, 4073, 4457, 4793, 4937, 5273, 5417, 6089, 6473, 6569, 6857, 7433, 7529, 7577, 7817, 9209, 9497, 9833

Offset: 1

Roger L. Bagula, Mar 11 2009

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Cf. A005385 for (p-1)/2, A090866 for (p-1)/4, A051644 for (p-1)/6, A055781 for (p-1)/10.

Flatten[Table[If[PrimeQ[n] && PrimeQ[(n - 1)/8], n, {}], {n, 1, 10000}]]
Select[Prime[Range[1500]], PrimeQ[(# - 1) / 8]&] (* Vincenzo Librandi, Apr 14 2013 *)

list(lim)=my(v=List()); forprime(p=2,(lim-1)\8, if(isprime(8*p+1), listput(v,8*p+1))); Vec(v) \\ Charles R Greathouse IV, Oct 20 2021

a(n)=8*A023228(n)+1. - R. J. Mathar, Mar 15 2009

a(n) >> n log^2 n. - Charles R Greathouse IV, Oct 21 2021

Edited by the Associate Editors of the OEIS, Apr 22 2009

cp's OEIS Frontend

A265759 Numerators of primes-only best approximates (POBAs) to 1; see Comments.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A023212 Primes p such that 4*p+1 is also prime.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A074781 Primes of the form p*2^k + 1 for any k and any prime p.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

A098006 (p-1)/2 - phi(p-1) as p runs through the odd primes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Formula

A063640 Primes of form p*q*r + 1, where p, q and r are primes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A222008 Primes of the form 4^k + 1 for some k > 0.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A116518 Odd numbers k such that k and phi(k) have the same number of divisors.

Views

Author

Keywords

Comments

A063640 Primes of form pqr + 1, where p, q and r are primes.