A363844 Number of k <= P(n) such that gcd(k,P(n)) > 1, yet there is a prime q | k that does not divide P(n), where P(n) = A002110(n).

0, 0, 0, 5, 95, 1548, 23110, 413508, 8020826, 186514437, 5447473481, 169902931273, 6317112341154, 260105450523376, 11228680152402376, 529602052783103298, 28154196548377380922, 1665532558381753842459, 101854713853486313230170, 6839699495691464491151135, 486637286249491454965285898

Offset

0,4

Links

Table of n, a(n) for n=0..20.

Formula

a(n) = A243823(A002110(n)).

a(n) = P(n) - A000010(P(n)) - A010846(P(n)) + 1, where P(n) = A002110(n).

a(n) = A002110(n) - A005867(n) - A363061(n) + 1.

Example

a(0) = 0 since P(0) = 1; phi(1) = 1 and A010846(1) = 1, hence 1 - 1 - 1 + 1 = 0.
a(1) = 0 since P(1) = 2; phi(2) = 1 and A010846(2) = 2, hence 2 - 1 - 2 + 1 = 0.
a(2) = 0 since P(2) = 6; phi(6) = 2 and A010846(6) = 5, hence 6 - 2 - 5 + 1 = 0.
a(3) = 5 since P(3) = 30; phi(30) = 8 and A010846(6) = 5, hence 30 - 8 - 18 + 1 = 5. We can also look at this as the cardinality of the set {1..30} \ ({1, 7, 11, 13, 17, 19, 23, 29} U {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30}) = {14, 21, 22, 26, 28}, therefore a(3) = 5.
Table relating a(n) to A002110(n), A363061(n), and A005867(n).
n A002110(n) A363061(n)      a(n) A005867(n)
--------------------------------------------
0         1          1         0          1
1         2          2         0          1
2         6          5         0          2
3        30         18         5          8
4       210         68        95         48
5      2310        283      1548        480
6     30030       1161     23110       5760
7    510510       4843    413508      92160
8   9699690      19985   8020826    1658880
...

Mathematica

b = Map[Last[ToExpression /@ StringSplit[#]] &, Split[Import["https://oeis.org/A363061/b363061.txt", "Data"]][[2 ;; -1, -1]]]; Array[(If[# == 0, Set[{k, p}, {1, 1}], p *= Prime[#]; k *= (Prime[#] - 1)]; p - k - b[[# + 1]] + 1) &, Length[b], 0]

Crossrefs

Cf. A000010, A002110, A005867, A243823, A363061.

Sequence in context: A275292 A362481 A359271 * A233077 A182960 A241998

Adjacent sequences: A363841 A363842 A363843 * A363845 A363846 A363847

Keyword

nonn,hard,changed

Author

Michael De Vlieger, Jun 23 2023

Status

approved