A039698 -id:A039698 - cp's OEIS frontend

A001751 Primes together with primes multiplied by 2.

2, 3, 4, 5, 6, 7, 10, 11, 13, 14, 17, 19, 22, 23, 26, 29, 31, 34, 37, 38, 41, 43, 46, 47, 53, 58, 59, 61, 62, 67, 71, 73, 74, 79, 82, 83, 86, 89, 94, 97, 101, 103, 106, 107, 109, 113, 118, 122, 127, 131, 134, 137, 139, 142, 146, 149, 151, 157, 158, 163, 166

Offset: 1

N. J. A. Sloane

For n > 1, a(n) is position of primes in A026741.
For n > 1, a(n) is the position of the ones in A046079. - Ant King, Jan 29 2011
A251561(a(n)) != a(n). - Reinhard Zumkeller, Dec 27 2014
Number of terms <= n is pi(n) + pi(n/2). - Robert G. Wilson v, Aug 04 2017
Number of terms <=10^k: 7, 40, 263, 1898, 14725, 120036, 1013092, 8762589, 77203401, 690006734, 6237709391, 56916048160, 523357198488, 4843865515369, ..., . - Robert G. Wilson v, Aug 04 2017
Complement of A264828. - Chai Wah Wu, Oct 17 2024

T. D. Noe, Table of n, a(n) for n = 1..10000

Union of A001747 and A000040.
Subsequence of A039698 and of A033948.
Cf. A026741, A046079, A178156, A251561, A264828.

a001751 n = a001751_list !! (n-1)
a001751_list = 2 : filter (\n -> (a010051 $ div n $ gcd 2 n) == 1) [1..]
-- Reinhard Zumkeller, Jun 20 2011 (corrected, improved), Dec 17 2010

