A236531 -id:A236531 - cp's OEIS frontend

A218829 Number of ordered ways to write n = k + m with k > 0 and m > 0 such that prime(k) + 2 and prime(prime(m)) + 2 are both prime.

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

Offset: 1

Zhi-Wei Sun, Feb 05 2014

nonn

Conjecture: (i) a(n) > 0 for all n > 2, and a(n) = 1 only for n = 3, 22, 25, 38, 101, 273.
(ii) Each n = 2, 3, ... can be written as k + m with k > 0 and m > 0 such that 6*k - 1, 6*k + 1 and prime(prime(m)) + 2 are all prime.
(iii) Any integer n > 5 can be written as k + m with k > 0 and m > 0 such that phi(k) - 1, phi(k) + 1 and prime(prime(m)) + 2 are all prime, where phi(.) is Euler's totient function.
(iv) If n > 2 is neither 10 nor 31, then n can be written as k + m with k > 0 and m > 0 such that prime(k) + 2 and prime(prime(prime(m))) + 2 are both prime.
(v) If n > 1 is not equal to 133, then n can be written as k + m with k > 0 and m > 0 such that 6*k - 1, 6*k + 1 and prime(prime(prime(m))) + 2 are all prime.
Clearly, each part of the conjecture implies the twin prime conjecture.
We have verified part (i) for n up to 10^9. See the comments in A237348 for an extension of this part.

			a(3) = 1 since 3 = 2 + 1 with prime(2) + 2 = 3 + 2 = 5 and prime(prime(1)) + 2 = prime(2) + 2 = 5 both prime.
a(22) = 1 since 22 = 20 + 2 with prime(20) + 2 = 71 + 2 = 73 and prime(prime(2)) + 2 = prime(3) + 2 = 5 + 2 = 7 both prime.
a(25) = 1 since 25 = 2 + 23 with prime(2) + 2 = 3 + 2 = 5 and prime(prime(23)) + 2 = prime(83) + 2 = 431 + 2 = 433 both prime.
a(38) = 1 since 38 = 35 + 3 with prime(35) + 2 = 149 + 2 = 151 and prime(prime(3)) + 2 = prime(5) + 2 = 11 + 2 = 13 both prime.
a(101) = 1 since 101 = 98 + 3 with prime(98) + 2 = 521 + 2 = 523 and prime(prime(3)) + 2 = prime(5) + 2 = 11 + 2 = 13 both prime.
a(273) = 1 since 273 = 2 + 271 with prime(2) + 2 = 3 + 2 = 5 and prime(prime(271)) + 2 = prime(1741) + 2 = 14867 + 2 = 14869 both prime.

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000
Andrei-Lucian Dragoi, The "Vertical" Generalization of the Binary Goldbach's Conjecture as Applied on "Iterative" Primes with (Recursive) Prime Indexes (i-primeths), Journal of Advances in Mathematics and Computer Science (2017), Vol. 25, No. 2, pp. 1-32.
Zhi-Wei Sun, Unification of Goldbach's conjecture and the twin prime conjecture, a message to Number Theory List, Jan. 29, 2014.
Zhi-Wei Sun, Super Twin Prime Conjecture, a message to Number Theory List, Feb. 6, 2014.
Z.-W. Sun, Problems on combinatorial properties of primes, arXiv:1402.6641, 2014

Cf. A000010, A000040, A001359, A002822, A006512, A072281, A182662, A199920, A236531, A236566, A236831, A236968, A237127, A237130, A237168, A237253, A237259, A237260, A237348.

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

A236566 Number of ordered ways to write 2*n = p + q with p, q and prime(p + 2) + 2 all prime.

Original entry on oeis.org

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

Offset: 1

Zhi-Wei Sun, Jan 28 2014

nonn

Conjecture: (i) a(n) > 0 for all n > 2.
(ii) If n > 30, then 2*n + 1 can be written as 2*p + q with p, q and prime(p + 2) + 2 all prime.
Part (i) implies both the Goldbach conjecture and the twin prime conjecture. If all primes p with prime(p + 2) + 2 are smaller than an even number N > 2, then for any such a prime p the number N! + N - p is in the interval (N!, N! + N) and hence not prime.
Similarly, part (ii) implies both Lemoine's conjecture (cf. A046927) and the twin prime conjecture.
We have verified part (i) of the conjecture for n up to 2*10^8.

			a(10) = 1 since 2*10 = 3 + 17 with 3, 17 and prime(3 + 2) + 2 = 11 + 2 = 13 all prime.
