A071181 -id:A071181 - cp's OEIS frontend

A066412 Number of elements in the set phi_inverse(phi(n)).

2, 2, 3, 3, 4, 3, 4, 4, 4, 4, 2, 4, 6, 4, 5, 5, 6, 4, 4, 5, 6, 2, 2, 5, 5, 6, 4, 6, 2, 5, 2, 6, 5, 6, 10, 6, 8, 4, 10, 6, 9, 6, 4, 5, 10, 2, 2, 6, 4, 5, 7, 10, 2, 4, 9, 10, 8, 2, 2, 6, 9, 2, 8, 7, 11, 5, 2, 7, 3, 10, 2, 10, 17, 8, 9, 8, 9, 10, 2, 7, 2, 9, 2, 10, 8, 4, 3, 9, 6, 10, 17, 3, 9, 2, 17, 7

Offset: 1

Vladeta Jovovic, Dec 25 2001

nonn

			invphi(6) = [7, 9, 14, 18], thus a(7) = a(9) = a(14) = a(18) = 4.

Antti Karttunen, Table of n, a(n) for n = 1..10000
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
Wikipedia, Euler's totient function (see the last paragraph in section "Some values of the function")

Cf. A000010, A001055, A014197, A032447, A036913, A057826, A071181.

Cf. A070305 (positions where coincides with A000005).

Maple
```
nops(invphi(phi(n)));
```

