A120963 -id:A120963 - cp's OEIS frontend

A341711 a(n) = A120963(2*n+1)/2.

1, 5, 19, 59, 165, 419, 1001, 2257, 4877, 10133, 20399, 39881, 76085, 141877, 259373, 465493, 821813, 1428725, 2449573, 4145249, 6931259, 11459483, 18749007, 30373189, 48752125, 77568683, 122406223, 191651957, 297856813, 459652759, 704595749, 1073152385

Offset: 0

N. J. A. Sloane, Feb 19 2021

nonn

A bisection of A341710.

D. Weigel, R. Veysseyre, T. Phan, J. M. Effantin, and Y. Billiet, Crystallography, geometry and physics in higher dimensions. I. Point-symmetry operations, Acta Cryst., A40 (1984), 323-330 (see Table 3).

Cf. A120963, A341710, A341712.

with(numtheory):
b:= proc(n) option remember; nops(invphi(n)) end:
g:= proc(n) option remember; `if`(n=0, 1, add(
      g(n-j)*add(d*b(d), d=divisors(j)), j=1..n)/n)
    end:
a:= n-> g(2*n+1)/2:
seq(a(n), n=0..40);  # Alois P. Heinz, Feb 19 2021

terms = 64; (* number of terms of A120963 *)
nmax = Floor[terms/2] - 1;
S[m_] := S[m] = CoefficientList[Product[1/(1 - x^EulerPhi[k]),
     {k, 1, m*terms}] + O[x]^(terms + 1),x];
S[m = 1];
S[m++];
While[S[m] != S[m - 1], m++];
A120963 = S[m];
a[n_ /; 0 <= n <= nmax] := A120963[[2 n + 2]]/2;
Table[a[n], {n, 0, nmax}] (* Jean-François Alcover, May 12 2022 *)

A341710 a(n) = A120963(n)/2.

Original entry on oeis.org

1, 3, 5, 12, 19, 39, 59, 112, 165, 292, 419, 710, 1001, 1629, 2257, 3567, 4877, 7505, 10133, 15266, 20399, 30140, 39881, 57983, 76085, 108981, 141877, 200625, 259373, 362433, 465493, 643653, 821813, 1125269, 1428725, 1939149, 2449573, 3297411, 4145249, 5538254

Offset: 1

N. J. A. Sloane, Feb 19 2021

nonn

Cf. A120963, A341711, A341712.

with(numtheory):
b:= proc(n) option remember; nops(invphi(n)) end:
a:= proc(n) option remember; `if`(n=0, 1/2, add(
      a(n-j)*add(d*b(d), d=divisors(j)), j=1..n)/n)
    end:
seq(a(n), n=1..40);  # Alois P. Heinz, Feb 19 2021

terms = 40;
S[m_] := S[m] = CoefficientList[Product[1/(1 - x^EulerPhi[k]),
     {k, 1, m*terms}] + O[x]^(terms+1), x]/2 // Rest;
S[m = 1];
S[m++];
While[S[m] != S[m-1], m++];
S[m] (* Jean-François Alcover, May 12 2022 *)

A341712 a(n) = A120963(2*n)/2.

Original entry on oeis.org

3, 12, 39, 112, 292, 710, 1629, 3567, 7505, 15266, 30140, 57983, 108981, 200625, 362433, 643653, 1125269, 1939149, 3297411, 5538254, 9195371, 15104245, 24561098, 39562657, 63160404, 99987453, 157029090, 244754385, 378754786, 582124254, 888874067, 1348842728

Offset: 1

N. J. A. Sloane, Feb 19 2021

nonn

A bisection of A341710.

Cf. A120963, A341710, A341711.

with(numtheory):
b:= proc(n) option remember; nops(invphi(n)) end:
g:= proc(n) option remember; `if`(n=0, 1, add(
      g(n-j)*add(d*b(d), d=divisors(j)), j=1..n)/n)
    end:
a:= n-> g(2*n)/2:
seq(a(n), n=1..40);  # Alois P. Heinz, Feb 19 2021

terms = 64; (* number of terms of A120963 *)
nmax = Floor[terms/2];
S[m_] := S[m] = CoefficientList[Product[1/(1 - x^EulerPhi[k]),
     {k, 1, m*terms}] + O[x]^(terms+1), x];