a(589) = 1 since 2*589 = 577 + 601 with 577, 601 and prime(577 + 2) + 2 = 4229 + 2 = 4231 all prime.

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

Cf. A000040, A001359, A002372, A002375, A006512, A046927, A236531.

p[m_]:=PrimeQ[Prime[m+2]+2]
a[n_]:=Sum[If[p[Prime[k]]&&PrimeQ[2n-Prime[k]],1,0],{k,1,PrimePi[2n-1]}]
Table[a[n],{n,1,100}]

A237130 Number of ordered ways to write n = k + m with k > 0 and m > 0 such that both {3k - 1, 3k + 1} and {phi(m) - 1, phi(m) + 1} are twin prime pairs, where phi(.) is Euler's totient function.

Original entry on oeis.org

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

Offset: 1

Zhi-Wei Sun, Feb 04 2014

nonn

Conjecture: (i) a(n) > 0 for all n > 8.
(ii) Any integer n > 6 can be written as k + m with k > 0 and m > 0 such that both {prime(k), prime(k) + 2} and {phi(m) - 1, phi(m) + 1} are twin prime pairs.
(iii) Each n = 12, 13, ... can be written as p + q (q > 0) with p, p + 6, phi(q) - 1 and phi(q) + 1 all prime.
(iv) If n > 2 is neither 10 nor 430, then n can be written as k + m with k > 0 and m > 0 such that both {3k - 1, 3*k + 1} and {6*m - 1, 6*m + 1} are twin prime pairs.
Note that each part of the above conjecture implies the twin prime conjecture.

			a(7) = 1 since 7 = 2 + 5 with 3*2 - 1 = 5, 3*2 + 1 =7, phi(5) - 1 = 3 and phi(5) + 1 = 5 all prime.
a(140) = 1 since 140 = 104 + 36 with 3*104 - 1 = 311, 3*104 + 1 = 313, phi(36) - 1 = 11 and phi(36) + 1 = 13 all prime.

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

Cf. A000010, A000040, A001359, A006512, A014574, A072281, A182662, A236531, A236566, A236831, A236968, A237127.

PQ[n_]:=PrimeQ[EulerPhi[n]-1]&&PrimeQ[EulerPhi[n]+1]
a[n_]:=Sum[If[PrimeQ[3k-1]&&PrimeQ[3k+1]&&PQ[n-k],1,0],{k,1,n-1}]
Table[a[n],{n,1,100}]

A238573 a(n) = |{0 < k <= n: prime(k*n) + 2 is prime}|.

Original entry on oeis.org

0, 1, 1, 0, 3, 0, 4, 1, 2, 3, 1, 3, 4, 4, 4, 4, 1, 3, 6, 5, 3, 3, 4, 6, 3, 8, 5, 6, 3, 4, 2, 10, 6, 5, 7, 8, 6, 8, 7, 5, 7, 5, 11, 7, 7, 8, 8, 11, 6, 5, 7, 11, 11, 7, 4, 9, 7, 3, 5, 7, 7, 11, 8, 13, 9, 8, 7, 7, 12, 10, 8, 11, 8, 15, 8, 9, 9, 15, 13, 4

Offset: 1

Zhi-Wei Sun, Mar 01 2014

nonn

Conjecture: (i) a(n) > 0 for all n > 6, and a(n) = 1 only for n = 2, 3, 8, 11, 17. Moreover, for any n > 0 there exists a positive integer k < 3*sqrt(n) + 6 such that prime(k*n) + 2 is prime.
(ii) For any integer n > 6, prime(k^2*n) + 2 is prime for some k = 1, ..., n.
(iii) If n > 5, then prime(k^2*(n-k)) + 2 is prime for some 0 < k < n.
Clearly, each of the three parts implies the twin prime conjecture.
We have verified part (i) of the conjecture for n up to 2*10^6.

			a(2) = 1 since prime(1*2) + 2 = 3 + 2 = 5 is prime.
a(3) = 1 since prime(1*3) + 2 = 5 + 2 = 7 is prime.
a(8) = 1 since prime(8*8) + 2 = 311 + 2 = 313 is prime.
a(11) = 1 since prime(3*11) + 2 = 137 + 2 = 139 is prime.
a(17) = 1 since prime(1*17) + 2 = 59 + 2 = 61 is prime.

Zhi-Wei Sun, Table of n, a(n) for n = 1..5000
Zhi-Wei Sun, Problems on combinatorial properties of primes, arXiv:1402.6641, 2014.

Cf. A000040, A001359, A006512, A218829, A236531, A237578, A238576.

