A029935 -id:A029935 - cp's OEIS frontend

A018804 Pillai's arithmetical function: Sum_{k=1..n} gcd(k, n).

1, 3, 5, 8, 9, 15, 13, 20, 21, 27, 21, 40, 25, 39, 45, 48, 33, 63, 37, 72, 65, 63, 45, 100, 65, 75, 81, 104, 57, 135, 61, 112, 105, 99, 117, 168, 73, 111, 125, 180, 81, 195, 85, 168, 189, 135, 93, 240, 133, 195, 165, 200, 105, 243, 189, 260, 185, 171, 117, 360

Offset: 1

David W. Wilson

a(n) is the number of times the number 1 appears in the character table of the cyclic group C_n. - Ahmed Fares (ahmedfares(AT)my-deja.com), Jun 02 2001
a(n) is the number of ways to express all fractions f/g whereby each product (f/g)*n is a natural number between 1 and n (using fractions of the form f/g with 1 <= f,g <= n). For example, for n=4 there are 8 such fractions: 1/1, 1/2, 2/2, 3/3, 1/4, 2/4, 3/4 and 4/4. - Ron Lalonde (ronronronlalonde(AT)hotmail.com), Oct 03 2002
Number of non-congruent solutions to xy == 0 (mod n). - Yuval Dekel (dekelyuval(AT)hotmail.com), Oct 06 2003
Conjecture: n>1 divides a(n)+1 iff n is prime. - Thomas Ordowski, Oct 22 2014
The above conjecture is false, with counterexample given by n = 3*37*43*42307*116341 and a(n)+1 = 26*n. - Varun Vejalla, Jun 19 2025
a(n) is the number of 0's in the multiplication table Z/nZ (cf. A000010 for number of 1's). - Eric Desbiaux, Jun 11 2015
{a(n)} == 1, 3, 1, 0, 1, 3, 1, 0, ... (mod 4). - Isaac Saffold, Dec 30 2017
Since a(p^e) = p^(e-1)*((p-1)e+p) it follows a(p) = 2p-1 and therefore p divides a(p)+1. - Ruediger Jehn, Jun 23 2022

			G.f. = x + 3*x^2 + 5*x^3 + 8*x^4 + 9*x^5 + 15*x^6 + 13*x^7 + 20*x^8 + ...

S. S. Pillai, On an arithmetic function, J. Annamalai University 2 (1933), pp. 243-248.
J. Sándor, A generalized Pillai function, Octogon Mathematical Magazine Vol. 9, No. 2 (2001), 746-748.

Seiichi Manyama, Table of n, a(n) for n = 1..10000 (first 2000 terms from T. D. Noe)
U. Abel, W. Awan, and V. Kushnirevych, A Generalization of the Gcd-Sum Function, J. Int. Seq. 16 (2013) #13.6.7.
Antal Bege, Hadamard product of GCD matrices, Acta Univ. Sapientiae, Mathematica, 1, 1 (2009) 43-49.
Olivier Bordelles, The Composition of the gcd and Certain Arithmetic Functions, J. Int. Seq. 13 (2010) #10.7.1.
Olivier Bordelles, An Asymptotic Formula for Short Sums of Gcd-Sum Functions, Journal of Integer Sequences, Vol. 15 (2012), #12.6.8.
Olivier Bordelles, A Multidimensional Cesáro Type Identity and Applications, J. Int. Seq. 18 (2015) # 15.3.7.
Kevin A. Broughan, The gcd-sum function, Journal of Integer Sequences 4 (2001), Article 01.2.2, 19 pp.
J.-M. De Koninck and I. Kátai, Some remarks on a paper of L. Toth, JIS 13 (2010) 10.1.2.
Pentti Haukkanen and László Tóth, Menon-type identities again: Note on a paper by Li, Kim and Qiao, arXiv:1911.05411 [math.NT], 2019.
Soichi Ikeda and Kaneaki Matsuoka, On the Lcm-Sum Function, Journal of Integer Sequences, Vol. 17 (2014), Article 14.1.7.
Mathematical Reflections, Solution to Problem O364, Issue 2, 2016, p 24. [Cached copy at Wayback Machine]
Taylor McAdam, Almost-primes in horospherical flows on the space of lattices, arXiv:1802.08764 [math.DS], 2018.
Taylor McAdam, Almost-prime times in horospherical flows on the space of lattices, Journal of Modern Dynamics (2019) Vol. 15, 277-327.
J. Ransford, A Sum of Gcd’s over Friable Numbers, JIS vol 19 (2016) # 16.3.2
Jeffrey Shallit, Problem E 2821, American Mathematical Monthly 87 (1980), 220.
Jeffrey Shallit, Solution, American Mathematical Monthly, 88 (1981), 444-445.
László Tóth, A gcd-sum function over regular integers modulo n, JIS 12 (2009) 09.2.5.
László Tóth, On the Bi-Unitary Analogues of Euler's Arithmetical Function and the Gcd-Sum Function, JIS 12 (2009) 09.5.2.
László Tóth, A survey of gcd-sum functions, J. Integer Sequences 13 (2010), Article 10.8.1, 23 pp.
László Tóth, Weighted gcd-sum functions, J. Integer Sequences, 14 (2011), Article 11.7.7.
D. Zhang and W. Zhai, Mean Values of a Gcd-Sum Function Over Regular Integers Modulo n, J. Int. Seq. 13 (2010), 10.4.7.
D. Zhang and W. Zhai, Mean Values of a Class of Arithmetical Functions, J. Int. Seq. 14 (2011) #11.6.5.
D. Zhang and W. Zhai, On an Open Problem of Tóth, J. Int. Seq. 16 (2013) #13.6.5.

