A065966 -id:A065966 - cp's OEIS frontend

A065976 Consecutive terms of A065966 which are also consecutive integers.

7, 8, 9, 10, 11, 22, 46, 166, 358, 718, 1438, 2038, 2878, 4078, 4126, 4918, 5638, 5806, 5926, 6046, 7246, 7558, 7606, 7726, 9838, 10798, 11278, 13798, 13966, 14158, 15286, 15646, 20326, 21598, 21766, 23398, 24406, 24526, 25798, 28318, 28606

Offset: 1

Jason Earls, Dec 09 2001

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

A065966(n) = A065966(n+1).

{ n=p=0; for (m=3, 10^9, if (isprime(eulerphi(m)/2), if (m==p + 1, write("b065976.txt", n++, " ", p); if (n==1000, return)); p=m) ) } \\ Harry J. Smith, Nov 05 2009

A068213 Duplicate of A065966.

Original entry on oeis.org

5, 7, 8, 9, 10, 11, 12, 14, 18, 22, 23, 46, 47, 59, 83, 94, 107, 118, 166, 167, 179, 214

Offset: 1

dead

A035095 Smallest prime congruent to 1 (mod prime(n)).

Original entry on oeis.org

3, 7, 11, 29, 23, 53, 103, 191, 47, 59, 311, 149, 83, 173, 283, 107, 709, 367, 269, 569, 293, 317, 167, 179, 389, 607, 619, 643, 1091, 227, 509, 263, 823, 557, 1193, 907, 1571, 653, 2339, 347, 359, 1087, 383, 773, 3547, 797, 2111, 2677, 5449, 2749, 467

Offset: 1

Labos Elemer

nonn

This is a version of the "least prime in special arithmetic progressions" problem.
Smallest numbers m such that largest prime factor of Phi(m) = prime(n), the n-th prime, also seems to be prime and identical to n-th term of A035095. See A068211, A068212, A065966: Min[x : A068211(x)=prime(n)] = A035095(n); e.g., Phi(a(7)) = Phi(103) = 2*3*17, of which 17 = p(7) is the largest prime factor, arising first here.
It appears that A035095, A066674, A125878 are probably all the same, but see the comments in A066674. - N. J. A. Sloane, Jan 05 2013
Minimum of the smallest prime factors of F(n,i) = (i^prime(n)-1)/(i-1), when i runs through all integers in [2, prime(n)]. Every prime factor of F(n,i) is congruent to 1 modulo prime(n). - Vladimir Shevelev, Nov 26 2014
Conjecture: a(n) is the smallest prime p such that gpf(p-1) = prime(n). See A023503. - Thomas Ordowski, Aug 06 2017
For n>1, a(n) is the smallest prime congruent to 1 mod (2*prime(n)). - Chai Wah Wu, Apr 28 2025

			a(8) = 191 because in the prime(8)k+1 = 19k+1 sequence, 191 is the smallest prime.

E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Bd 1 (reprinted Chelsea 1953).
E. C. Titchmarsh, A divisor problem, Renc. Circ. Math. Palermo, 54 (1930) pp. 414-429.
P. Turan, Über Primzahlen der arithmetischen Progression, Acta Sci. Math. (Szeged), 8 (1936/37) pp. 226-235.

T. D. Noe, Table of n, a(n) for n = 1..10000
P. Erdős, On some application of Brun's method, Acta Sci. Math (Szeged), v. 13, 1949, pp. 57-63.
A. Granville and C. Pomerance, On the least prime in certain arithmetic progressions
A. Granville and C. Pomerance, On the least prime in certain arithmetic progressions J. Lond Math Soc s2-41 (2) (1990), pp. 193-200.
D. R. Heath-Brown, almost-primes in arithmetic progressions in short intervals, Math Proc Cambr. Phil Soc v 83 (1978), pp. 357-375.
D. R. Heath-Brown, Siegel zeros and the least prime in arithmetic progression, Quart. J. of Math 41 (49) (1990), pp. 405-418.
H.-J. Kanold, Uber Primzahlen in arithmetischen Folgen, Math. Ann. v 156 (1964) pp. 393-395.
U. V. Linnik, On the least prime in an arithmetic progression. I. The basic theorem, Rec. Math (N.S.) v 15 (57) (1944), pp 139-178. MR0012111
C. Pomerance, A note on the least prime in an arithmetic progression J. Number Theory 12 (2) (1980), pp. 218-223.
K. Prachar, Uber die kleinste Primzahl in einer arithmetischen Reihe, J Reine Angew Math. 206 (1961) pp. 3-4.
A. Schinzel, Remark on the paper of K. Prachar Uber die kleinste.., J. Reine Angew Math. v 210 (1962) pp. 122-122.
S. S. Wagstaff, Jr., The irregular primes to 125000, Math. Comp., 32 (1978) pp. 583-591.
S. S. Wagstaff, Jr, Greatest of the Least Primes in Arithmetic Progressions Having a Given Modulus, Math. Comp., 33 (147) (1979) pp. 1073-1080.
Index entries for sequences related to primes in arithmetic progressions