p[k_,n_]:=PrimeQ[Prime[k*n]+2]
a[n_]:=Sum[If[p[k,n],1,0],{k,1,n}]
Table[a[n],{n,1,80}]

A236831 Number of ordered ways to write n = p + q with q > 0 such that p, p + 2 and p + prime(q) + 1 are all prime.

Original entry on oeis.org

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

Offset: 1

Zhi-Wei Sun, Jan 31 2014

nonn

Conjecture: a(n) > 0 for all n > 13.

			a(12) = 1 since 12 = 5 + 7 with 5, 5 + 2 = 7 and 5 + prime(7) + 1 = 5 + 17 + 1 = 23 all prime.
a(85) = 1 since 85 = 29 + 56 with 29, 29 + 2 = 31 and 29 + prime(56) + 1 = 29 + 263 + 1 = 293 all prime.

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000
Z.-W. Sun, Problems on combinatorial properties of primes, arXiv:1402.6641, 2014

Cf. A000040, A001359, A006512, A236531.

p[n_,m_]:=PrimeQ[m+2]&&PrimeQ[m+Prime[n-m]+1]
a[n_]:=Sum[If[p[n,Prime[k]],1,0],{k,1,PrimePi[n-1]}]
Table[a[n],{n,1,100}]

A182662 Number of ordered ways to write n = p + q with q > 0 such that p, 3(p + prime(q)) - 1 and 3(p + prime(q)) + 1 are all prime.

Original entry on oeis.org

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

Offset: 1

Zhi-Wei Sun, Jan 31 2014

nonn

Conjecture: a(n) > 0 if n is not a divisor of 12.

Clearly, this implies the twin prime conjecture.

			a(11) = 1 since 11 = 7 + 4 with 7, 3*(7 + prime(4)) - 1 = 3*14 - 1 = 41 and 3*(7 + prime(4)) + 1 = 3*14 + 1 = 43 all prime.
a(210) = 1 since 210 = 97 + 113 with 97, 3*(97 + prime(113)) - 1 = 3*(97 + 617) - 1 = 2141 and 3*(97 + prime(113)) + 1 = 3*(97 + 617) + 1 =  2143 all prime.

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000
Z.-W. Sun, Problems on combinatorial properties of primes, arXiv:1402.6641, 2014

Cf. A000040, A001359, A006512, A236531, A236831.

p[n_,m_]:=PrimeQ[3(m+Prime[n-m])-1]&&PrimeQ[3(m+Prime[n-m])+1]
a[n_]:=Sum[If[p[n,Prime[k]],1,0],{k,1,PrimePi[n-1]}]
Table[a[n],{n,1,100}]

A236968 Number of ordered ways to write n = k + m with k > 0 and m > 0 such that 6k - 1, 6k + 1 and k + phi(m) are all prime, where phi(.) is Euler's totient function.

Original entry on oeis.org

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

Offset: 1

Zhi-Wei Sun, Feb 02 2014

nonn

Conjecture: (i) a(n) > 0 for all n > 1. Also, any n > 12 can be written as k + m (k > 0 and m > 2) with 6*k - 1, 6*k + 1 and k + phi(m)/2 all prime.
(ii)  Each integer n > 34 can be written as p + q (q > 0) with p and p + phi(q) both prime. Also, any integer n > 14 can be written as p + q (q > 2) with p, p + 6 and p + phi(q)/2 all prime.
Clearly, part (i) of the conjecture implies that any integer n > 1 can be written as p + m - phi(m), where p is a prime and m is a positive integer.

			a(17) = 1 since 17 = 7 + 10 with 6*7 - 1 = 41, 6*7 + 1 = 43 and 7 + phi(10) = 7 + 4 = 11 all prime.
a(486) = 1 since 486 = 325 + 161 with 6*325 - 1 = 1949, 6*325 + 1 = 1951 and 325 + phi(161) = 325 + 132 = 457 all prime.

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

Cf. A000010, A000040, A001359, A002822, A006512, A182662, A199920, A236531, A236831.

p[n_,k_]:=PrimeQ[6k-1]&&PrimeQ[6k+1]&&PrimeQ[k+EulerPhi[n-k]]
a[n_]:=Sum[If[p[n,k],1,0],{k,1,n-1}]
Table[a[n],{n,1,100}]

A237253 Number of ordered ways to write n = k + m with k > 0 and m > 0 such that phi(k) - 1, phi(k) + 1 and prime(prime(prime(m))) - 2 are all prime, where phi(.) is Euler's totient function.

Original entry on oeis.org

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

Offset: 1

