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,3

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

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

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

Example

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

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

Prog

(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((d<n)&&A302777(n/d), m *= ((n/d)-1); n = d; break))); (m); }; \\ Antti Karttunen, Jan 15 2019

Crossrefs

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

Sequence in context: A117744 A366481 A361697 * A299439 A109746 A286365

Adjacent sequences: A091729 A091730 A091731 * A091733 A091734 A091735

Keyword

nonn,mult

Author

Steven Finch, Mar 05 2004

Status

approved