A032447 -id:A032447 - cp's OEIS frontend

A064275 Inverse of sequence A032447 considered as a permutation of the positive integers.

1, 2, 3, 4, 6, 5, 10, 7, 11, 8, 19, 9, 21, 12, 14, 15, 27, 13, 33, 16, 22, 20, 42, 17, 37, 23, 34, 24, 54, 18, 56, 28, 38, 29, 44, 25, 65, 35, 45, 30, 73, 26, 82, 39, 46, 43, 89, 31, 83, 40, 58, 47, 102, 36, 74, 48, 66, 55, 109, 32, 111, 57, 67, 59, 91, 41, 128, 60, 86, 49, 130, 50, 132, 68, 75, 69, 112, 51, 149, 61

Offset: 1

Howard A. Landman, Sep 23 2001

Cf. A032447, A007614.

import Data.List (elemIndex); import Data.Maybe (fromJust)
a064275 = (+ 1) . fromJust . (`elemIndex` a032447_list)
-- Reinhard Zumkeller, Nov 22 2015

Edited by N. J. A. Sloane, Nov 05 2007

More terms from Alois P. Heinz, Jan 20 2011

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

A007614 All values attained by the phi(n) function, in ascending order.

Original entry on oeis.org

1, 1, 2, 2, 2, 4, 4, 4, 4, 6, 6, 6, 6, 8, 8, 8, 8, 8, 10, 10, 12, 12, 12, 12, 12, 12, 16, 16, 16, 16, 16, 16, 18, 18, 18, 18, 20, 20, 20, 20, 20, 22, 22, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 28, 28, 30, 30, 32, 32, 32, 32, 32, 32, 32, 36, 36, 36, 36, 36, 36, 36, 36

Offset: 1

Walter Nissen

Write down phi(1), phi(2), phi(3), ..., then sort this list. Of course the list before sorting is simply sequence A000010.
To ensure that all terms are found, the values of phi(n) should be computed for all n up to a primorial p# -- which are the local minima of the phi function. Selecting and sorting the values of phi(n) <= phi(p#) produces the terms of this sequence. - T. D. Noe, Mar 22 2011
A002202(n) occurs A058277(n) times. - Reinhard Zumkeller, Nov 22 2015

Zak Seidov, Table of n, a(n) for n=1..9999 (values up to 5152)
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

Corresponding values of n are given by A032447.

Cf. A000010. A002110, A002202, A058277 (run lengths).

