login
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

%I #9 Jul 17 2024 08:58:08

%S 0,0,0,5,95,1548,23110,413508,8020826,186514437,5447473481,

%T 169902931273,6317112341154,260105450523376,11228680152402376,

%U 529602052783103298,28154196548377380922,1665532558381753842459,101854713853486313230170,6839699495691464491151135,486637286249491454965285898

%N 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).

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

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

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

%e a(0) = 0 since P(0) = 1; phi(1) = 1 and A010846(1) = 1, hence 1 - 1 - 1 + 1 = 0.

%e a(1) = 0 since P(1) = 2; phi(2) = 1 and A010846(2) = 2, hence 2 - 1 - 2 + 1 = 0.

%e a(2) = 0 since P(2) = 6; phi(6) = 2 and A010846(6) = 5, hence 6 - 2 - 5 + 1 = 0.

%e 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.

%e Table relating a(n) to A002110(n), A363061(n), and A005867(n).

%e n A002110(n) A363061(n) a(n) A005867(n)

%e --------------------------------------------

%e 0 1 1 0 1

%e 1 2 2 0 1

%e 2 6 5 0 2

%e 3 30 18 5 8

%e 4 210 68 95 48

%e 5 2310 283 1548 480

%e 6 30030 1161 23110 5760

%e 7 510510 4843 413508 92160

%e 8 9699690 19985 8020826 1658880

%e ...

%t 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]

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

%K nonn,hard

%O 0,4

%A _Michael De Vlieger_, Jun 23 2023