Select[Range[163], Or[PrimeQ[#], PrimeQ[1/2 #]] &] (* Ant King, Jan 29 2011 *)
upto=200;With[{pr=Prime[Range[PrimePi[upto]]]},Select[Sort[Join[pr,2pr]],# <= upto&]] (* Harvey P. Dale, Sep 23 2014 *)

isA001751(n)=isprime(n/gcd(n,2)) || n==2

list(lim)=vecsort(concat(primes(primepi(lim)), 2* primes(primepi(lim\2)))) \\ Charles R Greathouse IV, Oct 31 2012

from sympy import primepi
def A001751(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return int(n+x-primepi(x)-primepi(x>>1))
    return bisection(f,n,n) # Chai Wah Wu, Oct 17 2024

A066071 Nonprime numbers k such that phi(k) + 1 is prime.

Original entry on oeis.org

1, 4, 6, 8, 9, 10, 12, 14, 18, 21, 22, 26, 27, 28, 32, 34, 36, 38, 40, 42, 46, 48, 49, 54, 55, 57, 58, 60, 62, 63, 74, 75, 76, 77, 82, 86, 88, 91, 93, 94, 95, 98, 99, 100, 106, 108, 110, 111, 114, 115, 117, 118, 119, 122, 124, 125, 126, 132, 133, 134, 135, 142, 145, 146

Offset: 1

Labos Elemer, Dec 03 2001

nonn

A039698 with the primes removed. For every prime p, 2p is in the sequence. - Ray Chandler, May 26 2008

Includes 3*p for p in A005382 and p^2 for p in A065508. - Robert Israel, Dec 29 2017

			Solutions to 1+phi(x)=13 are {13, 21, 26, 28, 36, 42} of which the 5 composites are in the sequence.

Iain Fox, Table of n, a(n) for n = 1..10000 (first 1000 terms from Harry J. Smith)

Cf. A000010, A000040, A005382, A006093, A039649, A039698, A058339, A058340, A065508, A066072, A066073, A066074, A066075, A066076, A066077, A066080.

[n: n in [1..200] |not IsPrime(n) and IsPrime(EulerPhi(n)+1)]; // Vincenzo Librandi, Jul 02 2016

select(n -> not isprime(n) and isprime(1+numtheory:-phi(n)), [$1..1000]); # Robert Israel, Dec 29 2017

Select[Complement[Range@ #, Prime@ Range@ PrimePi@ #] &@ 150, PrimeQ[EulerPhi@ # + 1] &] (* Michael De Vlieger, Jul 01 2016 *)

isok(k) = { !isprime(k) && isprime(eulerphi(k) + 1) } \\ Harry J. Smith, Nov 10 2009

A072281 Numbers n such that phi(n) + 1 and phi(n) - 1 are twin primes.

Original entry on oeis.org

5, 7, 8, 9, 10, 12, 13, 14, 18, 19, 21, 26, 27, 28, 31, 36, 38, 42, 43, 49, 54, 61, 62, 73, 77, 86, 91, 93, 95, 98, 99, 103, 109, 111, 117, 122, 124, 133, 135, 139, 146, 148, 151, 152, 154, 171, 181, 182, 186, 189, 190, 193, 198, 199, 206, 209, 216, 217, 218, 221, 222

Offset: 1

Joseph L. Pe, Jul 10 2002

Phi(n) is middle term between twin primes (A014574). Union of A006512 and A068019; intersection of A039698 and A078892. - Ray Chandler, May 26 2008

The positions of isolated nonprimes in A000010. - Juri-Stepan Gerasimov, Nov 10 2009

			phi(14) + 1 = 7 and phi(14) - 1 = 5, so 14 is a term of the sequence.

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

Cf. A000010, A000040, A006512, A014574, A039698, A068019, A078892.

Select[Range[10^3], PrimeQ[EulerPhi[ # ] + 1] && PrimeQ[EulerPhi[ # ] - 1] &]
Select[Range[300],And@@PrimeQ[EulerPhi[#]+{1,-1}]&] (* Harvey P. Dale, Apr 07 2012 *)

isok(n) = my(p); isprime(p=eulerphi(n)-1) && isprime(p+2); \\ Michel Marcus, Sep 29 2019

Extended by Ray Chandler, May 26 2008

A078892 Numbers n such that phi(n) - 1 is prime, where phi is Euler's totient function (A000010).

Original entry on oeis.org

5, 7, 8, 9, 10, 12, 13, 14, 15, 16, 18, 19, 20, 21, 24, 25, 26, 27, 28, 30, 31, 33, 35, 36, 38, 39, 42, 43, 44, 45, 49, 50, 51, 52, 54, 56, 61, 62, 64, 65, 66, 68, 69, 70, 72, 73, 77, 78, 80, 81, 84, 86, 90, 91, 92, 93, 95, 96, 98, 99, 102, 103, 104, 105, 109, 111, 112, 117

Offset: 1

Reinhard Zumkeller, Dec 12 2002

For all primes p: p is in the sequence iff p is the greater member of a twin prime pair (A006512), see A078893.

Union of A006512 and A078893. - Ray Chandler, May 26 2008

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

Cf. A000010, A000040, A008864, A109606, A006512, A039698, A072281, A078893.

[n: n in [1..200] | IsPrime(EulerPhi(n)-1)]; // Vincenzo Librandi, Aug 13 2013

Select[Range[200], PrimeQ[EulerPhi[#] - 1]&] (* Vincenzo Librandi, Aug 13 2013 *)

is(n)=isprime(eulerphi(n)-1) \\ Charles R Greathouse IV, Feb 21 2013

A296078 Least number with the same prime signature as 1+phi(n), where phi = A000010, Euler totient function.

Original entry on oeis.org

2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 4, 2, 2, 2, 4, 2, 2, 2, 4, 6, 2, 2, 2, 2, 4, 2, 2, 6, 2, 4, 2, 2, 2, 4, 2, 2, 2, 2, 6, 4, 2, 2, 2, 2, 6, 6, 4, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 2, 6, 4, 6, 2, 6, 12, 4, 2, 4, 2, 2, 2, 2, 2, 4, 2, 6, 6, 2, 2, 4, 6, 2, 6, 2, 2, 4, 2, 12, 2, 2, 2, 6, 2, 2, 2, 2, 2, 6, 2, 4, 4

Offset: 1

Antti Karttunen, Dec 05 2017

nonn

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A000010, A046523, A039649, A296079, A296080.
Cf. A039698 (positions of 2's).
Cf. also A277906, A296076, A296085, A296092.

f[n_] := Block[{ps = Last@# & /@ FactorInteger[1 + EulerPhi@n]}, Times @@ ((Prime@ Range@ Length@ ps)^ps)]; Array[f, 105] (* Robert G. Wilson v, Dec 11 2017 *)

A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); }; \\ This function from Charles R Greathouse IV, Aug 17 2011
A296078(n) = A046523(1+eulerphi(n));

a(n) = A046523(A039649(n)) = A046523(1+A000010(n)).

A263028 Numbers n such that A002322(n) + 1 is a prime, where A002322 is Carmichael lambda.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 27, 28, 29, 30, 31, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 51, 52, 53, 54, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 76, 77, 78, 79, 80, 82, 83

Offset: 1

Vincenzo Librandi, Oct 12 2015

Complement of A263029.

Antti Karttunen, Table of n, a(n) for n = 1..39743

Cf. A002322, A263027, A263029, A296077 (characteristic function).

Cf. also A039698.

[1] cat [n: n in [2..100] | IsPrime(CarmichaelLambda(n)+1)];

Select[Range[1, 100], PrimeQ[CarmichaelLambda[#] + 1] &]

for(n=1, 1e3, if(isprime((1 + lcm(znstar(n)[2]))), print1(n", "))) \\ Altug Alkan, Oct 12 2015

More terms from Antti Karttunen, Dec 05 2017

A296079 a(n) = 1 if 1+phi(n) is prime, 0 otherwise, where phi = A000010, Euler totient function.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0

Offset: 1

Antti Karttunen, Dec 05 2017

nonn

Out of the first 65537 values, 26197 are 1's (indicating primes), and 39340 are 0's, indicating nonprimes.

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for characteristic functions

Characteristic function of A039698.
Cf. A039689 (positions of zeros).
Cf. also A296077, A296078, A296080.

Table[If[PrimeQ[EulerPhi[n]+1],1,0],{n,120}] (* Harvey P. Dale, Apr 23 2020 *)

PARI
```
A296079(n) = isprime(1+eulerphi(n));
```

a(n) = A010051(A039649(n)) = A010051(1+A000010(n)).

For all n, a(n) >= A010051(n) and a(2n) >= A010051(n).

A039689 Numbers k such that phi(k) + 1 is not a prime.

Original entry on oeis.org

15, 16, 20, 24, 25, 30, 33, 35, 39, 44, 45, 50, 51, 52, 56, 64, 65, 66, 68, 69, 70, 72, 78, 80, 81, 84, 85, 87, 90, 92, 96, 102, 104, 105, 112, 116, 120, 121, 123, 128, 129, 130, 136, 138, 140, 141, 143, 144, 147, 155, 156, 159, 160, 161, 162, 164, 165, 168, 170

Offset: 1

Olivier Gérard

			phi(20)+1 = 8+1 = 9 is not prime.

Antti Karttunen, Table of n, a(n) for n = 1..39340

Cf. A000010, A007614, A039649, A039698 (complement).
Positions of zeros in A296079.
Cf. also A263029.

Select[Range[200],!PrimeQ[EulerPhi[#]+1]&] (* Harvey P. Dale, Aug 31 2018 *)

isok(k) = !isprime(eulerphi(k)+1); \\ Michel Marcus, Jun 28 2021

Name edited by Antti Karttunen, Dec 05 2017

A214288 Primes of the form phi(n)+1 sorted by increasing n, where phi is the Euler totient function.

Original entry on oeis.org

2, 2, 3, 3, 5, 3, 7, 5, 7, 5, 11, 5, 13, 7, 17, 7, 19, 13, 11, 23, 13, 19, 13, 29, 31, 17, 17, 13, 37, 19, 17, 41, 13, 43, 23, 47, 17, 43, 53, 19, 41, 37, 29, 59, 17, 61, 31, 37, 67, 71, 73, 37, 41, 37, 61, 79, 41, 83, 43, 41, 89, 73, 61, 47, 73, 97, 43, 61, 41, 101, 103, 53, 107, 37

Offset: 1

Vincenzo Librandi, Jul 13 2012

Primes in A039649.

All primes are in the sequence.

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

Cf. A000010, A039698 (associated n), A214287.

Select[Table[EulerPhi[n]+1,{n,1,1000}],PrimeQ]

A237184 Number of ordered ways to write n = (1+(n mod 2))*p + q with p, q, phi(p+1) - 1 and phi(q-1) + 1 all prime.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 2, 0, 2, 1, 3, 1, 3, 1, 3, 0, 4, 2, 4, 2, 2, 2, 5, 1, 3, 3, 3, 1, 5, 3, 1, 2, 4, 3, 5, 2, 3, 4, 4, 1, 7, 3, 4, 4, 4, 2, 6, 2, 5, 4, 4, 2, 7, 3, 2, 4, 5, 3, 8, 2, 2, 4, 5, 2, 7, 2, 5, 4, 4, 3, 6, 2, 5

Offset: 1

Zhi-Wei Sun, Feb 04 2014

nonn

Conjecture: a(n) > 0 for all n > 23.
This is stronger than Goldbach's conjecture and Lemoine's conjecture (cf. A046927).
We have verified the conjecture for n up to 3*10^6.

			a(10) = 1 since 10 = 7 + 3 with 7, 3, phi(7+1) - 1 = 3 and phi(3-1) + 1 = 2 all prime.
a(499) = 1 since 499 = 2*199 + 101 with 199, 101, phi(199+1) - 1 = 79 and phi(101-1) + 1 = 41 all prime.
a(869) = 1 since 869 = 2*433 + 3 with 433, 3, phi(433+1) - 1 = 179 and phi(3-1) + 1 = 2 all prime.

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000

Cf. A000040, A002372, A002375, A039698, A046927, A078892, A237127, A237130, A237168, A237183.

pq[n_]:=PrimeQ[n]&&PrimeQ[EulerPhi[n+1]-1]
PQ[n_]:=PrimeQ[n]&&PrimeQ[EulerPhi[n-1]+1]
a[n_]:=Sum[If[pq[k]&&PQ[n-(1+Mod[n,2])k],1,0],{k,1,(n-1)/(1+Mod[n,2])}]
Table[a[n],{n,1,80}]

cp's OEIS Frontend

A001751 Primes together with primes multiplied by 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Python

A066071 Nonprime numbers k such that phi(k) + 1 is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

A072281 Numbers n such that phi(n) + 1 and phi(n) - 1 are twin primes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A078892 Numbers n such that phi(n) - 1 is prime, where phi is Euler's totient function (A000010).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

A296078 Least number with the same prime signature as 1+phi(n), where phi = A000010, Euler totient function.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A263028 Numbers n such that A002322(n) + 1 is a prime, where A002322 is Carmichael lambda.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Extensions

A296079 a(n) = 1 if 1+phi(n) is prime, 0 otherwise, where phi = A000010, Euler totient function.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs