A014197 -id:A014197 - cp's OEIS frontend

A280611 Number of degree n products of distinct cyclotomic polynomials.

1, 2, 4, 6, 10, 14, 24, 34, 52, 70, 102, 134, 194, 254, 352, 450, 610, 770, 1036, 1302, 1716, 2130, 2770, 3410, 4406, 5402, 6892, 8382, 10600, 12818, 16120, 19422, 24216, 29010, 35932, 42854, 52832, 62810, 76944, 91078, 111008, 130938

Offset: 0

Christopher J. Smyth, Jan 06 2017

a(n) is also the number monic integer polynomials of degree n all of whose roots are distinct and of modulus 1. This follows from a classical result of Kronecker -- see link.

			a(3) = 6 because there are six degree-3 products of distinct cyclotomic polynomials, namely (z-1)(z^2+z+1), (z-1)(z^2+1), (z-1)(z^2-z+1), (z+1)(z^2+z+1), (z+1)(z^2+1) and (z+1)(z^2-z+1).

Boyd, David W.(3-BC); Montgomery, Hugh L.(1-MI), Cyclotomic partitions. In Number theory (Banff, AB, 1988), 7-25. Walter de Gruyter & Co., Berlin, 1990 ISBN:3-11-011723-1, MR1106647. [Asymptotics]

Vaclav Kotesovec, Table of n, a(n) for n = 0..10000
L. Kronecker, Zwei Sätze über Gleichungen mit ganzzahligen Coefficienten, J. Reine Angew. Math. 53 (1857), 173-175.

Cf. A014197, A280709 (variant where z, as well as cyclotomic polynomials, is allowed in the product), A120963 (variant where repeated roots are allowed), A051894 (variant where both z and repeated roots are allowed), A280712 (Inverse Euler transform of sequence).

Table[SeriesCoefficient[Product[(1 + x^EulerPhi@ i), {i, n E^2}], {x, 0, n}], {n, 0, 92}] (* Michael De Vlieger, Jan 10 2017 *)

G.f.: Product_{i>=1} (1 + x^phi(i)) = Product_{j>=1} (1 + x^j)^A014197(j), where phi(i)=A000010(i) is Euler's totient function.
This is also the Euler transform of A280712.
a(n) ~ exp(sqrt(105*zeta(3)*n/2)/Pi) * (105*zeta(3)/2)^(1/4) / (4*Pi*n^(3/4)). - Vaclav Kotesovec, Sep 02 2021

A362485 Number of numbers k such that iphi(k) = n, where iphi is the infinitary totient function A091732.

Original entry on oeis.org

2, 2, 2, 2, 0, 4, 0, 4, 0, 2, 0, 6, 0, 0, 2, 4, 0, 4, 0, 2, 0, 2, 0, 10, 0, 0, 0, 2, 0, 6, 0, 4, 0, 0, 0, 8, 0, 0, 0, 4, 0, 2, 0, 2, 2, 2, 0, 14, 0, 0, 0, 2, 0, 2, 0, 2, 0, 2, 0, 10, 0, 0, 0, 4, 0, 4, 0, 0, 0, 2, 0, 14, 0, 0, 0, 0, 0, 2, 0, 8, 0, 2, 0, 4, 0, 0

Offset: 1

Amiram Eldar, Apr 22 2023

nonn

a(n) is even for all n, because if k is a solution to iphi(k) = n, and A007814(k) is even, then 2*k is also a solution, i.e., iphi(2*k) = n.

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

Row lengths of A362484.
Cf. A007814, A091732, A362486 (positions of 0's), A362487 (indices of records).
Similar sequences: A014197, A063740, A361967, A362181.

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

a(A362486(n)) = 0.

A051894 Number of monic polynomials with integer coefficients of degree n with all roots in unit disc.

Original entry on oeis.org

1, 3, 9, 19, 43, 81, 159, 277, 501, 831, 1415, 2253, 3673, 5675, 8933, 13447, 20581, 30335, 45345, 65611, 96143, 136941, 197221, 276983, 392949, 545119, 763081, 1046835, 1448085, 1966831, 2691697, 3622683, 4909989, 6553615, 8804153

Offset: 0

Pantelis Damianou, Dec 17 1999

The number of polynomials of a given degree that satisfy the conditions 1) monic, 2) integer coefficients and 3) all roots in the unit disc is finite. This is an old theorem of Kronecker.
The irreducible polynomials with this property consist of f(x)=x plus the cyclotomic polynomials. - Franklin T. Adams-Watters, Jul 19 2006
First differences give A120963. - Joerg Arndt, Nov 22 2014

			a(1)=3 because the only monic, linear, polynomials with coefficients in Z and all their roots in the unit disc are f(z)=z, g(z)=z-1, h(z)=z+1.

Pantelis A. Damianou, Monic polynomials in Z[x] with roots in the unit disc, Technical Report TR\16\1999, University of Cyprus.