Cf. A034694, A032448, A006530, A006093, A035096, A000040, A019434, A058383.
Cf. A068211, A068212, A065966, A000010, A070844-A070858, A061092.
Cf. A000040.

a[n_] := Block[{p = Prime[n]}, r = 1 + p; While[ !PrimeQ[r], r += p]; r]; Array[a, 51] (* Jean-François Alcover, Sep 20 2011, after PARI *)
a[n_]:=If[n<2,3,Block[{p=Prime[n]},r=1+2*p;While[!PrimeQ[r],r+=2*p]];r];Array[a,51] (* Zak Seidov, Dec 14 2013 *)

a(n)=local(p,r);p=prime(n);r=1;while(!isprime(r),r+=p);r

{my(N=66); forprime(p=2, , forprime(q=p+1,10^10, if((q-1)%p==0, print1(q,", "); N-=1; break)); if(N==0,break)); } \\ Joerg Arndt, May 27 2016

from itertools import count
from sympy import prime, isprime
def A035095(n): return 3 if n==1 else next(filter(isprime,count((p:=prime(n)<<1)+1,p))) # Chai Wah Wu, Apr 28 2025

According to a long-standing conjecture (see the 1979 Wagstaff reference), a(n) <= prime(n)^2 + 1. This would be sufficient to imply that a(n) is the smallest prime such that greatest prime divisor of a(n)-1 is prime(n), the n-th prime: A006530(a(n)-1) = A000040(n). This in turn would be sufficient to imply that no value occurs twice in this sequence. - Franklin T. Adams-Watters, Jun 18 2010

a(n) = 1 + A035096(n)*A000040(n). - Zak Seidov, Dec 27 2013

Edited by Franklin T. Adams-Watters, Jun 18 2010
Minor edits by N. J. A. Sloane, Jun 27 2010
Edited by N. J. A. Sloane, Jan 05 2013

A066179 Primes p such that (p-1)/2 and (p-3)/4 are also prime.

Original entry on oeis.org

11, 23, 47, 167, 359, 719, 1439, 2039, 2879, 4079, 4127, 4919, 5639, 5807, 5927, 6047, 7247, 7559, 7607, 7727, 9839, 10799, 11279, 13799, 13967, 14159, 15287, 15647, 20327, 21599, 21767, 23399, 24407, 24527, 25799, 28319, 28607, 29399

Offset: 1

Vladeta Jovovic, Dec 14 2001

nonn

Call p "m-prime" iff (p-(2^i-1))/2^i is prime for i=0..m; sequence gives 2-primes. 0-primes are primes (A000040) and 1-primes are safe primes (A005385). a(n)-1 and a(n) are consecutive terms of the sequence A065966. It is not known if there are infinitely many m-primes for m > 0.

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

Cf. A000040, A005385, A065966.

lst={};Do[p=Prime[n];If[PrimeQ[a=(p-1)/2]&&PrimeQ[(a-1)/2],AppendTo[lst,p]],{n,8!}];lst (* Vladimir Joseph Stephan Orlovsky, Feb 27 2009 *)

{ n=0; default(primelimit, 4294965247); for (m=1, 10^9, p=prime(m); if (frac((p-3)/4), next); if (isprime((p-3)/4) && isprime((p-1)/2), write("b066179.txt", n++, " ", p); if (n==1000, return)) ) } \\ Harry J. Smith, Feb 05 2010

Offset changed from 0 to 1 by Harry J. Smith, Feb 05 2010

A066669 Numbers m such that phi(m) = 2^k*prime for some k >= 0.

Original entry on oeis.org

7, 9, 11, 13, 14, 18, 21, 22, 23, 25, 26, 28, 29, 33, 35, 36, 39, 41, 42, 44, 45, 46, 47, 50, 52, 53, 55, 56, 58, 59, 65, 66, 69, 70, 72, 75, 78, 82, 83, 84, 87, 88, 89, 90, 92, 94, 97, 100, 104, 105, 106, 107, 110, 112, 113, 115, 116, 118, 119, 123, 130, 132, 137, 138

Offset: 1

Labos Elemer, Dec 18 2001

