A049865 -id:A049865 - cp's OEIS frontend

A047994 Unitary totient (or unitary phi) function uphi(n).

1, 1, 2, 3, 4, 2, 6, 7, 8, 4, 10, 6, 12, 6, 8, 15, 16, 8, 18, 12, 12, 10, 22, 14, 24, 12, 26, 18, 28, 8, 30, 31, 20, 16, 24, 24, 36, 18, 24, 28, 40, 12, 42, 30, 32, 22, 46, 30, 48, 24, 32, 36, 52, 26, 40, 42, 36, 28, 58, 24, 60, 30, 48, 63, 48, 20, 66, 48, 44, 24, 70

Offset: 1

N. J. A. Sloane

A divisor d of n is called a unitary divisor if gcd(d, n/d) = 1. Define gcd*(k,n) to be the largest divisor d of k that is also a unitary divisor of n (that is, such that gcd(d, n/d) = 1). The unitary totient function a(n) = number of k with 1 <= k <= n such that gcd*(k,n) = 1. - N. J. A. Sloane, Aug 08 2021
Unitary convolution of A076479 and A000027. - R. J. Mathar, Apr 13 2011
Multiplicative with a(p^e) = p^e - 1. - N. J. A. Sloane, Apr 30 2013

			a(12) = a(3)*a(4) = 2*3 = 6.

T. D. Noe, Table of n, a(n) for n = 1..10000
Eckford Cohen, Arithmetical functions associated with the unitary divisors of an integer, Math. Zeitschr. 74 (1960) 66-80
Steven R. Finch, Unitarism and infinitarism.
Steven R. Finch, Unitarism and Infinitarism, February 25, 2004. [Cached copy, with permission of the author]
M. Lal, Iterates of the unitary totient function, Math. Comp., 28 (1974), 301-302.
R. J. Mathar, Survey of Dirichlet Series of Multiplicative Arithmetic Functions, arXiv:1106.4038 [math.NT], 2011, Remark 43.
László Tóth, On the Bi-Unitary Analogues of Euler's Arithmetical Function and the Gcd-Sum Function, JIS 12 (2009), Article 09.5.2.
László Tóth, A survey of gcd-sum functions, J. Int. Seq. 13 (2010), Article 10.8.1.

Cf. A000010, A000203, A001221, A003557, A049865, A003271, A028233, A076479.

a047994 n = f n 1 where
   f 1 uph = uph
   f x uph = f (x `div` sppf) (uph * (sppf - 1)) where sppf = a028233 x
-- Reinhard Zumkeller, Aug 17 2011

A047994 := proc(n)
    local a, f;
    a := 1 ;
    for f in ifactors(n)[2] do
        a := a*(op(1,f)^op(2,f)-1) ;
    end do:
    a ;
end proc:
seq(A047994(n),n=1..20) ; # R. J. Mathar, Dec 22 2011