Column 1 of A343510 and A343516.
Cf. A080997, A080998 for rankings of the positive integers in terms of centrality, defined to be the average fraction of an integer that it shares with the other integers as a gcd, or A018804(n)/n^2, also A080999, a permutation of this sequence (A080999(n) = A018804(A080997(n))).
Cf. A185210, A010766, A054523, A127468, A050873, A078430, A095026, A227507, A000010, A344372, A272718 (partial sums), A368736 - A368741.

a018804 n = sum $ map (gcd n) [1..n]  -- Reinhard Zumkeller, Jul 16 2012

[&+[Gcd(n,k):k in [1..n]]:n in [1..60]]; // Marius A. Burtea, Nov 14 2019

a:=n->sum(igcd(n,j),j=1..n): seq(a(n), n=1..60); # Zerinvary Lajos, Nov 05 2006

f[n_] := Block[{d = Divisors[n]}, Sum[ d*EulerPhi[n/d], {d, d}]]; Table[f[n], {n, 60}] (* Robert G. Wilson v, Mar 20 2012 *)
a[ n_] := If[ n < 1, 0, n Sum[ EulerPhi[d] / d, {d, Divisors@n}]]; (* Michael Somos, Jan 07 2017 *)
f[p_, e_] := (e*(p - 1)/p + 1)*p^e; a[n_] := Times @@ (f @@@ FactorInteger[n]); Array[a, 100] (* Amiram Eldar, Jul 19 2019 *)

{a(n) = direuler(p=2, n, (1 - X) / (1 - p*X)^2)[n]}; /* Michael Somos, May 31 2000 */

a(n)={ my(ct=0); for(i=0,n-1,for(j=0,n-1, ct+=(Mod(i*j,n)==0) ) ); ct; } \\ Joerg Arndt, Aug 03 2013

