cp's OEIS Frontend

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

%I A363844 #9 Jul 17 2024 08:58:08
%S A363844 0,0,0,5,95,1548,23110,413508,8020826,186514437,5447473481,
%T A363844 169902931273,6317112341154,260105450523376,11228680152402376,
%U A363844 529602052783103298,28154196548377380922,1665532558381753842459,101854713853486313230170,6839699495691464491151135,486637286249491454965285898
%N 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).
%F A363844 a(n) = A243823(A002110(n)).
%F A363844 a(n) = P(n) - A000010(P(n)) - A010846(P(n)) + 1, where P(n) = A002110(n).
%F A363844 a(n) = A002110(n) - A005867(n) - A363061(n) + 1.
%e A363844 a(0) = 0 since P(0) = 1; phi(1) = 1 and A010846(1) = 1, hence 1 - 1 - 1 + 1 = 0.
%e A363844 a(1) = 0 since P(1) = 2; phi(2) = 1 and A010846(2) = 2, hence 2 - 1 - 2 + 1 = 0.
%e A363844 a(2) = 0 since P(2) = 6; phi(6) = 2 and A010846(6) = 5, hence 6 - 2 - 5 + 1 = 0.
%e A363844 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 A363844 Table relating a(n) to A002110(n), A363061(n), and A005867(n).
%e A363844 n A002110(n) A363061(n)      a(n) A005867(n)
%e A363844 --------------------------------------------
%e A363844 0         1          1         0          1
%e A363844 1         2          2         0          1
%e A363844 2         6          5         0          2
%e A363844 3        30         18         5          8
%e A363844 4       210         68        95         48
%e A363844 5      2310        283      1548        480
%e A363844 6     30030       1161     23110       5760
%e A363844 7    510510       4843    413508      92160
%e A363844 8   9699690      19985   8020826    1658880
%e A363844 ...
%t A363844 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 A363844 Cf. A000010, A002110, A005867, A243823, A363061.
%K A363844 nonn,hard
%O A363844 0,4
%A A363844 _Michael De Vlieger_, Jun 23 2023