cp's OEIS Frontend

A091732 Iphi(n): infinitary analog of Euler's phi function.

%I A091732 #57 Aug 06 2024 09:33:58
%S A091732 1,1,2,3,4,2,6,3,8,4,10,6,12,6,8,15,16,8,18,12,12,10,22,6,24,12,16,18,
%T A091732 28,8,30,15,20,16,24,24,36,18,24,12,40,12,42,30,32,22,46,30,48,24,32,
%U A091732 36,52,16,40,18,36,28,58,24,60,30,48,45,48,20,66,48,44,24,70,24,72,36,48
%N A091732 Iphi(n): infinitary analog of Euler's phi function.
%C A091732 Not the same as A064380.
%C A091732 With n having a unique factorization as A050376(i) * A050376(j) * ... * A050376(k), with i, j, ..., k all distinct, a(n) = (A050376(i)-1) * (A050376(j)-1) * ... * (A050376(k)-1). (Cf. the first formula). - _Antti Karttunen_, Jan 15 2019
%H A091732 Antti Karttunen, <a href="/A091732/b091732.txt">Table of n, a(n) for n = 1..21011</a>
%H A091732 Graeme L. Cohen and Peter Hagis, <a href="http://dx.doi.org/10.1155/S0161171293000456">Arithmetic functions associated with the infinitary divisors of an integer</a>, Internat. J. Math. Math. Sci. 16 (1993) 373-383.
%H A091732 Steven R. Finch, <a href="https://citeseerx.ist.psu.edu/pdf/84155bde29ec97c3bd83370f09b7709441c409d3">Unitarism and infinitarism</a>, 2004.
%H A091732 Steven R. Finch, <a href="/A007947/a007947.pdf">Unitarism and Infinitarism</a>, February 25, 2004. [Cached copy, with permission of the author]
%H A091732 Antti Karttunen, <a href="/A091732/a091732.txt">Data supplement: n, a(n) computed for n = 1..100000</a>
%F A091732 Consider the set, I, of integers of the form p^(2^j), where p is any prime and j >= 0. Let n > 1. From the fundamental theorem of arithmetic and the fact that the binary representation of any integer is unique, it follows that n can be uniquely factored as a product of distinct elements of I. If n = P_1*P_2*...*P_t, where each P_j is in I, then iphi(n) = Product_{j=1..t} (P_j - 1).
%F A091732 From _Vladimir Shevelev_, Feb 20 2011: (Start)
%F A091732 Thus we have the following analog of the formula phi(n) = n*Product_{p prime divisors of n} (1-1/p): if the factorization of n over distinct terms of A050376 is n = Product(q) (this factorization is unique), then a(n) = n*Product(1-1/q). Thus a(n) is infinitary multiplicative, i.e., if n_1 and n_2 have no common i-divisors, then a(n_1*n_2) = a(n_1)*a(n_2). Now we see that this property is stronger than the usual multiplicativity, therefore a(n) is a multiplicative arithmetic function.
%F A091732 Add that Sum_{d runs i-divisors of n} a(d)=n and a(n) = n*Sum_{d runs i-divisors of n} A064179(d)/d. The latter formulas are analogs of the corresponding formulas for phi(n): Sum_{d|n} phi(d) = n and phi(n) = n*Sum_{d|n} mu(d)/d. (End).
%F A091732 a(n) = n - A323413(n). - _Antti Karttunen_, Jan 15 2019
%F A091732 a(n) <= A064380(n), with equality if and only if n is in A050376. - _Amiram Eldar_, Feb 18 2023
%e A091732 a(6)=2 since 6=P_1*P_2, where P_1=2^(2^0) and P_2=3^(2^0); hence (P_1-1)*(P_2-1)=2.
%e A091732 12=3*4 (3,4 are in A050376). Therefore, a(12) = 12*(1-1/3)*(1-1/4) = 6. - _Vladimir Shevelev_, Feb 20 2011
%p A091732 A091732 := proc(n) local f,a,e,p,b; a :=1 ; for f in ifactors(n)[2] do e := op(2,f) ; p := op(1,f) ; b := convert(e,base,2) ; for i from 1 to nops(b) do if op(i,b) > 0 then a := a*(p^(2^(i-1))-1) ; end if; end do: end do: a ; end proc:
%p A091732 seq(A091732(n),n=1..20) ; # _R. J. Mathar_, Apr 11 2011
%t A091732 f[p_, e_] := p^(2^(-1 + Position[Reverse @ IntegerDigits[e, 2], 1])); a[1] = 1; a[n_] := Times @@ (Flatten@(f @@@ FactorInteger[n]) - 1); Array[a, 100] (* _Amiram Eldar_, Feb 28 2020 *)
%o A091732 (PARI)
%o A091732 ispow2(n) = (n && !bitand(n,n-1));
%o A091732 A302777(n) = ispow2(isprimepower(n));
%o A091732 A091732(n) = { my(m=1); while(n > 1, fordiv(n, d, if((d<n)&&A302777(n/d), m *= ((n/d)-1); n = d; break))); (m); }; \\ _Antti Karttunen_, Jan 15 2019
%Y A091732 Cf. A037445, A049417, A050376, A064380, A300841, A323413.
%K A091732 nonn,mult
%O A091732 1,3
%A A091732 _Steven Finch_, Mar 05 2004