uphi[n_] := (Times @@ (Table[ #[[1]]^ #[[2]] - 1, {1} ] & /@ FactorInteger[n]))[[1]]; Table[ uphi[n], {n, 2, 75}] (* Robert G. Wilson v, Sep 06 2004 *)
uphi[n_] := If[n==1, 1, Product[{p, e} = pe; p^e-1, {pe, FactorInteger[n]}] ]; Array[uphi, 80] (* Jean-François Alcover, Nov 17 2018 *)

A047994(n)=my(f=factor(n)~); prod(i=1, #f, f[1, i]^f[2, i]-1);

for(n=1, 100, print1(direuler(p=2, n, (1 - 2*X + p*X^2)/(1-X)/(1-p*X))[n], ", ")) \\ Vaclav Kotesovec, Jun 15 2020

from math import prod
from sympy import factorint
def A047994(n): return prod(p**e-1 for p, e in factorint(n).items()) # Chai Wah Wu, Sep 24 2021

If n = Product p_i^e_i, uphi(n) = Product (p_i^e_i - 1).
a(n) = A000010(n)*A000203(A003557(n))/A003557(n). - Velin Yanev and Charles R Greathouse IV, Aug 23 2017
From Amiram Eldar, May 29 2020: (Start)
a(n) = Sum_{d|n, gcd(d, n/d) = 1} (-1)^omega(d) * n/d.
Sum_{d|n, gcd(d, n/d) = 1} a(d) = n.
a(n) >= phi(n) = A000010(n), with equality if and only if n is squarefree (A005117). (End)
Sum_{k=1..n} a(k) ~ c * Pi^2 * n^2 / 12, where c = A065464 = Product_{primes p} (1 - 2/p^2 + 1/p^3). - Vaclav Kotesovec, Jun 15 2020
Dirichlet g.f.: zeta(s-1) * zeta(s) * Product_{p prime} (1 - 2/p^s + 1/p^(2*s-1)). - Amiram Eldar, May 22 2025

More terms from Jud McCranie

A003271 Smallest number that requires n iterations of the unitary totient function (A047994) to reach 1.

Original entry on oeis.org

1, 2, 3, 4, 5, 9, 16, 17, 41, 83, 113, 137, 257, 773, 977, 1657, 2048, 2313, 4001, 5725, 7129, 11117, 17279, 19897, 22409, 39283, 43657, 55457, 120677, 308941, 314521, 465089, 564353, 797931, 1110841, 1310443, 1924159, 2535041, 3637637, 6001937, 8319617, 9453569, 10969369

Offset: 0

N. J. A. Sloane

A049865(a(n)) = n and A049865(m) <> n for m < a(n). [Reinhard Zumkeller, Aug 17 2011]

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Donovan Johnson, Table of n, a(n) for n = 0..66 (terms < 10^10)
R. K. Guy, Letter to N. J. A. Sloane, Apr 1975
M. Lal, Iterates of the unitary totient function, Math. Comp., 28 (1974), 301-302.

Cf. A047994, A049865, A225172, A225173.

import Data.List (elemIndex)
import Data.Maybe (fromJust)
a003271 n = a003271_list !! n
a003271_list = map ((+ 1) . fromJust . (`elemIndex` a049865_list)) [0..]
-- Reinhard Zumkeller, Aug 17 2011

uphi[n_ /; n <= 1] = 1; uphi[n_] := uphi[n] = (f = FactorInteger[n]; Times @@ (f[[All, 1]]^f[[All, 2]] - 1));
b[n_] := (k = 0; FixedPoint[(k++; uphi[#])&, n]; k - 1);
a[0] = 1; a[n_] := a[n] = For[an = a[n-1], True, an++, If[b[an] == n, Return[an]]];
Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 0, 42}] (* Jean-François Alcover, Oct 05 2017 *)

More terms from David W. Wilson

A225172 Largest number which requires n iterations of the unitary totient function (A047994) to reach 1.

Original entry on oeis.org

1, 2, 6, 14, 42, 86, 186, 462, 930, 1986, 4170, 6510, 14682, 29366, 50342, 73410, 189498, 287654, 491190, 849570, 1699142, 2433878, 4280774, 7978218, 14442690, 25900142, 44400390, 78492954, 123958794, 228018066, 355388970, 629582370, 780686294

Offset: 0

N. J. A. Sloane, May 01 2013

nonn

Searched up to 10^10. a(33) >= 1609056138. a(34) >= 2275537110. a(35) >= 4171607222. - Donovan Johnson, May 02 2013

M. Lal, Iterates of the unitary totient function, Math. Comp., 28 (1974), 301-302.

Cf. A047994, A003271, A225173.

(* This is just a verification of recorded data up to a(23), assuming a(n-1)/2 <= a(n) <= 4*a(n-1) *) uphi[n_] := (cnt++; fi = FactorInteger[n]; Times @@ (fi[[All, 1]]^fi[[All, 2]] - 1)); f[n_] := (cnt = 0; NestWhile[uphi, n, # > 1 &]; cnt); a[0] = 1; a[1] = 2; a[n_] := a[n] = (For[record = k = a[n-1]/2//Floor, k <= 4*a[n-1], k++, If[f[k] == n, record = k]]; record); Table[Print[a[n]]; a[n], {n, 0, 23}] (* Jean-François Alcover, May 02 2013 *)

a(n) = max{x : A049865(x) = n}. - R. J. Mathar, May 02 2013

a(16)-a(32) from Donovan Johnson, May 02 2013

A333609 The number of iterations of the infinitary totient function iphi (A091732) required to reach from n to 1.

Original entry on oeis.org

0, 1, 2, 3, 4, 2, 3, 3, 4, 4, 5, 3, 4, 3, 4, 5, 6, 4, 5, 4, 4, 5, 6, 3, 4, 4, 6, 5, 6, 4, 5, 5, 5, 6, 4, 4, 5, 5, 4, 4, 5, 4, 5, 5, 6, 6, 7, 5, 6, 4, 6, 5, 6, 6, 5, 5, 5, 6, 7, 4, 5, 5, 6, 7, 6, 5, 6, 6, 6, 4, 5, 4, 5, 5, 6, 7, 5, 4, 5, 5, 6, 5, 6, 5, 8, 5, 6

Offset: 1

Amiram Eldar, Mar 28 2020

nonn

			a(6) = 2 since there are 2 iterations from 6 to 1: iphi(6) = 2 and iphi(2) = 1.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A003434, A049865, A091732.

f[p_, e_] := p^(2^(-1 + Position[Reverse @ IntegerDigits[e, 2], 1])); iphi[1] = 1; iphi[n_] := Times @@ (Flatten@(f @@@ FactorInteger[n]) - 1); a[n_] := Length @ NestWhileList[iphi, n, # != 1 &] - 1; Array[a, 100]

A329153 Sum of the iterated unitary totient function (A047994).

Original entry on oeis.org

0, 1, 3, 6, 10, 3, 9, 16, 24, 10, 20, 9, 21, 9, 24, 39, 55, 24, 42, 21, 21, 20, 42, 23, 47, 21, 47, 42, 70, 24, 54, 85, 41, 55, 47, 47, 83, 42, 47, 70, 110, 21, 63, 54, 117, 42, 88, 54, 102, 47, 117, 83, 135, 47, 110, 63, 83, 70, 128, 47, 107, 54, 102, 165, 102

Offset: 1

Amiram Eldar, Feb 25 2020

nonn

Analogous to A092693 with the unitary totient function uphi instead of the Euler totient function phi (A000010).

			a(4) = uphi(4) + uphi(uphi(4)) + uphi(uphi(uphi(4))) = 3 + 2 + 1 = 6.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A003271, A047994, A049865, A092693, A225172, A225173, A286067.

uphi[1] = 1; uphi[n_] := Times @@ (-1 + Power @@@ FactorInteger[n]); Table[Plus @@ FixedPointList[uphi, n] - n - 1, {n, 1, 100}]

a(n) = n for n in A286067.

A385744 The number of iterations of the infinitary analog of the totient function A384247 that are required to reach from n to 1.

Original entry on oeis.org

0, 1, 2, 3, 4, 2, 3, 4, 5, 4, 5, 3, 4, 3, 5, 6, 7, 5, 6, 4, 4, 5, 6, 5, 6, 4, 6, 6, 7, 5, 6, 7, 5, 7, 6, 6, 7, 6, 6, 7, 8, 4, 5, 6, 8, 6, 7, 6, 7, 6, 8, 7, 8, 6, 8, 6, 7, 7, 8, 6, 7, 6, 7, 7, 7, 5, 6, 7, 7, 6, 7, 8, 9, 7, 7, 7, 7, 6, 7, 7, 8, 8, 9, 7, 8, 5, 7

Offset: 1

Amiram Eldar, Jul 08 2025

First differs from A049865 at n = 24.

			  n | a(n) | iterations
  --+------+----------------------
  2 |    1 | 2 -> 1
  3 |    2 | 3 -> 2 -> 1
  4 |    3 | 4 -> 3 -> 2 -> 1
  5 |    4 | 5 -> 4 -> 3 -> 2 -> 1
  6 |    2 | 6 -> 2 -> 1

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A384247, A385745, A385746, A385747.

Similar sequences: A003434, A049865, A225320, A333609.

f[p_, e_] := p^e*(1 - 1/p^(2^(IntegerExponent[e, 2]))); iphi[1] = 1; iphi[n_] := iphi[n] = Times @@ f @@@ FactorInteger[n];
a[n_] := Length @ NestWhileList[iphi, n, # != 1 &] - 1; Array[a, 100]

iphi(n) = {my(f = factor(n)); n * prod(i = 1, #f~, (1 - 1/f[i, 1]^(1 << valuation(f[i, 2], 2))));}
a(n) = if(n ==  1, 0, 1 + a(iphi(n)));

a(n) = a(A384247(n)) + 1 for n >= 2.

A362024 The number of iterations of the infinitary totient function iphi (A064380) required to reach from n to 1.

Original entry on oeis.org

1, 2, 3, 4, 3, 4, 4, 5, 5, 6, 5, 6, 5, 6, 7, 8, 7, 8, 7, 6, 6, 7, 6, 7, 8, 8, 9, 10, 7, 8, 8, 7, 7, 8, 9, 10, 7, 9, 8, 9, 9, 10, 9, 8, 11, 12, 8, 9, 9, 10, 10, 11, 7, 10, 9, 9, 11, 12, 8, 9, 9, 10, 9, 10, 8, 9, 11, 10, 9, 10, 8, 9, 9, 8, 10, 10, 10, 11, 11, 12

Offset: 2

Amiram Eldar, Apr 05 2023

nonn

			a(6) = 3 since there are 3 iterations from 6 to 1: iphi(6) = 3, iphi(3) = 2 and iphi(2) = 1.

Amiram Eldar, Table of n, a(n) for n = 2..10000

Cf. A064380, A362025 (indices of records).

Similar sequences: A003434, A049865, A333609.

infCoprimeQ[n1_, n2_] := Module[{g = GCD[n1, n2]}, If[g == 1, True, AllTrue[FactorInteger[g][[;; , 1]], BitAnd @@ IntegerExponent[{n1, n2}, #] == 0 &]]];
iphi[n_] := Sum[Boole[infCoprimeQ[j, n]], {j, 1, n - 1}];
a[n_] := Length@ NestWhileList[iphi, n, # > 1 &] - 1;
Array[a, 100, 2]

isinfcoprime(n1, n2) = {my(g = gcd(n1, n2), p, e1, e2); if(g == 1, return(1)); p = factor(g)[, 1]; for(i=1, #p, e1 = valuation(n1, p[i]); e2 = valuation(n2, p[i]); if(bitand(e1, e2) > 0, return(0))); 1; }
iphi(n) = sum(j = 1, n-1, isinfcoprime(j, n));
a(n) = if(n==2, 1, a(iphi(n)) + 1);

a(n) = a(A064380(n)) + 1 for n > 2.

cp's OEIS Frontend

A047994 Unitary totient (or unitary phi) function uphi(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A003271 Smallest number that requires n iterations of the unitary totient function (A047994) to reach 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

Extensions

A225172 Largest number which requires n iterations of the unitary totient function (A047994) to reach 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A333609 The number of iterations of the infinitary totient function iphi (A091732) required to reach from n to 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A329153 Sum of the iterated unitary totient function (A047994).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A385744 The number of iterations of the infinitary analog of the totient function A384247 that are required to reach from n to 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A362024 The number of iterations of the infinitary totient function iphi (A064380) required to reach from n to 1.

Views

Author

Keywords

Examples

Links

Crossrefs