Zhi-Wei Sun, Feb 05 2014

nonn

Conjecture: (i) a(n) > 0 for all n > 7.
(ii) Any integer n > 22 can be written as k + m with k > 0 and m > 0 such that prime(k) + 2 and prime(prime(prime(m))) - 2 are both prime.
Note that either part of the conjecture implies the twin prime conjecture.

			 a(12) = 1 since 12 = 9 + 3 with phi(9) - 1 = 5, phi(9) + 1 = 7 and prime(prime(prime(3))) - 2 = prime(prime(5)) - 2 = prime(11) - 2 = 29 all prime.
a(103) = 1 since 103 = 73 + 30 with phi(73) - 1 = 71, phi(73) + 1 = 73 and prime(prime(prime(30))) - 2 = prime(prime(113)) - 2 = prime(617) - 2 = 4547 all prime.

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

Cf. A000010, A000040, A001359, A006512, A072281, A218829, A236531, A236566, A237127, A237130, A237168.

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

A236573 Number of ordered ways to write n = k + m (k > 0, m > 0) such that p = 2k + phi(m) - 1, prime(p + 2) + 2 and 2n - p are all prime, where phi(.) is Euler's totient function.

Original entry on oeis.org

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

Offset: 1

Zhi-Wei Sun, Jan 29 2014

nonn

Conjecture: a(n) > 0 for all n > 712.

This implies the conjecture in A236566.

			a(100) = 1 since 100 = 10 + 90 with 2*10 + phi(90) - 1 = 20 + 24 - 1 = 43, prime(43 + 2) + 2 = 197 + 2 = 199 and 2*100 - 43 = 157 all prime.
a(1727) = 1 since 1727 = 956 + 771 with 2*956 + phi(771) - 1 = 1912 + 512 - 1 = 2423, prime(2423 + 2) + 2 = 21599 + 2 = 21601 and 2*1727 - 2423 = 1031 all prime.

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

Cf. A000010, A000040, A001359, A002372, A002375, A006512, A234808, A236531, A236566, A236568, A236569.

p[n_]:=PrimeQ[n]&&PrimeQ[Prime[n+2]+2]
f[n_,k_]:=2k+EulerPhi[n-k]-1
a[n_]:=Sum[If[p[f[n,k]]&&PrimeQ[2n-f[n,k]],1,0],{k,1,n-1}]
Table[a[n],{n,1,100}]

cp's OEIS Frontend

A218829 Number of ordered ways to write n = k + m with k > 0 and m > 0 such that prime(k) + 2 and prime(prime(m)) + 2 are both prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A236566 Number of ordered ways to write 2*n = p + q with p, q and prime(p + 2) + 2 all prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A237130 Number of ordered ways to write n = k + m with k > 0 and m > 0 such that both {3*k - 1, 3*k + 1} and {phi(m) - 1, phi(m) + 1} are twin prime pairs, where phi(.) is Euler's totient function.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A238573 a(n) = |{0 < k <= n: prime(k*n) + 2 is prime}|.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A236831 Number of ordered ways to write n = p + q with q > 0 such that p, p + 2 and p + prime(q) + 1 are all prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A182662 Number of ordered ways to write n = p + q with q > 0 such that p, 3*(p + prime(q)) - 1 and 3*(p + prime(q)) + 1 are all prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A236968 Number of ordered ways to write n = k + m with k > 0 and m > 0 such that 6*k - 1, 6*k + 1 and k + phi(m) are all prime, where phi(.) is Euler's totient function.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A237253 Number of ordered ways to write n = k + m with k > 0 and m > 0 such that phi(k) - 1, phi(k) + 1 and prime(prime(prime(m))) - 2 are all prime, where phi(.) is Euler's totient function.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

A237130 Number of ordered ways to write n = k + m with k > 0 and m > 0 such that both {3k - 1, 3k + 1} and {phi(m) - 1, phi(m) + 1} are twin prime pairs, where phi(.) is Euler's totient function.

A182662 Number of ordered ways to write n = p + q with q > 0 such that p, 3(p + prime(q)) - 1 and 3(p + prime(q)) + 1 are all prime.

A236968 Number of ordered ways to write n = k + m with k > 0 and m > 0 such that 6k - 1, 6k + 1 and k + phi(m) are all prime, where phi(.) is Euler's totient function.

A236573 Number of ordered ways to write n = k + m (k > 0, m > 0) such that p = 2k + phi(m) - 1, prime(p + 2) + 2 and 2n - p are all prime, where phi(.) is Euler's totient function.