a(n)=my(f=factor(n)); prod(i=1,#f~,(f[i,2]*(f[i,1]-1)/f[i,1] + 1)*f[i,1]^f[i,2]) \\ Charles R Greathouse IV, Oct 28 2014

a(n) = sumdiv(n, d, n*eulerphi(d)/d); \\ Michel Marcus, Jan 07 2017

from sympy.ntheory import totient, divisors
print([sum(n*totient(d)//d for d in divisors(n)) for n in range(1, 101)]) # Indranil Ghosh, Apr 04 2017

from sympy import factorint
from math import prod
def A018804(n): return prod(p**(e-1)*((p-1)*e+p) for p, e in factorint(n).items()) # Chai Wah Wu, Nov 29 2021

a(n) = Sum_{d|n} d*phi(n/d), where phi(n) is Euler totient function (cf. A000010). - Vladeta Jovovic, Apr 04 2001
Multiplicative; for prime p, a(p^e) = p^(e-1)*((p-1)e+p).
Dirichlet g.f.: zeta(s-1)^2/zeta(s).
a(n) = Sum_{d|n} d*tau(d)*mu(n/d). - Benoit Cloitre, Oct 23 2003
Equals A054523 * [1,2,3,...]. Equals row sums of triangle A010766. - Gary W. Adamson, May 20 2007
Equals inverse Mobius transform of A029935 = A054525 * (1, 2, 4, 5, 8, 8, 12, 12, ...). - Gary W. Adamson, Aug 02 2008, corrected Feb 07 2023
Equals row sums of triangle A127478. - Gary W. Adamson, Aug 03 2008
G.f.: Sum_{k>=1} phi(k)*x^k/(1 - x^k)^2, where phi(k) is the Euler totient function. - Ilya Gutkovskiy, Jan 02 2017
a(n) = Sum_{a = 1..n} Sum_{b = 1..n} Sum_{c = 1..n} 1, for n > 1. The sum is over a,b,c such that n*c - a*b = 0. - Benedict W. J. Irwin, Apr 04 2017
Proof: Let gcd(a, n) = g and x = n/g. Define B = {x, 2*x, ..., g*x}; then for all b in B there exists a number c such that a*b = n*c. Since the set B has g elements it follows that Sum_{b=1..n} Sum_{c=1..n} 1 >= g = gcd(a, n) and therefore Sum_{a=1..n} Sum_{b=1..n} Sum_{c=1..n} 1 >= Sum_{a=1..n} gcd(a, n). On the other hand, for all b not in B there is no number c <= n such that a*b = n*c and hence Sum_{b = 1..n} Sum_{c = 1..n} 1 = g. Therefore Sum_{a=1..n} Sum_{b = 1..n} Sum_{c = 1..n} 1 = a(n). - Ruediger Jehn, Jun 23 2022
a(2*n) = a(n)*(3-A007814(n)/(A007814(n)+2)) - Velin Yanev, Jun 30 2017
Proof: Let m = A007814(m) and decompose n into n = k*2^m. We know from Chai Wah Wu's program below that a(n) = Product(p_i^(e_i-1)*((p_i-1)*e_i+p_i)) where the numbers p_i are the prime factors of n and e_i are the corresponding exponents. Hence a(2n) = 2^m*(m+3)*a(k) = 2^m*(m+3)*a(k). On the other hand, a(n) = 2^(m-1)*(m+2)*a(k). Dividing the first equation by the second yields a(2n)/a(n) = 2*(m+3)/(m+2), which equals 3 - m/(m+2). Hence a(2n) = a(n)*(3 - m/(m+2)). - Ruediger Jehn, Jun 23 2022
Sum_{k=1..n} a(k) ~ 3*n^2/Pi^2 * (log(n) - 1/2 + 2*gamma - 6*Zeta'(2)/Pi^2), where gamma is the Euler-Mascheroni constant A001620. - Vaclav Kotesovec, Feb 08 2019
a(n) = Sum_{k=1..n} n/gcd(n,k)*phi(gcd(n,k))/phi(n/gcd(n,k)). - Richard L. Ollerton, May 10 2021
log(a(n)/n) << log n log log log n/log log n; in particular, a(n) << n^(1+e) for any e > 0. See Broughan link for bounds in terms of omega(n). - Charles R Greathouse IV, Sep 08 2022
a(n) = (1/4)*Sum_{k = 1..4*n} (-1)^k * gcd(k, 4*n) = (1/4) * A344372(2*n). - Peter Bala, Jan 01 2024

A038040 a(n) = n*d(n), where d(n) = number of divisors of n (A000005).

Original entry on oeis.org

1, 4, 6, 12, 10, 24, 14, 32, 27, 40, 22, 72, 26, 56, 60, 80, 34, 108, 38, 120, 84, 88, 46, 192, 75, 104, 108, 168, 58, 240, 62, 192, 132, 136, 140, 324, 74, 152, 156, 320, 82, 336, 86, 264, 270, 184, 94, 480, 147, 300, 204, 312, 106, 432, 220, 448, 228, 232, 118

Offset: 1

Christian G. Bower

Dirichlet convolution of sigma(n) (A000203) with phi(n) (A000010). - Michael Somos, Jun 08 2000
Dirichlet convolution of f(n)=n with itself. See the Apostol reference for Dirichlet convolutions. - Wolfdieter Lang, Sep 09 2008
Sum of all parts of all partitions of n into equal parts. - Omar E. Pol, Jan 18 2013

			For n = 6 the partitions of 6 into equal parts are [6], [3, 3], [2, 2, 2], [1, 1, 1, 1, 1, 1]. The sum of all parts is 6 + 3 + 3 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 = 24 equalling 6 times the number of divisors of 6, so a(6) = 24. - _Omar E. Pol_, May 08 2021

Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, pp. 29 ff.
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 162.

T. D. Noe, Table of n, a(n) for n = 1..1000
J. Bourgain, S. V. Konyagin and I. E. Shparlinski, Product sets of rationals, multiplicative translates of subgroups in residue rings and fixed points of the discrete logarithms, Int. Math. Res. Notices, 2008 (2008), Art. ID rnn 090, 1-29.
Jean Bourgain, Sergei Konyagin and Igor Shparlinski. Distribution on elements of cosets of small subgroups and applications, arXiv:1103.0567 [math.NT], Mar 2 2011.
Mikhail R. Gabdullin and Vitalii V. Iudelevich, Numbers of the form kf(k), arXiv:2201.09287 [math.NT] (2022).
Passawan Noppakaew and Prapanpong Pongsriiam, Product of Some Polynomials and Arithmetic Functions, J. Int. Seq. (2023) Vol. 26, Art. 23.9.1.
Paul Pollack, Analytic and Combinatorial Number Theory Course Notes, p. 147. [Broken link?]
Paul Pollack, Analytic and Combinatorial Number Theory Course Notes, p. 147.

Cf. A000005, A000010, A000203, A001620, A018804, A029935, A064987, A062952.
Cf. A127648, A127093, A127528.
Cf. A038044, A143127 (partial sums), A328722 (Dirichlet inverse).
Column 1 of A329323.

a038040 n = a000005 n * n  -- Reinhard Zumkeller, Jan 21 2014

with(numtheory): A038040 := n->tau(n)*n;

a[n_] := DivisorSigma[0, n]*n; Table[a[n], {n, 1, 60}] (* Jean-François Alcover, Sep 03 2012 *)

n*numlib::tau (n)$ n=1..90 // Zerinvary Lajos, May 13 2008

a(n)=if(n<1,0,direuler(p=2,n,1/(1-p*X)^2)[n])

a(n)=if(n<1,0,polcoeff(sum(k=1,n,k*x^k/(x^k-1)^2,x*O(x^n)),n)) /* Michael Somos, Jan 29 2005 */

a(n) = n*numdiv(n); \\ Michel Marcus, Oct 24 2020

from sympy import divisor_count as d
def a(n): return n*d(n)
print([a(n) for n in range(1, 60)]) # Michael S. Branicky, Mar 15 2022

[n*sigma(n,0) for n in range(1, 60)] # Stefano Spezia, Jul 20 2025

Dirichlet g.f.: zeta(s-1)^2.
G.f.: Sum_{n>=1} n*x^n/(1-x^n)^2. - Vladeta Jovovic, Dec 30 2001
Sum_{k=1..n} sigma(gcd(n, k)). Multiplicative with a(p^e) = (e+1)*p^e. - Vladeta Jovovic, Oct 30 2001
Equals A127648 * A127093 * the harmonic series, [1/1, 1/2, 1/3, ...]. - Gary W. Adamson, May 10 2007
Equals row sums of triangle A127528. - Gary W. Adamson, May 21 2007
a(n) = n*A000005(n) = A066186(n) - n*(A000041(n) - A000005(n)) = A066186(n) - n*A144300(n). - Omar E. Pol, Jan 18 2013
a(n) = A000203(n) * A240471(n) + A106315(n). - Reinhard Zumkeller, Apr 06 2014
L.g.f.: Sum_{k>=1} x^k/(1 - x^k) = Sum_{n>=1} a(n)*x^n/n. - Ilya Gutkovskiy, May 13 2017
a(n) = Sum_{d|n} A018804(d). - Amiram Eldar, Jun 23 2020
a(n) = Sum_{d|n} phi(d)*sigma(n/d). - Ridouane Oudra, Jan 21 2021
G.f.: Sum_{n >= 1} q^(n^2)*(n^2 + 2*n*q^n - n^2*q^(2*n))/(1 - q^n)^2. - Peter Bala, Jan 22 2021
a(n) = Sum_{k=1..n} sigma(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). - Richard L. Ollerton, May 07 2021
Define f(x) = #{n <= x: a(n) <= x}. Gabdullin & Iudelevich show that f(x) ~ x/sqrt(log x). That is, there are 0 < A < B such that Ax/sqrt(log x) < f(x) < Bx/sqrt(log x). - Charles R Greathouse IV, Mar 15 2022
Sum_{k=1..n} a(k) ~ n^2*log(n)/2 + (gamma - 1/4)*n^2, where gamma is Euler's constant (A001620). - Amiram Eldar, Oct 25 2022
Mobius transform of A060640. - R. J. Mathar, Feb 07 2023

A054523 Triangle read by rows: T(n,k) = phi(n/k) if k divides n, T(n,k)=0 otherwise (n >= 1, 1 <= k <= n).

Original entry on oeis.org

1, 1, 1, 2, 0, 1, 2, 1, 0, 1, 4, 0, 0, 0, 1, 2, 2, 1, 0, 0, 1, 6, 0, 0, 0, 0, 0, 1, 4, 2, 0, 1, 0, 0, 0, 1, 6, 0, 2, 0, 0, 0, 0, 0, 1, 4, 4, 0, 0, 1, 0, 0, 0, 0, 1, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 4, 2, 2, 2, 0, 1, 0, 0, 0, 0, 0, 1, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 6, 6

Offset: 1

N. J. A. Sloane, Apr 09 2000

From Gary W. Adamson, Jan 08 2007: (Start)
Let H be this lower triangular matrix. Then:
H * A051731 = A126988,
H * [1, 2, 3, ...] = 1, 3, 5, 8, 9, 15, ... = A018804,
H * sigma(n) = A038040 = d(n) * n = 1, 4, 6, 12, 10, ... where sigma(n) = A000203,
H * d(n) (A000005) = sigma(n) = A000203,
Row sums are A000027 (corrected by Werner Schulte, Sep 06 2020, see comment of Gary W. Adamson, Aug 03 2008),
H^2 * d(n) = d(n)*n, H^2 = A127192,
H * mu(n) (A008683) = A007431(n) (corrected by Werner Schulte, Sep 06 2020),
H^2 row sums = A018804. (End)
The Möbius inversion principle of Richard Dedekind and Joseph Liouville (1857), cf. "Concrete Mathematics", p. 136, is equivalent to the statement that row sums are the row index n. - Gary W. Adamson, Aug 03 2008
The multivariable row polynomials give n times the cycle index for the cyclic group C_n, called Z(C_n) (see the MathWorld link with the Harary reference): n*Z(C_n) = Sum_{k=1..n} T(n,k)*(y_{n/k})^k, n >= 1. E.g., 6*Z(C_6) = 2*(y_6)^1 + 2*(y_3)^2 + 1*(y_2)^3 + 1*(y_1)^6. - Wolfdieter Lang, May 22 2012
See A102190 (no 0's, rows reversed). - Wolfdieter Lang, May 29 2012
This is the number of permutations in the n-th cyclic group which are the product of k disjoint cycles. - Robert A. Beeler, Aug 09 2013

			Triangle begins
   1;
   1, 1;
   2, 0, 1;
   2, 1, 0, 1;
   4, 0, 0, 0, 1;
   2, 2, 1, 0, 0, 1;
   6, 0, 0, 0, 0, 0, 1;
   4, 2, 0, 1, 0, 0, 0, 1;
   6, 0, 2, 0, 0, 0, 0, 0, 1;
   4, 4, 0, 0, 1, 0, 0, 0, 0, 1;
  10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1;
   4, 2, 2, 2, 0, 1, 0, 0, 0, 0, 0, 1;

Ronald L. Graham, D. E. Knuth, Oren Patashnik, Concrete Mathematics, Addison-Wesley, 2nd ed., 1994, p. 136.

Reinhard Zumkeller, Rows n = 1..125 of triangle, flattened
Eric Weisstein's World of Mathematics, Cycle Index.

Cf. A000005, A000007, A000010, A000012, A000203, A007431, A008683.
Cf. A038040, A051731, A054521, A054525, A102190, A126988.
Sums incliude: A029935, A069097, A092843 (diagonal), A209295.
Sums of the form Sum_{k} k^p * T(n, k): A000027 (p=0), A018804 (p=1), A069097 (p=2), A343497 (p=3), A343498 (p=4), A343499 (p=5).

a054523 n k = a054523_tabl !! (n-1) !! (k-1)
a054523_row n = a054523_tabl !! (n-1)
a054523_tabl = map (map (\x -> if x == 0 then 0 else a000010 x)) a126988_tabl
-- Reinhard Zumkeller, Jan 20 2014

A054523:= func< n,k | k eq n select 1 else (n mod k) eq 0 select EulerPhi(Floor(n/k)) else 0 >;
[A054523(n,k): k in [1..n], n in [1..15]]; // G. C. Greubel, Jun 24 2024

A054523 := proc(n,k) if n mod k = 0 then numtheory[phi](n/k) ; else 0; end if; end proc: # R. J. Mathar, Apr 11 2011

T[n_, k_]:= If[k==n,1,If[Divisible[n, k], EulerPhi[n/k], 0]];
Table[T[n,k], {n,15}, {k,n}]//Flatten (* G. C. Greubel, Dec 15 2017 *)

for(n=1, 10, for(k=1, n, print1(if(!(n % k), eulerphi(n/k), 0), ", "))) \\ G. C. Greubel, Dec 15 2017

def A054523(n,k):
    if (k==n): return 1
    elif (n%k)==0: return euler_phi(int(n//k))
    else: return 0
flatten([[A054523(n,k) for k in range(1,n+1)] for n in range(1,16)]) # G. C. Greubel, Jun 24 2024

Sum_{k=1..n} k * T(n, k) = A018804(n). - Gary W. Adamson, Jan 08 2007
Equals A054525 * A126988 as infinite lower triangular matrices. - Gary W. Adamson, Aug 03 2008
From Werner Schulte, Sep 06 2020: (Start)
Sum_{k=1..n} T(n,k) * A000010(k) = A029935(n) for n > 0.
Sum_{k=1..n} k^2 * T(n,k) = A069097(n) for n > 0. (End)
From G. C. Greubel, Jun 24 2024: (Start)
T(2*n-1, n) = A000007(n-1), n >= 1.
T(2*n, n) = A000012(n), n >= 1.
Sum_{k=1..n} (-1)^(k-1)*T(n, k) = (1 - (-1)^n)*n/2.
Sum_{k=1..floor(n+1)/2} T(n-k+1, k) = A092843(n+1).
Sum_{k=1..n} (k+1)*T(n, k) = A209295(n).
Sum_{k=1..n} k^3 * T(n, k) = A343497(n).
Sum_{k=1..n} k^4 * T(n, k) = A343498(n).
Sum_{k=1..n} k^5 * T(n, k) = A343499(n). (End)

A299150 Denominators of the positive solution to n = Sum_{d|n} a(d) * a(n/d).

Original entry on oeis.org

1, 1, 2, 2, 2, 2, 2, 2, 8, 2, 2, 4, 2, 2, 4, 8, 2, 8, 2, 4, 4, 2, 2, 4, 8, 2, 16, 4, 2, 4, 2, 8, 4, 2, 4, 16, 2, 2, 4, 4, 2, 4, 2, 4, 16, 2, 2, 16, 8, 8, 4, 4, 2, 16, 4, 4, 4, 2, 2, 8, 2, 2, 16, 16, 4, 4, 2, 4, 4, 4, 2, 16, 2, 2, 16, 4, 4, 4, 2, 16, 128, 2, 2

Offset: 1

Gus Wiseman, Feb 03 2018

			Sequence begins: 1, 1, 3/2, 3/2, 5/2, 3/2, 7/2, 5/2, 27/8, 5/2, 11/2, 9/4, 13/2, 7/2.

Antti Karttunen, Table of n, a(n) for n = 1..65537 (first 1000 terms from Andrew Howroyd)

Cf. A000010, A003958, A005187, A006519, A007431, A011371, A018804, A023900, A029935, A037445, A046643, A046644, A165825, A257098, A298971, A299119, A299149 (numerators), A299151, A317848, A317929, A317932, A318314, A318512, A318653, A318681.

Cf. A318440 (the 2-adic valuation).

nn=50;
sys=Table[n==Sum[a[d]*a[n/d],{d,Divisors[n]}],{n,nn}];
Denominator[Array[a,nn]/.Solve[sys,Array[a,nn]][[2]]]
f[p_, e_] := 2^((1 + Mod[p, 2])*e - DigitCount[e, 2, 1]); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Apr 28 2023 *)

a(n)={my(v=factor(n)[,2]); denominator(n*prod(i=1, #v, my(e=v[i]); binomial(2*e, e)/4^e))} \\ Andrew Howroyd, Aug 09 2018

A299150(n) = { my(f = factor(n), m=1); for(i=1, #f~, m *= 2^(((1+(f[i,1]%2))*f[i,2]) - hammingweight(f[i,2]))); (m); }; \\ Antti Karttunen, Sep 03 2018

for(n=1, 100, print1(denominator(direuler(p=2, n, 1/(1-p*X)^(1/2))[n]), ", ")) \\ Vaclav Kotesovec, May 08 2025

a(n) = denominator(n*A317848(n)/A165825(n)) = A165825(n)/(A037445(n) * A006519(n)). - Andrew Howroyd, Aug 09 2018
a(n) = A046644(n)/A006519(n). - Andrew Howroyd and Antti Karttunen, Aug 30 2018
From Antti Karttunen, Sep 03 2018: (Start)
a(n) = 2^A318440(n).
Multiplicative with a(2^e) = 2^A011371(e), a(p^e) = 2^A005187(e) for odd primes p.
Multiplicative with a(p^e) = 2^(((1+A000035(p))*e)-A000120(e)) for all primes p.
(End)

Keyword:mult added by Andrew Howroyd, Aug 09 2018

A299149 Numerators of the positive solution to n = Sum_{d|n} a(d) * a(n/d).

Original entry on oeis.org

1, 1, 3, 3, 5, 3, 7, 5, 27, 5, 11, 9, 13, 7, 15, 35, 17, 27, 19, 15, 21, 11, 23, 15, 75, 13, 135, 21, 29, 15, 31, 63, 33, 17, 35, 81, 37, 19, 39, 25, 41, 21, 43, 33, 135, 23, 47, 105, 147, 75, 51, 39, 53, 135, 55, 35, 57, 29, 59, 45, 61, 31, 189, 231, 65, 33

Offset: 1

Gus Wiseman, Feb 03 2018

Dirichlet convolution of a(n)/A046644(n) with itself yields A000265. - Antti Karttunen, Aug 30 2018

			Sequence begins: 1, 1, 3/2, 3/2, 5/2, 3/2, 7/2, 5/2, 27/8, 5/2, 11/2, 9/4, 13/2, 7/2.

Antti Karttunen, Table of n, a(n) for n = 1..65537 (first 1000 terms Andrew Howroyd)
Vaclav Kotesovec, Graph - the asymptotic ratio (65537 terms)
Wikipedia, Dirichlet convolution.

Cf. A000010, A000265, A003958, A007431, A018804, A023900, A029935, A046643, A046644, A165825, A257098, A298971, A299119, A299150 (denominators), A299151, A317848, A318319, A318321, A318649.

nn=50;
sys=Table[n==Sum[a[d]*a[n/d],{d,Divisors[n]}],{n,nn}];
Numerator[Array[a,nn]/.Solve[sys,Array[a,nn]][[2]]]
odd[n_] := n/2^IntegerExponent[n, 2]; f[p_, e_] := odd[p^e*Binomial[2*e, e]]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Apr 30 2023 *)

a(n)={my(v=factor(n)[,2]); numerator(n*prod(i=1, #v, my(e=v[i]); binomial(2*e, e)/4^e))} \\ Andrew Howroyd, Aug 09 2018

\\ DirSqrt(v) finds u such that v = v[1]*dirmul(u, u).
DirSqrt(v)={my(n=#v, u=vector(n)); u[1]=1; for(n=2, n, u[n]=(v[n]/v[1] - sumdiv(n, d, if(d>1&&dAndrew Howroyd, Aug 09 2018

for(n=1, 100, print1(numerator(direuler(p=2, n, 1/(1-p*X)^(1/2))[n]), ", ")) \\ Vaclav Kotesovec, May 09 2025

a(n) = numerator(n*A317848(n)/A165825(n)) = A000265(n*A317848(n)). - Andrew Howroyd, Aug 09 2018

Sum_{k=1..n} A299149(k)/A299150(k) ~ n^2 / (2*sqrt(Pi*log(n))) * (1 + (1-gamma) / (4*log(n))), where gamma is the Euler-Mascheroni constant A001620. - Vaclav Kotesovec, May 09 2025

Keyword:mult added by Andrew Howroyd, Aug 09 2018

A299151 Numerators of the positive solution to 2^(n-1) = Sum_{d|n} a(d) * a(n/d).

Original entry on oeis.org

1, 1, 2, 7, 8, 14, 32, 121, 126, 248, 512, 1003, 2048, 4064, 8176, 130539, 32768, 65382, 131072, 261868, 524224, 1048064, 2097152, 4193131, 8388576, 16775168, 33554180, 67104688, 134217728, 268426672, 536870912, 8589802359, 2147482624, 4294934528, 8589934336, 17179801257, 34359738368, 68719345664, 137438949376, 274877643724, 549755813888

Offset: 1

Gus Wiseman, Feb 03 2018

Numerators of rational valued sequence f whose Dirichlet convolution with itself yields function g(n) = A000079(n-1) = 2^(n-1). - Antti Karttunen, Aug 10 2018

			Sequence begins: 1, 1, 2, 7/2, 8, 14, 32, 121/2, 126, 248, 512, 1003, 2048, 4064, 8176, 130539/8, 32768.

Andrew Howroyd, Table of n, a(n) for n = 1..1000

Cf. A000005, A000010, A000740, A018804, A023900, A029935, A034691, A046643, A059966, A228369, A257098, A296302, A298971, A299119, A299149, A299152.

Cf. also A317831.

nn=50;
sys=Table[2^(n-1)==Sum[a[d]*a[n/d],{d,Divisors[n]}],{n,nn}];
Numerator[Array[a,nn]/.Solve[sys,Array[a,nn]][[2]]]

A299151perA299152(n) = if(1==n,n,(2^(n-1)-sumdiv(n,d,if((d>1)&&(dA299151perA299152(d)*A299151perA299152(n/d),0)))/2);
A299151(n) = numerator(A299151perA299152(n));

More terms from Antti Karttunen, Jul 29 2018

A029937 Genus of modular curve X_1(n).

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 2, 1, 1, 2, 5, 2, 7, 3, 5, 6, 12, 5, 12, 10, 13, 10, 22, 9, 26, 17, 21, 21, 25, 17, 40, 28, 33, 25, 51, 25, 57, 36, 41, 45, 70, 37, 69, 48, 65, 55, 92, 52, 81, 61, 85, 78, 117, 57, 126, 91, 97

Offset: 1

N. J. A. Sloane

Also the dimension of the space of cusp forms of weight two on Gamma1(n). [Steven Finch, Apr 03 2009]

F. Hirzebruch et al., Manifolds and Modular Forms, Vieweg, 2nd ed. 1994, p. 161.

T. D. Noe, Table of n, a(n) for n = 1..1000
S. R. Finch, Modular forms on SL_2(Z), December 28, 2005. [Cached copy, with permission of the author]
Chang Heon Kim, Ja Kyung Koo, On the genus of some modular curves of level N, Bull Austral. Math. Soc. 54 (1996) 291-297.
A. V. Sutherland, Torsion subgroups of elliptic curves over number fields, 2012. - From _N. J. A. Sloane_, Feb 03 2013

Cf. A001617, A029938. [Steven Finch, Apr 03 2009]

with(numtheory); A029937 := proc(n) local i,j; j := 1+(1/24)*phi(n)*A001615(n); for i in divisors(n) do j := j-(1/4)*phi(i)*phi(n/i) od; j; end;

a[n_ /; n<5] = 0; a[n_] := 1+Sum[d^2*MoebiusMu[n/d]/24 - EulerPhi[d]*EulerPhi[n/d]/4, {d, Divisors[n]}]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Jan 13 2014 *)

A029935(n) = {
  my(f = factor(n), fsz = matsize(f)[1],
     g = prod(k=1, fsz, f[k,1]),
     h = prod(k=1, fsz, sqr(f[k,1]-1)*f[k,2] + sqr(f[k,1])-1));
  return(h*n\sqr(g));
};
a(n) = {
  if (n < 5, return(0));
  my(f = factor(n), fsz = matsize(f)[1],
     g = prod(k=1, fsz, f[k,1]),
     h = prod(k=1, fsz, sqr(f[k,1]) - 1));
  return(1 + sqr(n\g)*h/24 - A029935(n)/4);
};
vector(63, n, a(n))  \\ Gheorghe Coserea, Oct 23 2016

a(n) = 1 + A115000(n) - A029935(n)/4, n > 4. [Kim and Koo, Theorem 1]

cp's OEIS Frontend

A143275 A054525 * A029935.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A127374 Triangle, row sums = A029935.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A018804 Pillai's arithmetical function: Sum_{k=1..n} gcd(k, n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Python

Formula

A038040 a(n) = n*d(n), where d(n) = number of divisors of n (A000005).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

MuPAD

PARI

PARI

PARI

Python

SageMath

Formula

A054523 Triangle read by rows: T(n,k) = phi(n/k) if k divides n, T(n,k)=0 otherwise (n >= 1, 1 <= k <= n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

SageMath

Formula

A299150 Denominators of the positive solution to n = Sum_{d|n} a(d) * a(n/d).