Vaclav Kotesovec, Table of n, a(n) for n = 0..10000 (terms 0..1000 from T. D. Noe)
Pantelis A. Damianou, Monic polynomials in Z[x] with roots in the unit disc, American Math. Monthly, 108, 253-257 (2001).

Cf. A014197, A120963.

max = 40; CoefficientList[Product[1/(1 - x^EulerPhi[k]), {k, 1, 5max}] + O[x]^max, x] // Accumulate (* Jean-François Alcover, Apr 14 2017 *)

N=66; x='x+O('x^N); Ph(n)=if(n==0,1,eulerphi(n));
Vec(1/prod(n=0,N,1-x^Ph(n))) \\ Joerg Arndt, Jul 10 2015

Euler transform of b(n) where b(n) = A014197(n) except for n=1, where b(n) = 3 instead of 2; cumulative sum of A120963. - Franklin T. Adams-Watters, Jul 19 2006

log(a(n)) ~ sqrt(105*zeta(3)*n)/Pi. - Vaclav Kotesovec, Sep 02 2021

More terms from Franklin T. Adams-Watters, Jul 19 2006

A055486 Number of solutions to sigma(x) = n!.

Original entry on oeis.org

1, 0, 1, 3, 4, 15, 33, 111, 382, 1195, 3366, 14077, 53265, 229603, 910254, 4524029, 18879944, 91336498, 561832582, 2801857644, 14652294729, 78894985156, 408373652461, 2378940665083, 11939275822636, 71931330299023, 392274481206066, 2626331088771946

Offset: 1

Labos Elemer, Jun 28 2000

nonn

			For n = 9, solutions to sigma(x) = n! = 362880 form a set {97440, ..., 361657} of size 382, so a(9) = 382.

R. K. Guy (1981): Unsolved Problems In Number Theory, B39.

Max A. Alekseyev, Computing the Inverses, their Power Sums, and Extrema for Euler's Totient and Other Multiplicative Functions. Journal of Integer Sequences, Vol. 19 (2016), Article 16.5.2

Cf. A000142, A000203, A054973, A014197, A055488, A055489, A055506.

with(numtheory): for f from 1 to 9 do fac := f!: k := 0:for n from 1 to fac do if sigma(n)=fac then k := k+1: fi: od: print( k); od:

a(n) = A054973(n!) = Cardinality[{x; A000203(x) = A000142(n)}].

More terms from Jud McCranie, Oct 09 2000
a(13)-a(14) from Donovan Johnson, Nov 22 2008
a(15) from Ray Chandler, Jan 13 2009
a(16)-a(28) from Max Alekseyev, Jan 23 2012

A055506 Number of solutions to the equation phi(x) = n!.

Original entry on oeis.org

2, 3, 4, 10, 17, 49, 93, 359, 1138, 3802, 12124, 52844, 182752, 696647, 2852886, 16423633, 75301815, 367900714, 1531612895, 8389371542, 40423852287, 213232272280, 1295095864798, 7991762413764, 42259876674716, 252869570952706, 1378634826630301, 8749244047999717

Offset: 1

Labos Elemer, Jun 29 2000

nonn

Note that if phi(x) = n!, then x must be a product of primes p such that p - 1 divides n!. - David Wasserman, Apr 30 2002

Gives the row lengths of the table A165773 (see example). All solutions to phi(x)=n! are in the interval [n!,(n+1)!] with the smallest/largest solutions given in A055487/A165774 respectively. - M. F. Hasler, Oct 04 2009

			n = 5, phi(x) = 5! = 120 holds for the following 17 numbers: { 143, 155, 175, 183, 225, 231, 244, 248, 286, 308, 310, 350, 366, 372, 396, 450, 462 }.
From _M. F. Hasler_, Oct 04 2009: (Start)
The table A165773 looks as follows:
  1,2, (a(1)=2 numbers for which phi(n) = 1! = 1)
  3,4,6, (a(2)=3 numbers for which phi(n) = 2! = 2)
  7,9,14,18, (a(3)=4 numbers for which phi(n) = 3! = 6)
  35,39,45,52,56,70,72,78,84,90, (a(4)=10 numbers for which phi(n) = 4! = 24)
  ... (End)

Andrew Lelechenko, Table of n, a(n) for n = 1..36
Max A. Alekseyev, Computing the Inverses, their Power Sums, and Extrema for Euler's Totient and Other Multiplicative Functions. Journal of Integer Sequences, Vol. 19 (2016), Article 16.5.2.
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

Cf. A000010, A000142, A000203, A014197, A054873, A055486, A067847, A165773, A165774.

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

use ntheory ":all"; print "$ ",scalar(inverse_totient(factorial($))),"\n" for 1..20; # Dana Jacobsen, Mar 04 2019

a(n) = A014197(n!) = Cardinality({x; A000010(x) = A000142(n)}).