S[m = 1];
S[m++];
While[S[m] != S[m-1], m++];
A120963 = S[m];
a[n_ /; 1 <= n <= nmax] := A120963[[2n+1]]/2;
Table[a[n], {n, 1, nmax}] (* Jean-François Alcover, May 12 2022 *)

A360520 a(n) = A120963(n) + A341711(floor(n/2)).

Original entry on oeis.org

2, 3, 11, 15, 43, 57, 137, 177, 389, 495, 1003, 1257, 2421, 3003, 5515, 6771, 12011, 14631, 25143, 30399, 50931, 61197, 100161, 119643, 192051, 228255, 359839, 425631, 660623, 778119, 1190359, 1396479, 2109119, 2465439, 3679263, 4286175, 6327871, 7348719

Offset: 0

N. J. A. Sloane, Mar 02 2023

nonn

			n=4: a(4) = A120963(4) + A341711(2) = 24 + 19 = 43.

Jean-François Alcover, Table of n, a(n) for n = 0..1000

Cf. A120963, A341711.

with(numtheory):
b:= proc(n) option remember; nops(invphi(n)) end:
g:= proc(n) option remember; `if`(n=0, 1, add(
      g(n-j)*add(d*b(d), d=divisors(j)), j=1..n)/n)
    end:
a:= n-> g(n)+g(2*iquo(n, 2)+1)/2:
seq(a(n), n=0..40);  # Alois P. Heinz, Mar 02 2023

b[n_] := b[n] = Length[invphi[n]];
g[n_] := g[n] = If[n == 0, 1, Sum[g[n - j]*Sum[d*b[d], {d, Divisors[j]}], {j, 1, n}]/n];
a[n_] := g[n] + g[2*Quotient[n, 2] + 1]/2;
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Nov 16 2023, after Alois P. Heinz and using Maxim Rytin's invphi program (see A007617) *)

A014197 Number of numbers m with Euler phi(m) = n.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane

Carmichael conjectured that there are no 1's in this sequence. - Jud McCranie, Oct 10 2000
Number of cyclotomic polynomials of degree n. - T. D. Noe, Aug 15 2003
Let v == 0 (mod 24), w = v + 24, and v < k < q < w, where k and q are integer. It seems that, for most values of v, there is no b such that b = a(k) + a(q) and b > a(v) + a(w). The first case where b > a(v) + a(w) occurs at v = 888: b = a(896) + a(900) = 15 + 4, b > a(888) + a(912), or 19 > 8 + 7. The first case where v < n < w and a(n) > a(v) + a(w) occurs at v = 2232: a(2240) > a(2232) + a(2256), or 27 > 7 + 8. - Sergey Pavlov, Feb 05 2017
One elementary result relating to phi(m) is that if m is odd, then phi(m)=phi(2m) because 1 and 2 both have phi value 1 and phi is multiplicative. - Roderick MacPhee, Jun 03 2017

Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section B39, pp. 144-146.
Joe Roberts, Lure of The Integers, The Mathematical Association of America, 1992, entry 32, page 182.

T. D. Noe, Table of n, a(n) for n = 1..10000
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).
R. D. Carmichael, On Euler’s phi-function, Bull. Amer. Math. Soc. 13 (1907), 241-243.
R. D. Carmichael, Note on Euler’s phi-function, Bull. Amer. Math. Soc. 28 (1922), 109-110.
Kevin Ford, The number of solutions of phi(x)=m, arXiv:math/9907204 [math.NT], 1999.
S. Sivasankaranarayana Pillai, On some functions connected with phi(n), Bull. Amer. Math. Soc. 35 (1929), 832-836.
Primefan, Totient Answers For The First 1000 Integers.
Eric Weisstein's World of Mathematics, Totient Function.
Eric Weisstein's World of Mathematics, Totient Valence Function.

Cf. A000010, A002202, A032446 (bisection), A049283, A051894, A055506, A057635, A057826, A058277 (nonzero terms), A058341, A063439, A066412, A070243 (partial sums), A070633, A071386 (positions of odd terms), A071387, A071388 (positions of primes), A071389 (where prime(n) occurs for the first time), A082695, A097942 (positions of records), A097946, A120963, A134269, A219930, A280611, A280709, A280712, A296655 (positions of positive even terms), A305353, A305656, A319048, A322019.
For records see A131934.
Column 1 of array A320000.