nonn

Sequence is infinite, since 2n is in the sequence if and only if n is in the sequence. What is its density? - Charles R Greathouse IV, Feb 21 2013

Products of powers of 2, distinct terms (at least one) of A074781, and possibly (if all the factors from A074781 are Fermat primes, A019434) an additional Fermat prime (i.e., it can be divisible by a square of one Fermat prime, A330828). - Amiram Eldar, Feb 11 2025

			7 is a term because phi(7) = 6 divided by 2 is 3, a prime.
21 is a term because phi(21) = 12 divided by 4 is 3, a prime.
15 is not a term because phi(15) = 8 divided by 8 is 1, not a prime.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A000010, A066670, A066671, A066672, A066673, A065966.

Cf. A019434, A058500, A074781, A330828.

Select[Range@ 138, PrimeQ@ Last@ Most@ NestWhileList[#/2 &, EulerPhi@ #, IntegerQ@ # &] &] (* Michael De Vlieger, Mar 18 2017 *)

is(n)=n=eulerphi(n);isprime(n>>valuation(n,2)) \\ Charles R Greathouse IV, Feb 21 2013

A066670 Primes arising in A066669: the only odd prime divisor of phi(A066669(n)).

Original entry on oeis.org

3, 3, 5, 3, 3, 3, 3, 5, 11, 5, 3, 3, 7, 5, 3, 3, 3, 5, 3, 5, 3, 11, 23, 5, 3, 13, 5, 3, 7, 29, 3, 5, 11, 3, 3, 5, 3, 5, 41, 3, 7, 5, 11, 3, 11, 23, 3, 5, 3, 3, 13, 53, 5, 3, 7, 11, 7, 29, 3, 5, 3, 5, 17, 11, 3, 23, 3, 7, 37, 5, 3, 3, 13, 5, 5, 41, 83, 3, 43, 7, 5, 29, 11, 89, 3, 11, 5, 23, 3, 3

Offset: 1

Labos Elemer, Dec 18 2001

nonn

			A066669(9) = 23, phi(23) = 2*11, so a(9)=11.

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A000010, A000265, A053575, A006530, A065966, A066669, A066671, A066672, A066673.

Select[Array[#/2^IntegerExponent[#, 2] &@ EulerPhi@ # &, 200], PrimeQ]  (* Michael De Vlieger, Dec 08 2018 *)

lista(nn) = {for (n=1, nn, en=eulerphi(n); if (isprime(p=en>>valuation(en, 2)), print1(p, ", ")); ); } \\ Michel Marcus, Dec 08 2018

From Amiram Eldar, Jul 18 2024: (Start)
a(n) = A053575(A066669(n)).
a(n) = A000265(A000010(A066669(n))) = A006530(A000010(A066669(n))). (End)

A066671 a(n) is the largest power of 2 that divides phi(A066669(n)).

Original entry on oeis.org

2, 2, 2, 4, 2, 2, 4, 2, 2, 4, 4, 4, 4, 4, 8, 4, 8, 8, 4, 4, 8, 2, 2, 4, 8, 4, 8, 8, 4, 2, 16, 4, 4, 8, 8, 8, 8, 8, 2, 8, 8, 8, 8, 8, 4, 2, 32, 8, 16, 16, 4, 2, 8, 16, 16, 8, 8, 2, 32, 16, 16, 8, 8, 4, 16, 4, 16, 16, 4, 8, 32, 16, 8, 16, 16, 2, 2, 16, 4, 8, 16, 4, 8, 2, 16, 8, 32, 4, 64, 32, 32

Offset: 1

Labos Elemer, Dec 18 2001

nonn

			The first, 4th and 15th terms in A066669 are 7, 13 and 35; phi(7) = 2*3, phi(13) = 4*3, phi(35) = 24 = 8*3; the largest powers of 2 are 2, 4 and 8; so a(1) = 2, a(4) = 4, a(15) = 8.

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A000010, A065966, A066669, A066670, A066672, A066673, A069177.

Select[Array[{#1/#2, #2} & @@ {#, 2^IntegerExponent[#, 2]} &@ EulerPhi@ # &, 200], PrimeQ@ First@ # &][[All, -1]] (* Michael De Vlieger, Dec 08 2018 *)

lista(nn) = {for (n=1, nn, en=eulerphi(n); if (isprime(p=en>>valuation(en, 2)), print1(en/p, ", ")););} \\ Michel Marcus, Jan 03 2017

From Amiram Eldar, Jul 18 2024: (Start)
a(n) = A069177(A066669(n)).
a(n) = 2^A066672(n). (End)

Name corrected by Amiram Eldar, Jul 18 2024

A194593 Semiprimes s such that phi(s)/2 is prime.

Original entry on oeis.org

9, 10, 14, 22, 46, 94, 118, 166, 214, 334, 358, 454, 526, 694, 718, 766, 934, 958, 1006, 1126, 1174, 1438, 1678, 1726, 1774, 1966, 2038, 2374, 2566, 2614, 2638, 2734, 2878, 2974, 3046, 3238, 3646, 3814, 4054, 4078, 4126, 4198, 4414, 4894, 4918, 5158, 5638, 5758, 5806, 5926, 5998

Offset: 1

Juri-Stepan Gerasimov, Aug 30 2011

nonn

For n > 2, A001221(a(n)) = A001221(A000010(a(n))) = 2, and A008683(a(n)) = A008683(A000010(a(n))) = 1. - Torlach Rush, Aug 23 2018

For n > 1, A000010(a(n)) = A077065(n-1). - Torlach Rush, Sep 11 2018

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

Cf. A000010, A001358, A005384, A005385, A079148, A065966.

[9] cat [2*p: p in PrimesUpTo(3000) | IsPrime((p - 1) div 2)]; // Vincenzo Librandi, Aug 25 2018

9, 10, op(select(s -> isprime(s/2) and isprime((s-2)/4), [seq(s,s=6..10000,8)])); # Robert Israel, Apr 06 2016

Select[Range@ 6000, PrimeOmega@ # == 2 && PrimeQ[EulerPhi[#]/2] &] (* Michael De Vlieger, Apr 06 2016 *)

isok(n) = (bigomega(n)== 2) && isprime(eulerphi(n)/2); \\ Michel Marcus, Apr 06 2016

a(n) = 2*A005385(n-1), n>1.

a(n) = 4*A005384(n-1) + 2, n > 1. - Michel Marcus, Apr 02 2020

Corrected by R. J. Mathar, Oct 13 2011

A180642 Numbers k such that phi(k)/4 is a prime, where phi is the Euler totient function.

Original entry on oeis.org

13, 15, 16, 20, 21, 24, 25, 26, 28, 29, 30, 33, 36, 42, 44, 50, 53, 58, 66, 69, 92, 106, 138, 141, 149, 173, 177, 188, 236, 249, 269, 282, 293, 298, 317, 321, 332, 346, 354, 389, 428, 498, 501, 509, 537, 538, 557, 586, 634, 642, 653, 668, 681, 716, 773, 778, 789

Offset: 1

Carmine Suriano, Sep 14 2010

nonn

Apparently the sequence is infinite, but I have no proof. There are many n-ples of consecutives: (15,16)-(20,21)-(24,25,26)-(537,538)-(1436,1437)-...-(30236-30237)

This sequence is infinite if and only if there are infinitely many primes of the form 2p+1 or 4p+1 with prime p. - Charles R Greathouse IV, Feb 04 2013

			a(5) = 21 since pi(21)/4 = 12/4 = 3 is prime.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000010, A065966 (phi(k)/2 is prime), A090866 (subsequence of primes).

Select[Range[800],PrimeQ[EulerPhi[#]/4]&] (* Harvey P. Dale, Feb 11 2015 *)

is(n)=n=eulerphi(n);n%4==0 && isprime(n/4) \\ Charles R Greathouse IV, Feb 04 2013

is(n)=if(n<51,n=eulerphi(n);n%4==0 && isprime(n/4),my(v=[3,4,6]);for(i=1,#v,if(n%(2*v[i])==v[i]&&gcd(n/v[i],v[i])==1&&isprime(n/v[i])&&isprime(eulerphi(n)/4),return(1)));if(n%4==2,n/=2);n%4==1&&isprime(n)&&isprime(n\4)) \\ Charles R Greathouse IV, Feb 04 2013

a(n) >> n log^2 n. - Charles R Greathouse IV, Feb 04 2013

cp's OEIS Frontend

A065976 Consecutive terms of A065966 which are also consecutive integers.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A068213 Duplicate of A065966.

Views

Author

Keywords

A035095 Smallest prime congruent to 1 (mod prime(n)).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Formula

Extensions

A066179 Primes p such that (p-1)/2 and (p-3)/4 are also prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A066669 Numbers m such that phi(m) = 2^k*prime for some k >= 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A066670 Primes arising in A066669: the only odd prime divisor of phi(A066669(n)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A066671 a(n) is the largest power of 2 that divides phi(A066669(n)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A194593 Semiprimes s such that phi(s)/2 is prime.

Views

Author

Keywords

Comments

Links