cp's OEIS Frontend

A322582 a(n) = n - A003958(n), where A003958 is fully multiplicative with a(p) = (p-1).

%I A322582 #30 Feb 18 2023 21:19:19
%S A322582 0,1,1,3,1,4,1,7,5,6,1,10,1,8,7,15,1,14,1,16,9,12,1,22,9,14,19,22,1,
%T A322582 22,1,31,13,18,11,32,1,20,15,36,1,30,1,34,29,24,1,46,13,34,19,40,1,46,
%U A322582 15,50,21,30,1,52,1,32,39,63,17,46,1,52,25,46,1,68,1,38,43,58,17,54,1,76,65,42,1,72,21,44,31,78,1
%N A322582 a(n) = n - A003958(n), where A003958 is fully multiplicative with a(p) = (p-1).
%C A322582 a(p*(n/p)) - (n/p) = (p-1)*a(n/p) holds for all prime divisors p of n, which can be seen by expanding the left hand side as p*(n/p) - A003958(p*(n/p)) - (n/p) = (p-1)*(n/p) - (p-1)*A003958(n/p) = (p-1)*((n/p) - A003958(n/p)) = (p-1)*a(n/p). This shows that this sequence gives a lower limit for arithmetic derivative (A003415) in the same way as A348507 gives an upper limit for it. - _Antti Karttunen_, Nov 07 2021
%C A322582 With n = Product_{i=1..k} p_i the prime factorization of n, if one constructs for each i a test with a probability of success equal to 1/p_i, and if the tests are independent, then a(n)/n is the probability that at least one of the k tests succeeds. - _Luc Rousseau_, Jan 14 2023
%H A322582 Antti Karttunen, <a href="/A322582/b322582.txt">Table of n, a(n) for n = 1..16384</a>
%F A322582 a(n) = n - A003958(n).
%F A322582 From _Antti Karttunen_, Nov 07 2021: (Start)
%F A322582 a(n) = A003415(n) - A348975(n).
%F A322582 For all n >= 1, a(n) <= A003415(n) <= A348507(n).
%F A322582 For n > 1, a(n) = a(A032742(n))*(A020639(n)-1) + A032742(n). [See the comment above and compare with _Reinhard Zumkeller_'s May 09 2011 formula for A003415]
%F A322582 (End)
%t A322582 a[1] = 0; a[n_] := n - Times @@ ((First[#] - 1)^Last[#] & /@ FactorInteger[n]); Array[a, 60] (* _Amiram Eldar_, Dec 17 2018 *)
%o A322582 (PARI)
%o A322582 A003958(n) = { my(f = factor(n)); for(i=1, #f~, f[i, 1]--); factorback(f); };
%o A322582 A322582(n) = (n-A003958(n));
%o A322582 (PARI)
%o A322582 A020639(n) = if(1==n, n, (factor(n)[1, 1]));
%o A322582 A322582(n) = { my(s=0, m=1, spf); while(n>1, spf = A020639(n); n /= spf; s += m*n; m *= (spf-1)); (s); }; \\ (Compare to the similar programs given in A003415 and A348507) - _Antti Karttunen_, Nov 07 2021
%Y A322582 Cf. A003415, A003958, A322581, A348507, A348928 [= gcd(n,a(n))], A348975 (difference from the arithmetic derivative).
%Y A322582 Cf. A349139, A348980, A348981, A348982, A348983 (Dirichlet convolutions with other sequences).
%Y A322582 Cf. A168065 (gives the arithmetic mean of this and A348507), A168066.
%K A322582 nonn
%O A322582 1,4
%A A322582 _Antti Karttunen_, Dec 17 2018