a := function(n)
local S, T, R, max, i, k, r;
S:=[];
for i in DivisorsInt(n)+1 do
    if IsPrime(i)=true then
        S:=Concatenation(S,[i]);
    fi;
od;
T:=[];
for k in [1..Size(S)] do
    T:=Concatenation(T,[S[k]/(S[k]-1)]);
od;
max := n*Product(T);
R:=[];
for r in [1..Int(max)] do
    if Phi(r)=n then
        R:=Concatenation(R,[r]);
    fi;
od;
return Size(R);
end; # Miles Englezou, Oct 22 2024

[#EulerPhiInverse(n): n in [1..100]]; // Marius A. Burtea, Sep 08 2019

with(numtheory): A014197:=n-> nops(invphi(n)): seq(A014197(n), n=1..200);

a[1] = 2; a[m_?OddQ] = 0; a[m_] := Module[{p, nmax, n, k}, p = Select[ Divisors[m]+1, PrimeQ]; nmax = m*Times @@ (p/(p - 1)); n = m; k = 0; While[n <= nmax, If[EulerPhi[n] == m, k++]; n++]; k]; Array[a, 92] (* Jean-François Alcover, Dec 09 2011, updated Apr 25 2016 *)
With[{nn = 116}, Function[s, Function[t, Take[#, nn] &@ ReplacePart[t, Map[# -> Length@ Lookup[s, #] &, Keys@ s]]]@ ConstantArray[0, Max@ Keys@ s]]@ KeySort@ PositionIndex@ Array[EulerPhi, Floor[nn^(3/2)] + 10]] (* Michael De Vlieger, Jul 19 2017 *)

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

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

from sympy import totient, divisors, isprime, prod
def a(m):
    if m == 1: return 2
    if m % 2: return 0
    X = (x + 1 for x in divisors(m))
    nmax=m*prod(i/(i - 1) for i in X if isprime(i))
    n=m
    k=0
    while n<=nmax:
        if totient(n)==m:k+=1
        n+=1
    return k
print([a(n) for n in range(1, 51)]) # Indranil Ghosh, Jul 18 2017, after Mathematica code

Dirichlet g.f.: Sum_{n>=1} a(n)*n^-s = zeta(s)*Product_(1+1/(p-1)^s-1/p^s). - Benoit Cloitre, Apr 12 2003
Limit_{n->infinity} (1/n) * Sum_{k=1..n} a(k) = zeta(2)*zeta(3)/zeta(6) = 1.94359643682075920505707036... (see A082695). - Benoit Cloitre, Apr 12 2003
From Christopher J. Smyth, Jan 08 2017: (Start)
Euler transform = Product_{n>=1} (1-x^n)^(-a(n)) = g.f. of A120963.
Product_{n>=1} (1+x^n)^a(n)
= Product_{n>=1} ((1-x^(2n))/(1-x^n))^a(n)
= Product_{n>=1} (1-x^n)^(-A280712(n))
= Euler transform of A280712 = g.f. of A280611.
(End)
a(A000010(n)) = A066412(n). - Antti Karttunen, Jul 18 2017
From Antti Karttunen, Dec 04 2018: (Start)
a(A000079(n)) = A058321(n).
a(A000142(n)) = A055506(n).
a(A017545(n)) = A063667(n).
a(n) = Sum_{d|n} A008683(n/d)*A070633(d).
a(n) = A056239(A322310(n)).
(End)

A280611 Number of degree n products of distinct cyclotomic polynomials.

Original entry on oeis.org

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

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

A280709 The number of monic integer polynomials of degree n all of whose roots are distinct and of modulus at most 1.

Original entry on oeis.org

1, 3, 6, 10, 16, 24, 38, 58, 86, 122, 172, 236, 328, 448, 606, 802, 1060, 1380, 1806, 2338, 3018, 3846, 4900, 6180, 7816, 9808, 12294, 15274, 18982, 23418, 28938, 35542, 43638, 53226, 64942, 78786, 95686, 115642, 139754, 168022, 202086, 241946

Offset: 0

Christopher J. Smyth, Jan 07 2017

Such polynomials are a product of distinct cyclotomic polynomials, possibly multiplied by z. This follows from a classical result of Kronecker -- see Links.

			a(2)=6 because the six polynomials z^2+z+1, z^2+1, z^2-z+1, z^2-z, z^2+z and z^2-1 are the only ones of the required type.

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. A280611 (variant where all roots must have modulus exactly 1);

Cf. A120963 (variant where multiple roots are allowed).

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

a(0) = 1 and a(n) = b(n)+b(n-1) for n >= 1, where b(n) = A280611(n).
G.f.: (1+x)*Product_{i>=1} (1+x^phi(i)) = (1+x)*Product_{j>=1} (1+x^j)^A014197(j), where phi(i)=A000010(i) is Euler's totient function.
It is also the Euler transform of A280712 except with its first two terms (2,1) replaced by (3,0).
a(n) ~ exp(sqrt(105*zeta(3)*n/2)/Pi) * (105*zeta(3)/2)^(1/4) / (2*Pi*n^(3/4)). - Vaclav Kotesovec, Sep 02 2021

A305353 Expansion of Product_{k>=1} (1 - x^phi(k)), where phi is Euler's totient function.

Original entry on oeis.org

1, -2, -2, 6, -4, 2, 6, -14, 8, -2, 4, -6, -16, 38, -22, 6, 2, -10, 2, 6, 60, -126, 28, 70, -38, 6, -38, 70, -54, 38, 18, -74, -70, 214, 106, -426, 186, 54, -26, -2, -92, 186, -218, 250, -66, -118, -104, 326, 466, -1258, 500, 258, -254, 250, -368, 486, -342, 198

Offset: 0

Seiichi Manyama, May 31 2018

sign

Cf. A000010 (phi), A014197, A120963, A280611.

terms = 58;
S[m_] := S[m] = CoefficientList[Product[1 - x^EulerPhi[k],
     {k, 1, m*terms}] + O[x]^terms, x];
S[m = 1];
S[m++];
While[S[m] != S[m - 1], m++];
S[m] (* Jean-François Alcover, May 12 2022 *)

Product_{k>=1} (1 - x^k)^A014197(k).

A347428 Expansion of g.f. Product_{k>=2} 1/(1-x^phi(k)).

Original entry on oeis.org

1, 1, 4, 4, 14, 14, 40, 40, 106, 106, 254, 254, 582, 582, 1256, 1256, 2620, 2620, 5256, 5256, 10266, 10266, 19482, 19482, 36204, 36204, 65792, 65792, 117496, 117496, 206120, 206120, 356320, 356320, 606912, 606912, 1020848, 1020848, 1695676, 1695676, 2786010

Offset: 0

Michel Marcus, Sep 02 2021

nonn

Vaclav Kotesovec, Table of n, a(n) for n = 0..10000
David P. Roberts and Fernando Rodriguez Villegas, Hypergeometric Motives, arXiv:2109.00027 [math.AG], 2021. See (5.2) p. 6.

Cf. A000010 (phi), A014197, A051894, A120963 (similar g.f.).

with(numtheory):
b:= proc(n) option remember; nops(invphi(n)) end:
g:= proc(n) option remember; `if`(n=0, 1, add(
      g(n-j)*add(d*b(d), d=divisors(j)), j=1..n)/n)
    end:
a:= n-> g(n)-g(n-1):
seq(a(n), n=0..40);  # Alois P. Heinz, Jun 23 2023

nt = 100; (* number of terms *)
f[kmax_] := f[kmax] = CoefficientList[Product[1/(1 - x^EulerPhi[k]), {k, 2, kmax}] + O[x]^nt, x]; f[kmax = nt]; f[kmax += nt];
While[f[kmax] != f[kmax - nt], kmax += nt];
f[kmax] (* Jean-François Alcover, Nov 29 2023 *)

From Vaclav Kotesovec, Sep 02 2021: (Start)
For n>0, a(n) = A120963(n) - A120963(n-1).
log(a(n)) ~ sqrt(105*zeta(3)*n)/Pi. (End)

Terms a(16) and beyond corrected by Vaclav Kotesovec, Jun 23 2023, following a suggestion from Georg Fischer

cp's OEIS Frontend

A341711 a(n) = A120963(2*n+1)/2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A341710 a(n) = A120963(n)/2.

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

A341712 a(n) = A120963(2*n)/2.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Mathematica

A360520 a(n) = A120963(n) + A341711(floor(n/2)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A014197 Number of numbers m with Euler phi(m) = n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

PARI

Python

Formula

A280611 Number of degree n products of distinct cyclotomic polynomials.

Views

Author

Keywords

Comments

Examples

References

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