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

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, 28, 8, 30, 15, 20, 16, 24, 24, 36, 18, 24, 12, 40, 12, 42, 30, 32, 22, 46, 30, 48, 24, 32, 36, 52, 16, 40, 18, 36, 28, 58, 24, 60, 30, 48, 45, 48, 20, 66, 48, 44, 24, 70, 24, 72, 36, 48

Offset: 1

Author

Steven Finch, Mar 05 2004

Keywords

• nonn
• mult

Comments

Not the same as A064380.

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

Examples

			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.
12=3*4 (3,4 are in A050376). Therefore, a(12) = 12*(1-1/3)*(1-1/4) = 6. - _Vladimir Shevelev_, Feb 20 2011
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..21011
• Graeme L. Cohen and Peter Hagis, Arithmetic functions associated with the infinitary divisors of an integer, Internat. J. Math. Math. Sci. 16 (1993) 373-383.
• Steven R. Finch, Unitarism and infinitarism, 2004.
• Steven R. Finch, Unitarism and Infinitarism, February 25, 2004. [Cached copy, with permission of the author]
• Antti Karttunen, Data supplement: n, a(n) computed for n = 1..100000

Crossrefs

Cf. A037445, A049417, A050376, A064380, A300841, A323413.

Programs

Maple

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:
seq(A091732(n),n=1..20) ; # R. J. Mathar, Apr 11 2011

Mathematica

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

PARI

ispow2(n) = (n && !bitand(n,n-1));
A302777(n) = ispow2(isprimepower(n));
A091732(n) = { my(m=1); while(n > 1, fordiv(n, d, if((dA302777(n/d), m *= ((n/d)-1); n = d; break))); (m); }; \\ Antti Karttunen, Jan 15 2019

Formula

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

From Vladimir Shevelev, Feb 20 2011: (Start)

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.

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

a(n) = n - A323413(n). - Antti Karttunen, Jan 15 2019

a(n) <= A064380(n), with equality if and only if n is in A050376. - Amiram Eldar, Feb 18 2023