A047994 -id:A047994 - cp's OEIS frontend

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

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

A361966 Irregular table read by rows in which the n-th row consists of all the numbers m such that uphi(m) = n, where uphi is the unitary totient function (A047994).

Original entry on oeis.org

1, 2, 3, 6, 4, 5, 10, 7, 12, 14, 8, 9, 15, 18, 30, 11, 22, 13, 20, 21, 26, 42, 24, 16, 17, 34, 19, 28, 38, 33, 66, 23, 46, 25, 35, 36, 39, 50, 60, 70, 78, 27, 54, 29, 40, 58, 31, 44, 48, 62, 32, 45, 51, 90, 102, 37, 52, 57, 74, 84, 114, 41, 55, 82, 110, 43, 56, 86

Offset: 1

Amiram Eldar, Apr 01 2023

			The table begins:
  n   n-th row
  --  --------
   1  1, 2;
   2  3, 6;
   3  4;
   4  5, 10;
   5
   6  7, 12, 14;
   7  8;
   8  9, 15, 18, 30;
   9
  10  11, 22;
  11
  12  13, 20, 21, 26, 42;

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

The unitary version of A032447.

Cf. A047994, A135347, A162247, A361967 (row lengths), A361968, A361969, A361970, A361971.

invUPhi[n_] := Module[{fct = f[n], sol}, sol = Times @@@ (1 + Select[fct, UnsameQ @@ # && (Length[#] == 1 || CoprimeQ @@ (# + 1)) && Times @@ PrimeNu[# + 1] == 1 &]); Sort@ Join[sol, 2*Select[sol, OddQ]]]; invUPhi[1] = {1, 2}; Table[invUPhi[n], {n, 1, 50}] // Flatten (* using the function f by T. D. Noe at A162247 *)

A287055 Numbers n such that uphi(n) = uphi(n+1), where uphi(n) is the unitary totient function (A047994).

Original entry on oeis.org

1, 20, 35, 143, 194, 208, 740, 1119, 1220, 1299, 1419, 1803, 1892, 2232, 2623, 3705, 3716, 3843, 4995, 5031, 5183, 5186, 5635, 7868, 10659, 17948, 18507, 18914, 21007, 23616, 25388, 25545, 30380, 30744, 31599, 32304, 34595, 37820, 38024, 47067, 60767, 70394

Offset: 1

Amiram Eldar, May 18 2017

nonn

The unitary version of A001274 (phi(n) = phi(n+1)). The first terms that are common to both sequences are: 1, 194, 3705, 5186, 25545, 388245, 1659585, 2200694, 2521694, 2619705, 3289934, 4002405, 5781434, 6245546, 6372794, 8338394.

			uphi(20) = uphi(21) = 12, thus 20 is in the sequence.

Chai Wah Wu, Table of n, a(n) for n = 1..2198 (terms 1..207 from Amiram Eldar)

Cf. A001274, A047994.

uphi[n_] := If[n==1,1,(Times @@ (Table[#[[1]]^#[[2]] - 1, {1}] & /@ FactorInteger[n]))[[1]]]; a={}; u1=0; For[k=0, k<10^5, k++; u2=uphi[k]; If[u1==u2, a = AppendTo[a, k-1]]; u1=u2]; a

uphi(n) = my(f = factor(n)); prod(i=1, #f~, f[i,1]^f[i,2]-1);
isok(n) = uphi(n+1) == uphi(n); \\ Michel Marcus, May 20 2017

from math import prod
from sympy import factorint
A287055_list, a, n = [], 1, 1
while n < 10**5:
    b = prod(p**e-1 for p, e in factorint(n+1).items())
    if a == b:
        A287055_list.append(n)
    a, n = b, n+1 # Chai Wah Wu, Sep 24 2021

A323410 Unitary analog of cototient function A051953: a(n) = n - A047994(n).

Original entry on oeis.org

0, 1, 1, 1, 1, 4, 1, 1, 1, 6, 1, 6, 1, 8, 7, 1, 1, 10, 1, 8, 9, 12, 1, 10, 1, 14, 1, 10, 1, 22, 1, 1, 13, 18, 11, 12, 1, 20, 15, 12, 1, 30, 1, 14, 13, 24, 1, 18, 1, 26, 19, 16, 1, 28, 15, 14, 21, 30, 1, 36, 1, 32, 15, 1, 17, 46, 1, 20, 25, 46, 1, 16, 1, 38, 27, 22, 17, 54, 1, 20, 1, 42, 1, 48, 21, 44, 31, 18, 1, 58, 19, 26, 33, 48

Offset: 1

Antti Karttunen, Jan 15 2019

Antti Karttunen, Table of n, a(n) for n = 1..21210
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..100000

Cf. A047994, A065463.

Cf. also A034460, A051953, A323409, A323413.

a[n_] := n - Times @@ (Power @@@ FactorInteger[n] - 1); a[1] = 0; Array[a, 100] (* Amiram Eldar, Apr 08 2023 *)

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

a(n) = n - A047994(n), where A047994 is unitary phi.

Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = 1 - A065463 = 0.2955577... . - Amiram Eldar, Dec 15 2023

A030163 Solutions x of 2*uphi(x)=x, where uphi is the unitary phi function (A047994).

Original entry on oeis.org

2, 12, 168, 240, 14880, 65280, 4294901760, 7608944640, 1125874137169920, 18446744069414584320

Offset: 1

Yasutoshi Kohmoto

Tomohiro Yamada, An analog of perfect numbers involving the unitary totient function, arXiv:1806.00647 [math.NT], 2018.

Cf. A047994.

uphi(n) = my(f=factor(n)~); prod(i=1, #f, f[1, i]^f[2, i]-1);
isok(n) = uphi(n) == n/2; \\ Michel Marcus, Feb 13 2018

solve_uphi(N, D, limit) = {my(g,f,uphi,sol,p,n,pn,uphipn,tmp,ll); sol = [];g = gcd(N, D); N /= g; D /= g; if (D==1, if (N==1, sol = [1]);sol;, f = factor(D); uphi = prod(i=1, #f~, f[i, 1]^f[i, 2]-1); if (uphi(x <= limit), vecsort(sol,,8));}
solve_uphi(1, 2, 10^20) \\ Michel Marcus, Jun 07 2018

Corrected offset and keyword more by Michel Marcus, Feb 13 2018

A361967 Number of numbers k such that uphi(k) = n, where uphi is the unitary totient function (A047994).

Original entry on oeis.org

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

Offset: 1

Amiram Eldar, Apr 01 2023

nonn

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

Row lengths of A361966.
The unitary version of A014197.
Cf. A047994, A135347, A327837, A347771 (positions of 0's), A361966, A361968 (indices of records), A361969 (positions of 1's), A361970, A361971 (record values).

a[n_] := Length[invUPhi[n]]; Array[a, 100] (* using the function invUPhi from A361966 *)

a(A347771(n)) = 0.
a(A361969(n)) = 1.
a(A361970(n)) = n.
Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = A327837. - Amiram Eldar, Dec 24 2024

A177754 Partial sums of A047994.

Original entry on oeis.org

1, 2, 4, 7, 11, 13, 19, 26, 34, 38, 48, 54, 66, 72, 80, 95, 111, 119, 137, 149, 161, 171, 193, 207, 231, 243, 269, 287, 315, 323, 353, 384, 404, 420, 444, 468, 504, 522, 546, 574, 614, 626, 668, 698, 730, 752, 798, 828, 876, 900, 932, 968, 1020, 1046, 1086

Offset: 1

Jonathan Vos Post, May 12 2010

Partial sums of unitary totient (or unitary phi) function uphi(n). This is to A047994 as A002088 is to A000010. The subsequence of primes in the partial sum begins: 2, 7, 11, 13, 19, 137, 149, 193, 269, 353, 1523, 1543, 1609, 1657.

			a(7) = 1 + 1 + 2 + 3 + 4 + 2 + 6 = 19.

Eckford Cohen, Arithmetical functions associated with the unitary divisors of an integer, Mathematische Zeitschrift, Vol. 74, No. 1 (1960), pp. 66-80.
R. Sitaramachandrarao and D. Suryanarayana, On Sum_{n<=x} sigma*(n) and Sum_{n<=x} phi*(n), Proceedings of the American Mathematical Society, Vol. 41, No. 1 (1973), pp. 61-66.

Cf. A000010, A002088, A003271, A047994, A065463.

uphi[1] = 1; uphi[n_] := Times @@ (-1 + Power @@@ FactorInteger[n]); s = 0; Accumulate[Array[uphi, 60]] (* Amiram Eldar, Dec 18 2018*)

a(n) = Sum_{i=1..n} A047994(i).

a(n) ~ alpha * n^2/2 + O(n*log^2(n)) where alpha = Product_{p prime} (1 - 1/(p*(p+1))) = 0.704442... (A065463). - Amiram Eldar, Dec 18 2018

A348004 Numbers whose unitary divisors have distinct values of the unitary totient function uphi (A047994).

Original entry on oeis.org

1, 3, 4, 5, 7, 8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 21, 23, 24, 25, 27, 28, 29, 31, 32, 33, 35, 36, 37, 39, 40, 41, 43, 44, 45, 47, 48, 49, 51, 52, 53, 55, 56, 57, 59, 60, 61, 63, 64, 65, 67, 68, 69, 71, 72, 73, 75, 76, 77, 79, 80, 81, 83, 85, 87, 88, 89, 91

Offset: 1

Amiram Eldar, Sep 23 2021

nonn

First differs from A042965 \ {0} at n=63, and from A122906 at n=53.
Since Sum_{d|k, gcd(d,k/d)=1} uphi(d) = k, these are numbers k such that the set {uphi(d) | d|k, gcd(d,k/d)=1} is a partition of k into distinct parts.
Includes all the odd prime powers (A061345), since an odd prime power p^e has 2 unitary divisors, 1 and p^e, whose uphi values are 1 and p^e - 1. It also includes all the powers of 2, except for 2 (A151821).
If k is a term, then all the unitary divisors of k are also terms.
The number of terms not exceeding 10^k for k = 1, 2, ... are 7, 74, 741, 7386, 73798, 737570, 7374534, 73740561, 737389031, 7373830133, ... Apparently, this sequence has an asymptotic density 0.73738...

			4 is a term since it has 2 unitary divisors, 1 and 4, and uphi(1) = 1 != uphi(4) = 3.
12 is a term since the uphi values of its unitary divisors, {1, 3, 4, 12}, are distinct: {1, 2, 3, 6}.

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

The unitary version of A326835.

Cf. A034444, A042965, A047994, A061345, A151821, A122906, A348001.

f[p_, e_] := p^e - 1; uphi[1] = 1; uphi[n_] := Times @@ f @@@ FactorInteger[n]; q[n_] := Length @ Union[uphi /@ (d = Select[Divisors[n], CoprimeQ[#, n/#] &])] == Length[d]; Select[Range[100], q]

from math import prod
from sympy.ntheory.factor_ import udivisors, factorint
A348004_list = []
for n in range(1,10**3):
    pset = set()
    for d in udivisors(n,generator=True):
        u = prod(p**e-1 for p, e in factorint(d).items())
        if u in pset:
            break
        pset.add(u)
    else:
        A348004_list.append(n) # Chai Wah Wu, Sep 24 2021

Numbers k such that A348001(k) = A034444(k).

A049865 Number of iterations of unitary totient function (A047994) required to reach 1 from n.

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, 4, 5, 4, 5, 6, 7, 5, 6, 7, 5, 7, 5, 5, 6, 6, 5, 7, 8, 4, 5, 6, 8, 6, 7, 6, 7, 5, 8, 6, 7, 5, 8, 5, 6, 7, 8, 5, 6, 6, 7, 8, 7, 5, 6, 7, 7, 5, 6, 6, 7, 6, 7, 6, 6, 5, 6, 6, 7, 8, 9, 6, 9, 5, 6, 6, 7, 8, 7, 6, 6, 7, 7, 7, 8, 7, 7, 7, 8, 8, 9, 7, 7, 7, 8, 6, 7, 8, 7

Offset: 1

David W. Wilson

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

T. D. Noe, Table of n, a(n) for n = 1..10000

a049865 n = length $ takeWhile (> 1) $ iterate a047994 n
a049865_list = map a049865 [1..]
-- Reinhard Zumkeller, Aug 17 2011

A049865 := proc(n)
    if n = 1 then
        0 ;
    else
        1+procname( A047994(n)) ;
    end if;
end proc: # R. J. Mathar, May 02 2013

uphi[n_] := (f = FactorInteger[n]; Times @@ (f[[All, 1]]^f[[All, 2]] - 1)); uphi[n_ /; n <= 1] = 1; a[n_] := (k = 0; FixedPoint[ (k++; uphi[#]) & , n]; k-1); Table[a[n], {n, 1, 120}] (* Jean-François Alcover, Jan 20 2012 *)

A135347 An inverse of the unitary totient function A047994.

Original entry on oeis.org

1, 3, 4, 5, -1, 7, 8, 9, -1, 11, -1, 13, -1, 24, 16, 17, -1, 19, -1, 33, -1, 23, -1, 25, -1, 27, -1, 29, -1, 31, 32, 45, -1, -1, -1, 37, -1, -1, -1, 41, -1, 43, -1, 69, -1, 47, -1, 49, -1, -1, -1, 53, -1, 76, -1, 72, -1, 59, -1, 61, -1, 96, 64, 85, -1, 67, -1, -1, -1, 71, -1, 73, -1, -1, -1, -1, -1, 79, -1, 81, -1, 83, -1, 104, -1, -1, -1

Offset: 1

R. J. Mathar, Dec 07 2007

sign

a(n) is the smallest m such that A047994(m)=n, or -1 if this m does not exist. Proof of nonexistence may be done by transversing all A045778(n) factorizations of n, increasing each factor in these factorizations by 1 and showing that none of these modified products is a product of powers of distinct primes.

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

Cf. A047994, A045778, A361966.

a[n_] := Module[{v = invUPhi[n]}, If[v == {}, -1, v[[1]]]]; Array[a, 100] (* Amiram Eldar, Apr 01 2023, using the function invUPhi from A361966 *)

cp's OEIS Frontend

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

A361966 Irregular table read by rows in which the n-th row consists of all the numbers m such that uphi(m) = n, where uphi is the unitary totient function (A047994).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A287055 Numbers n such that uphi(n) = uphi(n+1), where uphi(n) is the unitary totient function (A047994).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

A323410 Unitary analog of cototient function A051953: a(n) = n - A047994(n).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A030163 Solutions x of 2*uphi(x)=x, where uphi is the unitary phi function (A047994).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

Extensions

A361967 Number of numbers k such that uphi(k) = n, where uphi is the unitary totient function (A047994).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A177754 Partial sums of A047994.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A348004 Numbers whose unitary divisors have distinct values of the unitary totient function uphi (A047994).

Views

Author

Keywords

Comments

Examples