A286424 Number of partitions of p_n# into parts (q, k) both coprime to p_n#, with q prime and k nonprime, where p_n# = A002110(n).

0, 0, 1, 1, 4, 110, 1432, 23338, 397661, 8193828, 212858328, 5941706227

Offset: 0

Author

Michael De Vlieger, May 08 2017

Keywords

• nonn
• hard
• more

Comments

Number of totative pairs (q, k) such that prime q + k nonprime = p_n# and both gcd(q, p_n#) = 1 and gcd(k, p_n#) = 1, with p_n < q <= pi(p_n#), where pi(p_n#) = A000849(n) - n = A048862(n).

Primes p_n < q <= pi(p_n#) are greater than the greatest prime factor of p_n# = p_n, and are thus coprime to p_n#. By the definition of primorial, we need not consider p >= p_n, as these p are divisors of p_n#, i.e., gcd(p, p_n#) = p. Since the totatives of m can be paired such that a + b = m, we need only determine if (p_n# - q) is not prime in order to count pairs (q, k).

a(n) < floor(A005867(n)/2).

a(n) <= A048862(n).

The totative pair (q,1) = (p_n# - 1, 1) is counted by a(n) for n in A057704, with (p_n# - 1) appearing in A057705.

Examples

			a(0) = 0 by definition. A002110(0) = 1; 1 is coprime to all numbers; the only possible totative pair is (1,1) and this does not include both a prime and a nonprime.
a(1) = 0 since, of the floor(A005867(1)/2) = 1 totative pair (1,1) of A002110(1) = 2, none include a both a prime and a nonprime.
a(2) = 1 since, the only totative pair (1,5) of A002110(1) = 6 includes both a prime and a nonprime.
a(3) = 1 since only (1,29) includes both a prime and a nonprime.
a(4) = 4 since (23,187), (41,169), (67,143), (89,121) include a both a prime and a nonprime.
		

Links

• C. K. Caldwell, The Prime Glossary, Primorial.
• Eric Weisstein's World of Mathematics, Totative.

Crossrefs

Cf. A000849, A002110, A005867, A048862, A048863, A057704, A057705, A116979, A117929.

Programs

Mathematica

Table[Function[P, Count[Prime@ Range[n + 1, PrimePi[P]], q_ /; ! PrimeQ[P - q]]]@ Product[Prime@ i, {i, n}], {n, 0, 9}] (* Michael De Vlieger, May 08 2017 *)

Formula

a(n) = (A000010(A002110(n)) - A048863(n)) - 2*A117929(A002110(n))

= (A005867(n) - A048863(n)) - 2*A117929(A002110(n))

= A048862(n) - 2*A117929(A002110(n)).

Extensions

a(11) from Giovanni Resta, May 09 2017