With[{nn = 120}, Function[s, Take[#, nn] &@ Values@ KeySort@ Flatten@ Map[Function[{k, m}, Map[# -> m &, k]] @@ {#, Length@ #} &@ Lookup[s, #] &, Keys@ s]]@ KeySort@ PositionIndex@ Array[EulerPhi, nn^2 + 10]] (* Michael De Vlieger, Jul 18 2017 *)

for(n=1,150,print1(sum(i=1,10*n,if(n-eulerphi(n)-i+eulerphi(i),0,1)),",")) \\ By the original author(s). Note: the upper limit 10*n for the search range is quite ad hoc, and is guaranteed to miss some cases when n is large enough. Cf. Wikipedia-article. - Antti Karttunen, Jul 19 2017

\\ Here is an implementation not using arbitrary limits:
A014197(n, m=1) = { n==1 && return(1+(m<2)); my(p, q); sumdiv(n, d, if( d>=m && isprime(d+1), sum( i=0, valuation(q=n\d, p=d+1), A014197(q\p^i, p))))} \\ M. F. Hasler, Oct 05 2009
A066412(n) = A014197(eulerphi(n)); \\ Antti Karttunen, Jul 19 2017

a(n) = invphiNum(eulerphi(n)); \\ Amiram Eldar, Nov 14 2024, using Max Alekseyev's invphi.gp

;; A naive implementation requiring precomputed A057826:
(define (A066412 n) (if (<= n 2) 2 (let ((ph (A000010 n))) (let loop ((k (A057826 (/ ph 2))) (s 0)) (if (zero? k) s (loop (- k 1) (+ s (if (= ph (A000010 k)) 1 0)))))))) ;; Antti Karttunen, Jul 18 2017

a(n) = Card( k>0 : cototient(k)=cototient(n) ) where cototient(x) = x - phi(x). - Benoit Cloitre, May 09 2002
From Antti Karttunen, Jul 18 2017: (Start)
a(n) = A014197(A000010(n)).
For all n, a(n) <= A071181(n).
(End)

A028476 Greatest k such that phi(k) = phi(n), where phi is Euler's totient function.

Original entry on oeis.org

2, 2, 6, 6, 12, 6, 18, 12, 18, 12, 22, 12, 42, 18, 30, 30, 60, 18, 54, 30, 42, 22, 46, 30, 66, 42, 54, 42, 58, 30, 62, 60, 66, 60, 90, 42, 126, 54, 90, 60, 150, 42, 98, 66, 90, 46, 94, 60, 98, 66, 120, 90, 106, 54, 150, 90, 126, 58, 118, 60, 198, 62, 126, 120, 210, 66, 134

Offset: 1

Vladeta Jovovic, Jan 12 2002

nonn

Every number in this sequence occurs at least twice. For all n > 6, a(n) > phi(n)^2 is impossible. - Alonso del Arte, Dec 31 2016

			phi(1) = 1 and phi(2) = 1 also. There is no greater k such that phi(k) = 1, so therefore a(1) = a(2) = 2.
phi(3) = phi(4) = phi(6) = 2, and there is no greater k such that phi(k) = 6, hence a(3) = a(4) = a(6) = 6.

Antti Karttunen, Table of n, a(n) for n = 1..10000 (computed from the b-file of A057826 provided by T. D. Noe)
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

Cf. A000010, A015126, A057826, A066412, A066659, A071181.

Table[Module[{k = (2 Boole[n <= 6]) + #^2}, While[EulerPhi@ k != #, k--]; k] &@ EulerPhi@ n, {n, 120}] (* Michael De Vlieger, Dec 31 2016 *)

a(n) = invphiMax(eulerphi(n)); \\ Amiram Eldar, Nov 14 2024, using Max Alekseyev's invphi.gp

a(1) = a(2) = 2, for n > 2, a(n) = A057826(A000010(n)/2). - Antti Karttunen, Aug 07 2017

A319048 a(n) is the greatest k such that A000010(k) divides n where A000010 is the Euler totient function.

Original entry on oeis.org

2, 6, 2, 12, 2, 18, 2, 30, 2, 22, 2, 42, 2, 6, 2, 60, 2, 54, 2, 66, 2, 46, 2, 90, 2, 6, 2, 58, 2, 62, 2, 120, 2, 6, 2, 126, 2, 6, 2, 150, 2, 98, 2, 138, 2, 94, 2, 210, 2, 22, 2, 106, 2, 162, 2, 174, 2, 118, 2, 198, 2, 6, 2, 240, 2, 134, 2, 12, 2, 142, 2, 270, 2, 6, 2, 12, 2, 158, 2, 330

Offset: 1

Michel Marcus, Sep 09 2018

nonn

Sándor calls this function the totient maximum function and remarks that this function is well-defined, since a(n) can be at least 2, and cannot be greater than n^2 (when n > 6).

Antti Karttunen, Table of n, a(n) for n = 1..16384
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
József Sándor, On the Euler minimum and maximum functions, Notes on Number Theory and Discrete Mathematics, Volume 15, 2009, Number 3, Pages 1—8.

Cf. A000010 (Euler totient), A061026 (the totient minimum function).
Cf. A319068 (the analog for the sum of divisors).
Cf. A070633, also A057635, A057826, A069932, A071181.
Right border of A378638.

a[n_] := Module[{kmax = If[n <= 6, 10 n, n^2]}, For[k = kmax, True, k--, If[Divisible[n, EulerPhi[k]], Return[k]]]];
Array[a, 80] (* Jean-François Alcover, Sep 17 2018, from PARI *)

a(n) = {my(kmax = if (n<=6, 10*n, n^2)); forstep (k=kmax, 1, -1, if ((n % eulerphi(k)) == 0, return (k)););}

\\ (The first two functions could probably be combined in a smarter way):
A014197(n, m=1) = { n==1 && return(1+(m<2)); my(p, q); sumdiv(n, d, if( d>=m && isprime(d+1), sum( i=0, valuation(q=n\d, p=d+1), A014197(q\p^i, p))))} \\ From A014197 by M. F. Hasler
A057635(n) = if(1==n,2,if((n%2),0,my(k=A014197(n),i=n); if(!k, 0, while(k, i++; if(eulerphi(i)==n, k--)); (i))));
A319048(n) = { my(m=0); fordiv(n,d, m = max(m,A057635(d))); (m); }; \\ Antti Karttunen, Sep 09 2018

a(n) = {my(d = divisors(n)); vecmax(vector(#d, i, invphiMax(d[i])));} \\ Amiram Eldar, Nov 29 2024, using Max Alekseyev's invphi.gp

a(n) = Max_{d|n} A057635(d). - Antti Karttunen, Sep 09 2018

A070633 a(n) is the number of k>0 such that phi(k) divides n.

Original entry on oeis.org

2, 5, 2, 9, 2, 9, 2, 14, 2, 7, 2, 19, 2, 5, 2, 20, 2, 13, 2, 16, 2, 7, 2, 34, 2, 5, 2, 11, 2, 13, 2, 27, 2, 5, 2, 31, 2, 5, 2, 30, 2, 13, 2, 14, 2, 7, 2, 51, 2, 7, 2, 11, 2, 15, 2, 19, 2, 7, 2, 37, 2, 5, 2, 35, 2, 13, 2, 9, 2, 9, 2, 63, 2, 5, 2, 9, 2, 11, 2, 46, 2, 7, 2, 31, 2, 5, 2, 25, 2, 17, 2

Offset: 1

Benoit Cloitre, May 13 2002

Inverse Möbius transform of A014197. - Antti Karttunen, Sep 10 2018

Antti Karttunen, Table of n, a(n) for n = 1..65537
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

Cf. A000010, A014197, A069932, A071181, A319048.

Row lengths of A378638.

for(n=1,120,print1(sum(i=1,100*n,if(n%eulerphi(i),0,1)),","));

\\ In contrast to above program, this is safe in any range 1..n:
A014197(n, m=1) = { n==1 && return(1+(m<2)); my(p, q); sumdiv(n, d, if( d>=m && isprime(d+1), sum( i=0, valuation(q=n\d, p=d+1), A014197(q\p^i, p))))}; \\ From A014197 by M. F. Hasler
A070633(n) = sumdiv(n, d, A014197(d)); \\ Antti Karttunen, Sep 10 2018

a(n) = sumdiv(n, d, invphiNum(d)); \\ Amiram Eldar, Nov 29 2024, using Max Alekseyev's invphi.gp

From Antti Karttunen, Sep 10 2018: (Start)
a(n) = Sum_{d|n} A014197(d).
a(n) >= A069932(n).
a(A000010(n)) = A071181(n).
(End)

A070610 Number of positive integers k such that sigma(k) divides sigma(n).

Original entry on oeis.org

1, 2, 2, 2, 3, 6, 3, 3, 2, 5, 6, 5, 3, 10, 10, 3, 5, 4, 3, 8, 5, 9, 10, 12, 3, 8, 5, 8, 5, 18, 5, 4, 13, 7, 13, 4, 2, 12, 8, 10, 8, 19, 3, 15, 6, 18, 13, 7, 3, 5, 18, 5, 7, 21, 18, 21, 7, 10, 12, 27, 4, 19, 6, 2, 15, 26, 3, 13, 19, 26, 18, 6, 2, 7, 7, 8, 19, 27, 7, 9, 2, 13, 15, 14, 13, 9

Offset: 1

Benoit Cloitre, May 13 2002

Antti Karttunen, Table of n, a(n) for n = 1..16384
Index entries for sequences related to sigma(n)

Cf. A000203, A070242, A071181, A074754.

for(n=1,150,print1(sum(i=1,10*n,if((sigma(n))%(sigma(i)),0,1)),","))

A070610(n) = { my(s=sigma(n)); sum(k=1, s, !(s%sigma(k))); }; \\ Antti Karttunen, Nov 17 2017

a(n) = A074754(A000203(n)). - Antti Karttunen, Nov 17 2017

Offset corrected, name edited by Antti Karttunen, Nov 17 2017

cp's OEIS Frontend

A066412 Number of elements in the set phi_inverse(phi(n)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Scheme

Formula

A028476 Greatest k such that phi(k) = phi(n), where phi is Euler's totient function.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A319048 a(n) is the greatest k such that A000010(k) divides n where A000010 is the Euler totient function.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

A070633 a(n) is the number of k>0 such that phi(k) divides n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

PARI

PARI

Formula

A070610 Number of positive integers k such that sigma(k) divides sigma(n).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

Formula

Extensions