A157187 Number of ways to write n as p*q-(p+q) with primes p <= q.

1, 1, 0, 2, 0, 1, 0, 1, 0, 1, 0, 2, 0, 0, 0, 2, 0, 1, 0, 1, 0, 1, 0, 2, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 3, 0, 0, 0, 2, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 3, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 4, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 2, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 2, 0, 1, 0, 1, 0

Offset: 0

Author

M. F. Hasler, Mar 11 2009

Keywords

• nonn

Comments

The only even number which can be written in the given way is n=0=2*2-(2+2), since if q an odd prime, pq-(p+q) is always odd.

Erdős shows that this sequence is unbounded. In particular, for any e > 0, there are infinitely many n such that a(n) > exp(sqrt(log n) - e). - Charles R Greathouse IV, Dec 05 2012

The number n = A218862(k) tells where a(n) is first equal to k. - T. D. Noe, Dec 06 2012

Examples

			a(0)=1 since 0=2*2-(2+2) is the only possibility.
a(1)=1 since 1=2*3-(2+3) is the only possibility.
a(2)=0 since 2 cannot be written as pq-(p+q) for primes p,q.
a(3)=2 since 3 = 2*5-(2+5) = 3*3-(3+3) are the two possibilities.
a(15437822399)=100 since p can be taken to be any of {13, 41, 43, 109, 113, 151, 181, 199, 271, 401, 613, 617, 661, 673, 859, 883, 919, 1021, 1123, 1201, 1249, 1471, 1801, 1871, 1951, 2003, 2269, 2647, 2731, 2861, 3169, 3511, 3571, 4159, 4999, 5281, 5881, 6007, 6427, 7057, 7393, 7481, 7841, 9241, 9521, 10193, 12241, 12377, 12853, 13729, 15401, 15913, 16831, 17551, 18701, 20593, 21169, 22051, 22441, 23801, 26951, 27541, 28051, 30577, 30941, 32341, 32401, 34273, 34651, 36037, 36721, 40801, 42043, 46411, 47521, 48049, 51481, 53857, 57331, 59671, 63649, 65521, 66529, 70687, 72931, 76441, 77617, 78541, 87517, 91631, 92401, 96097, 97241, 101921, 102103, 103951, 117811, 120121, 122401, 123553}.
		

Links

• T. D. Noe, Table of n, a(n) for n = 0..10000
• P. Erdős, On the integers which are the totient of a product of two primes, Quart. J. Math., Oxford Ser. 7 (1936), pp. 227-229.

Crossrefs

Cf. A218862.

Programs

Mathematica

nn = 100; ps = Prime[Range[PrimePi[nn + 1]]]; t = Table[0, {nn}]; Do[n = p*q - p - q; If[p <= q && 0 < n <= nn, t[[n]]++], {p, ps}, {q, ps}]; Join[{1}, t] (* T. D. Noe, Dec 05 2012 *)

PARI

A157187(n)=local(c=0,L=sqrtint(n++)); fordiv( n,d, d>L && break; isprime(d+1) && isprime(n/d+1) && c++);c

Formula

a(13+20n) = 0 for all n. - T. D. Noe, Dec 06 2012