import Data.List.Ordered (insertBag)
a007614 n = a007614_list !! (n-1)
a007614_list = f [1..] a002110_list [] where
   f xs'@(x:xs) ps'@(p:ps) us
     | x < p = f xs ps' $ insertBag (a000010' x) us
     | otherwise = vs ++ f xs' ps ws
     where (vs, ws) = span (<= a000010' x) us
-- Reinhard Zumkeller, Nov 22 2015

Cases[Sort[Table[EulerPhi[n],{n,1,36^2}]], n_ /; n<=36 ]  (* Jean-François Alcover, Mar 22 2011 *)
A007614[m_]:=Select[Sort[Table[EulerPhi[n],{n,Prime[m]}]],#≤m&]; A007614[1000] (* Zak Seidov, Mar 22 2011 *)
primorial = Times @@ Prime[Range[4]]; phi = EulerPhi[primorial]; Sort[Select[EulerPhi[Range[primorial]], # <= phi &]] (* T. D. Noe, Mar 22 2011 *)

PARI
```
(See A032447).
```

lista(nmax) = {my(m); for(n = 1, nmax, m = invphiNum(n); for(i = 1, m, print1(n, ", ")));} \\ Amiram Eldar, Nov 15 2024 using Max Alekseyev's invphi.gp

A362484 Irregular table read by rows in which the n-th row consists of all the numbers m such that iphi(m) = n, where iphi is the infinitary totient function A091732.

Original entry on oeis.org

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

Offset: 1

Amiram Eldar, Apr 22 2023

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

Amiram Eldar, Table of n, a(n) for n = 1..17858 (first 100000 rows)

Cf. A091732, A162247, A362485 (row lengths).

Similar sequences: A032447, A361966, A362213, A362180.

powQ[n_] := n == 2^IntegerExponent[n, 2]; powfQ[n_] := Length[fact = FactorInteger[n]] == 1 && powQ[fact[[1, 2]]];
invIPhi[n_] := Module[{fct = f[n], sol}, sol = Times @@@ (1 + Select[fct, UnsameQ @@ # && AllTrue[# + 1, powfQ] &]); Sort@ Join[sol, 2*sol]]; invIPhi[1] = {1, 2};
Table[invIPhi[n], {n, 1, 36}] // Flatten (* using the function f by T. D. Noe at A162247 *)

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

Original entry on oeis.org

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)

A206225 Numbers j such that the numbers Phi(j, m) are in sorted order for any integer m >= 2, where Phi(k, x) is the k-th cyclotomic polynomial.

Original entry on oeis.org

1, 2, 6, 4, 3, 10, 12, 8, 5, 14, 18, 9, 7, 15, 20, 24, 16, 30, 22, 11, 21, 26, 28, 36, 42, 13, 34, 40, 48, 32, 60, 17, 38, 54, 27, 19, 33, 44, 50, 25, 66, 46, 23, 35, 39, 52, 45, 56, 72, 90, 84, 78, 70, 58, 29, 62, 31, 51, 68, 80, 96, 64, 120

Offset: 1

Lei Zhou, Feb 13 2012

nonn

Based on A002202 "Values taken by totient function phi(m)", A000010 can only take certain even numbers. So for the worst case, the largest Phi(k,m) with degree d (even positive integer) will be (1-k^(d+1))/(1-k) (or smaller) and the smallest Phi(k,m) with degree d+2 will be (1+k^(d+3))/(1+k) (or larger).
Note that (1+k^(d+3))/(1+k)-(1-k^(d+1))/(1-k) = (k/(k^2-1))*(2+k^d*(k^3-(k^2+k+1))) >= 0 since k^3 > k^2+k+1 when k >= 2.
This means that this sequence can be segmented into sets in which Phi(k,m) shares the same degree of polynomial and it can be generated in this way.

			For k such that A000010(k) = 1,
  Phi(1,m) = -1 + m,
  Phi(2,m) = 1 + m,
  Phi(1,m) < Phi(2,m),
  so, a(1)=1, a(2)=2.
For k > 2 such that A000010(k) = 2,
  Phi(3,m) = 1 + m + m^2,
  Phi(4,m) = 1 + m^2,
  Phi(6,m) = 1 - m + m^2.
For m > 1, Phi(6,m) < Phi(4,m) < Phi(3,m), so a(3)=6, a(4)=4, and a(5)=3 (noting that Phi(6,m) > Phi(2,m) when m > 2, and Phi(6,2) = Phi(2,2)).
For k such that A000010(k) = 4,
  Phi(5,m) = 1 + m + m^2 + m^3 + m^4,
  Phi(8,m) = 1 + m^4,
  Phi(10,m) = 1 - m + m^2 - m^3 + m^4,
  Phi(12,m) = 1 - m^2 + m^4.
For m > 1, Phi(10,m) < Phi(12,m) < Phi(8,m) < Phi(5,m), so a(6) = 10, a(7) = 12, a(8) = 8, and a(9) = 5 (noting Phi(10,m) - Phi(3,m) = m((m^2 + m + 2)(m - 2) + 2) >= 4 > 0 when m >= 2).

S. P. Glasby, Cyclotomic ordering conjecture, arXiv:1903.02951 [math.NT], 2019.
Carl Pomerance and Simon Rubinstein-Salzedo, Cyclotomic Coincidences, arXiv:1903.01962 [math.NT], 2019.

Cf. A194712, A000010, A002202, A032447.

t = Select[Range[400], EulerPhi[#] <= 40 &]; SortBy[t, Cyclotomic[#, 2] &]

A194712 Numbers L such that cyclotomic polynomial Phi(L,m) < Phi(j,m) for any j > L and m >= 2.

Original entry on oeis.org

1, 2, 6, 10, 12, 14, 18, 20, 24, 30, 36, 42, 48, 60, 66, 72, 90, 96, 120, 126, 150, 210, 240, 270, 330, 390, 420, 462, 510, 546, 570, 630, 660, 690, 714, 780, 840, 870, 930, 990, 1050, 1110, 1140, 1170, 1260, 1320, 1470, 1530, 1560, 1680, 1710, 1890, 1950

Offset: 1

Lei Zhou, Feb 13 2012

nonn

			For k such that A000010(k) = 1,
  Phi(1,m) = -1 + m,
  Phi(2,m) = 1 + m,
  Phi(1,m) < Phi(2,m),
so a(1) = 1, a(2) = 2.
For k > 2 such that A000010(k) = 2,
  Phi(3,m) = 1 + m + m^2,
  Phi(4,m) = 1 + m^2,
  Phi(6,m) = 1 - m + m^2.
Obviously when integer m > 1, Phi(6,m) < Phi(4,m) < Phi(3,m), so a(3)=6.
For k > 6 such that A000010(k) = 4,
  Phi(8,m) = 1 + m^4,
  Phi(10,m) = 1 - m + m^2 - m^3 + m^4,
  Phi(12,m) = 1 - m^2 + m^4.
Obviously when integer m > 1, Phi(10,m) < Phi(12,m) < Phi(8,m), so a(4) = 10, and a(5) = 12.

Wikipedia, Cyclotomic polynomial

Cf. A206225, A000010, A002202, A032447.

t = Select[Range[2400], EulerPhi[#] <= 480 &]; t2 = SortBy[t, Cyclotomic[#, 2] &]; DeleteDuplicates[Table[Max[Take[t2, n]], {n, Length[t2]}]]

A303745 Totients t where gcd({x: phi(x)=t}) > 1.

Original entry on oeis.org

10, 22, 28, 30, 44, 46, 52, 54, 56, 58, 66, 70, 78, 82, 92, 102, 104, 106, 110, 116, 126, 130, 136, 138, 140, 148, 150, 164, 166, 172, 178, 184, 190, 196, 198, 204, 208, 210, 212, 220, 222, 226, 228, 238, 250, 260, 262, 268, 270, 282, 292, 294, 296, 306

Offset: 1

Torlach Rush, Apr 29 2018

nonn

If the least solution of phi(x)=t is prime then gcd({x: phi(x)=t}) is prime.
If gcd({x: phi(x)=t}) > 1 is not prime then the least solution of phi(x)=t is not prime.
For known terms if the number of solutions of x: phi(x)=t is 2 or 3 then the least solution divides the greatest solution (see A297475). - Torlach Rush, Jul 03 2018

			10 is a term because the greatest common divisor of 11 and 22, the solutions of phi(10) is 11.
2 is not a term because the greatest common divisor of 3, 4 and 6, the solutions of phi(2) is 1.

Robert Israel, Table of n, a(n) for n = 1..10000
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
Maxim Rytin, Finding the Inverse of Euler Totient Function, Wolfram Library Archive, 1999.

Cf. A000010, A002202, A032447, A297475, A007367.

filter:= proc(n) local L;
L:= numtheory:-invphi(n);
L <> [] and igcd(op(L)) > 1
end proc:
select(filter, [seq(i,i=2..1000, 2)]); # Robert Israel, Jun 26 2018

Select[Range[2, 1000, 2], GCD@@invphi[#] > 1&] (* Jean-François Alcover, Jan 31 2023, using Maxim Rytin's invphi program *)

isok(n) = gcd(invphi(n)) > 1; \\ Michel Marcus, May 13 2018

gcd({x: phi(x)=t}) > 1.

A085713 Consider numbers k such that phi(x) = k has exactly 3 solutions and they are (3p, 4p, 6*p) where p is 1 or a prime. Sequence gives values of p.

Original entry on oeis.org

1, 23, 29, 47, 53, 59, 71, 83, 103, 107, 131, 149, 167, 173, 179, 191, 197, 223, 227, 239, 263, 269, 283, 293, 311, 317, 347, 359, 373, 383, 389, 419, 431, 443, 467, 479, 491, 503, 509, 557, 563, 569, 587, 599, 643, 647, 653, 659, 677, 683, 709, 719

Offset: 1

Alford Arnold, Jul 19 2003

nonn

Prime numbers in this sequence are called prime replicators of 2, by Stolarski and Greenbaum, (3, 4, 6) being the solutions of phi(x)=2. - Michel Marcus, Oct 20 2012

Prime numbers in this sequence when multiplied by 2 equal k + 2. For example, 83 * 2 = 164 + 2. - Torlach Rush, Jun 16 2018

			83 is a term because the three solutions (249,332,498) to phi(x) = 164 can be written as (3*83, 4*83, 6*83).

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..500 from Reinhard Zumkeller)
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
K. B. Stolarski and S. Greenbaum, A Ratio Associated with phi(x) = n, The Fibonacci Quarterly, Volume 23, Number 3, August 1985, pp. 265-269.

Cf. A000010, A002202, A007367, A007374, A032447, A058277, A064275.

Cf. A007614, A010051.

import Data.List.Ordered (insertBag)
import Data.List (groupBy); import Data.Function (on)
a085713 n = a085713_list !! (n-1)
a085713_list = 1 : r yx3ss where
   r (ps:pss) | a010051' cd == 1 &&
                map (flip div cd) ps == [3, 4, 6] = cd : r pss
              | otherwise = r pss  where cd = foldl1 gcd ps
   yx3ss = filter ((== 3) . length) $
       map (map snd) $ groupBy ((==) `on` fst) $
       f [1..] a002110_list []
       where f is'@(i:is) ps'@(p:ps) yxs
              | i < p = f is ps' $ insertBag (a000010' i, i) yxs
              | otherwise = yxs' ++ f is' ps yxs''
              where (yxs', yxs'') = span ((<= a000010' i) . fst) yxs
-- Reinhard Zumkeller, Nov 25 2015

t = Table[ EulerPhi[n], {n, 1, 5000}]; u = Union[ Select[t, Count[t, # ] == 3 &]]; a = {}; Do[k = 1; While[ EulerPhi[3k] != u[[n]], k++ ]; AppendTo[a, k], {n, 1, 60}]; Sort[a]

is(p) = if(p > 1 && !isprime(p), 0, invphi(eulerphi(3*p)) == [3*p, 4*p, 6*p]); \\ Amiram Eldar, Nov 19 2024, using Max Alekseyev's invphi.gp

Edited and extended by Robert G. Wilson v, Jul 19 2003

Nonprimes 343=7^3 and 361=19^2 deleted by Reinhard Zumkeller, Nov 25 2015

A035113 Numbers != 2 (mod 4) listed in order of increasing totient function phi (A000010).

Original entry on oeis.org

1, 3, 4, 5, 8, 12, 7, 9, 15, 16, 20, 24, 11, 13, 21, 28, 36, 17, 32, 40, 48, 60, 19, 27, 25, 33, 44, 23, 35, 39, 45, 52, 56, 72, 84, 29, 31, 51, 64, 68, 80, 96, 120, 37, 57, 63, 76, 108, 41, 55, 75, 88, 100, 132, 43, 49, 69, 92, 47, 65, 104, 105, 112, 140, 144

Offset: 1

N. J. A. Sloane

			phi(1)=1, phi(3)=2, phi(4)=2, phi(5)=4, ...

Dumitru Damian, Table of n, a(n) for n = 1..10000
L. C. Washington, The Main Conjecture and Annihilation of Class Groups, In: Introduction to Cyclotomic Fields, Graduate Texts in Mathematics, vol 83 (1997) Springer, New York, NY.

Cf. A000010, A035114.

Cf. A002181, A002202, A007614, A014197, A016825, A032447, A058277.

from sympy import totient as A000010
def lov(n): return sorted([[A000010(n), n] for n in range(1,n) if n%4 != 2])
print([x[1] for x in lov(200)][:100]) # Dumitru Damian, Feb 01 2022

More terms from James Sellers

a(43) onward corrected by Sean A. Irvine, Sep 26 2020

cp's OEIS Frontend

A064275 Inverse of sequence A032447 considered as a permutation of the positive integers.

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

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

A007614 All values attained by the phi(n) function, in ascending order.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

A362484 Irregular table read by rows in which the n-th row consists of all the numbers m such that iphi(m) = n, where iphi is the infinitary totient function A091732.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

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

A206225 Numbers j such that the numbers Phi(j, m) are in sorted order for any integer m >= 2, where Phi(k, x) is the k-th cyclotomic polynomial.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A194712 Numbers L such that cyclotomic polynomial Phi(L,m) < Phi(j,m) for any j > L and m >= 2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A303745 Totients t where gcd({x: phi(x)=t}) > 1.

Views

Author

Keywords

Comments

Examples

A085713 Consider numbers k such that phi(x) = k has exactly 3 solutions and they are (3p, 4p, 6*p) where p is 1 or a prime. Sequence gives values of p.