More terms from Jud McCranie, Jan 02 2001
More terms from David Wasserman, Apr 30 2002 (with the assistance of Vladeta Jovovic and Sascha Kurz)
a(21)-a(28) from Max Alekseyev, Jan 26 2012, Jul 09 2014

A071386 Numbers k such that the cardinality of the set of solutions to phi(x) = k is odd.

Original entry on oeis.org

2, 8, 20, 32, 40, 44, 48, 56, 60, 72, 92, 96, 104, 108, 116, 120, 128, 132, 140, 144, 156, 164, 192, 204, 212, 216, 220, 240, 252, 260, 272, 276, 296, 300, 332, 344, 356, 360, 368, 380, 384, 392, 396, 400, 416, 420, 440, 444, 452, 456, 476, 480, 500, 504, 512

Offset: 1

Labos Elemer, May 23 2002

nonn

			k = 40 is a term: InvPhi(40) = {41,55,75,82,88,100,110,132,150} has 9 entries.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

Cf. A000010 (phi), A014197, A058277, A063512, A071387.

is(n) = invphiNum(n) % 2; \\ Amiram Eldar, Mar 28 2024, using Max Alekseyev's invphi.gp (see links).

{ k : Card(InvPhi(k)) mod 2 = 1 }.

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

A063439 a(n) = phi(n)^phi(n).

Original entry on oeis.org

1, 1, 4, 4, 256, 4, 46656, 256, 46656, 256, 10000000000, 256, 8916100448256, 46656, 16777216, 16777216, 18446744073709551616, 46656, 39346408075296537575424, 16777216, 8916100448256, 10000000000, 341427877364219557396646723584, 16777216, 104857600000000000000000000

Offset: 1

Reinhard Zumkeller, Jul 24 2001

nonn

Number of endofunctions over RRS[n]. Used in proof of Dirichlet theorem to derive characters: a(n) = A000312(A000010(n)). - Labos Elemer, May 27 2002
Sum_{n>=1} 1/phi(n)^phi(n) ~ 2.765711032... and so apparently equals Sum_{n>=1} A014197(n)/n^n where A014197(n) is the number of numbers m such that phi(m) = n. Is this a known result? - Gerald McGarvey, May 16 2004
The equality above is true and it is not unique for phi: for each value k = phi(n) the summand 1/phi(n)^phi(n) appears A014197(k) times, so Sum_{n>=1} 1/phi(n)^phi(n) = Sum_{k>=1} A014197(k) * (1/k^k). - Amiram Eldar, Dec 10 2024

Harry J. Smith, Table of n, a(n) for n = 1..200

Cf. A000010, A000312, A014197.

[EulerPhi(n)^EulerPhi(n): n in [1..30]]; // Vincenzo Librandi, Dec 29 2019

Table[EulerPhi[n]^EulerPhi[n], {n, 30}] (* Vincenzo Librandi, Dec 29 2019 *)

{ for (n=1, 200, p=eulerphi(n); write("b063439.txt", n, " ", p^p) ) } \\ Harry J. Smith, Aug 21 2009

n log n / (log log n) << log a(n) < n log n. - Charles R Greathouse IV, Jan 19 2012

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)

A072075 Smallest solution to phi(x) = 10^n where phi(x) = A000010(x).

Original entry on oeis.org

1, 11, 101, 1111, 10291, 100651, 1004251, 10165751, 100064101, 1000078501, 10000222501, 100062501601, 1000062516001, 10000062660001, 100002441447211, 1003922328562757, 10000390625025601, 100000002482366251, 1000000002851006251, 10000062500000160001

Offset: 0

Labos Elemer, Jun 13 2002

nonn

			n=3: a(3)=1111 because InvPhi[1000]= {1111,1255,1375,1875,2008,2222,2500,2510,2750,3012,3750}.

Ray Chandler, Table of n, a(n) for n = 0..1000
Max A. Alekseyev, Computing the Inverses, their Power Sums, and Extrema for Euler's Totient and Other Multiplicative Functions. Journal of Integer Sequences, Vol. 19 (2016), Article 16.5.2

Cf. A000010, A014573, A014197, A110077, A072074, A072076.

More terms from Max Alekseyev, Apr 26 2010

a(18)-a(19) from Donovan Johnson, Feb 02 2012

cp's OEIS Frontend

A280611 Number of degree n products of distinct cyclotomic polynomials.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A362485 Number of numbers k such that iphi(k) = n, where iphi is the infinitary totient function A091732.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A051894 Number of monic polynomials with integer coefficients of degree n with all roots in unit disc.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A055486 Number of solutions to sigma(x) = n!.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Formula

Extensions

A055506 Number of solutions to the equation phi(x) = n!.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Perl

Formula

Extensions

A071386 Numbers k such that the cardinality of the set of solutions to phi(x) = k is odd.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

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