cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 11 results. Next

A222548 a(n) = Sum_{k=1..n} floor(n/k)^2.

Original entry on oeis.org

1, 5, 11, 22, 32, 52, 66, 92, 115, 147, 169, 219, 245, 289, 333, 390, 424, 496, 534, 612, 672, 740, 786, 898, 957, 1037, 1113, 1219, 1277, 1413, 1475, 1595, 1687, 1791, 1883, 2056, 2130, 2246, 2354, 2526, 2608, 2792, 2878, 3040, 3190, 3330, 3424, 3662, 3773
Offset: 1

Views

Author

Benoit Cloitre, Feb 24 2013

Keywords

Comments

a(n) is the number of common divisors of integers 1<=i,j<=n over all ordered pairs (i,j). - Geoffrey Critzer, Jan 15 2015

References

  • J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, p. 98.

Crossrefs

Similar sequences for Sum_{k=1..n} floor(n/k)^m: A006218 (m=1), this sequence (m=2), A318742 (m=3), A318743 (m=4), A318744 (m=5).

Programs

  • Magma
    [&+[Floor(n/k)^2:k in [1..n] ]: n in [1..40]]; // Marius A. Burtea, Jul 16 2019
    
  • Mathematica
    Table[Sum[Floor[n/k]^2, {k, n}], {n, 50}] (* T. D. Noe, Feb 26 2013 *)
    Table[nn = n;Total[Level[Table[Table[DivisorSigma[0, GCD[i, j]], {i, 1, nn}], {j, 1, nn}], {2}]], {n, 1, 49}] (* Geoffrey Critzer, Jan 15 2015 *)
    Table[Sum[2*DivisorSigma[1, k] - DivisorSigma[0, k], {k, 1, n}], {n, 1, 50}] (* Vaclav Kotesovec, Sep 02 2018 *)
  • PARI
    a(n)=sum(k=1,n,(n\k)^2)
    
  • Python
    from math import isqrt
    def A222548(n): return -(s:=isqrt(n))**3 + sum((q:=n//k)*((k<<1)+q-1) for k in range(1,s+1)) # Chai Wah Wu, Oct 21 2023

Formula

a(n) = zeta(2)*n^2 + O(n log n).
a(n) = 2*A024916(n) - A006218(n). - Vaclav Kotesovec, Sep 02 2018
G.f.: (1/(1 - x)) * Sum_{k>=1} (2*k - 1) * x^k/(1 - x^k). - Ilya Gutkovskiy, Jul 16 2019
a(n) = Sum_{d=1..n} (2*d-1)*floor(n/d). [Uspensky and Heaslet] - Michael Somos, Feb 16 2020
a(n) = Sum_{k=1..n} Sum_{d|k} floor(n/d). - Ridouane Oudra, Jul 16 2020
a(n) = Sum_{i=1..n} Sum_{j=1..n} tau(gcd(i,j)). - Ridouane Oudra, Nov 23 2021

A272718 Partial sums of gcd-sum sequence A018804.

Original entry on oeis.org

1, 4, 9, 17, 26, 41, 54, 74, 95, 122, 143, 183, 208, 247, 292, 340, 373, 436, 473, 545, 610, 673, 718, 818, 883, 958, 1039, 1143, 1200, 1335, 1396, 1508, 1613, 1712, 1829, 1997, 2070, 2181, 2306, 2486, 2567, 2762, 2847, 3015, 3204, 3339, 3432, 3672, 3805, 4000, 4165
Offset: 1

Views

Author

Gareth McCaughan, May 05 2016

Keywords

Comments

a(n) is the sum of all pairs of greater common divisors for (i,j) where 1 <= i <= j <= n. - Jianing Song, Feb 07 2021

Examples

			The gcd-sum function takes values 1,3,5 for n = 1,2,3; therefore a(3) = 1+3+5 = 9.
		

Crossrefs

Partial sums of A018804.

Programs

  • Mathematica
    b[n_] := GCD[n, #]& /@ Range[n] // Total;
    Array[b, 100] // Accumulate (* Jean-François Alcover, Jun 05 2021 *)
    f[p_, e_] := (e*(p - 1)/p + 1)*p^e; s[n_] := Times @@ f @@@ FactorInteger[n]; Accumulate[Array[s, 100]] (* Amiram Eldar, Dec 10 2024 *)
  • PARI
    first(n)=my(v=vector(n),f); v[1]=1; for(i=2,n, f=factor(i); v[i] = v[i-1] + prod(j=1, #f~, (f[j, 2]*(f[j, 1]-1)/f[j, 1] + 1)*f[j, 1]^f[j, 2])); v \\ Charles R Greathouse IV, May 05 2016

Formula

According to Bordellès (2007), a(n) = (n^2 / (2*zeta(2)))*(log n + gamma - 1/2 + log(A^12/(2*Pi))) + O(n^(1+theta+epsilon)) where gamma = A001620, A ~= 1.282427129 is the Glaisher-Kinkelin constant A074962, theta is a certain constant defined in terms of the divisor function and known to lie between 1/4 and 131/416, and epsilon is any positive number.
G.f.: (1/(1 - x))*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) = (1/2)*Sum_{k=1..n} phi(k) * floor(n/k) * floor(1+n/k), where phi(k) is the Euler totient function. - Daniel Suteu, May 28 2018
From Jianing Song, Feb 07 2021: (Start)
a(n) = Sum_{i=1..n, j=i..n} gcd(i,j).
a(n) = (A018806(n) + n*(n+1)/2) / 2 = (Sum_{k=1..n} phi(k)*(floor(n/k))^2 + n*(n+1)/2) / 2, phi = A000010.
a(n) = A178881(n) + n*(n+1)/2.
a(n) = A018806(n) - A178881(n). (End)

A092287 a(n) = Product_{j=1..n} Product_{k=1..n} gcd(j,k).

Original entry on oeis.org

1, 1, 2, 6, 96, 480, 414720, 2903040, 5945425920, 4334215495680, 277389791723520000, 3051287708958720000, 437332621360674939863040000, 5685324077688774218219520000, 15974941971638268369709427589120000, 982608696336737613503095822614528000000000
Offset: 0

Views

Author

N. J. A. Sloane, based on a suggestion from Leroy Quet, Feb 03 2004

Keywords

Comments

Conjecture: Let p be a prime and let ordp(n,p) denote the exponent of the highest power of p that divides n. For example, ordp(48,2)=4, since 48=3*(2^4). Then we conjecture that the prime factorization of a(n) is given by the formula: ordp(a(n),p) = (floor(n/p))^2 + (floor(n/p^2))^2 + (floor(n/p^3))^2 + .... Compare this to the de Polignac-Legendre formula for the prime factorization of n!: ordp(n!,p) = floor(n/p) + floor(n/p^2) + floor(n/p^3) + .... This suggests that a(n) can be considered as generalization of n!. See A129453 for the analog for a(n) of Pascal's triangle. See A129454 for the sequence defined as a triple product of gcd(i,j,k). - Peter Bala, Apr 16 2007
The conjecture is correct. - Charles R Greathouse IV, Apr 02 2013
a(n)/a(n-1) = n, n >= 1, if and only if n is noncomposite, otherwise a(n)/a(n-1) = n * f^2, f > 1. - Daniel Forgues, Apr 07 2013
Conjecture: For a product over a rectangle, f(n,m) = Product_{j=1..n} Product_{k=1..m} gcd(j,k), a factorization similar to the one given above for the square case takes place: ordp(f(n,m),p) = floor(n/p)*floor(m/p) + floor(n/p^2)*floor(m/p^2) + .... By way of directly computing the values of f(n,m), it can be verified that the conjecture holds at least for all 1 <= m <= n <= 200. - Andrey Kaydalov, Mar 11 2019

Crossrefs

Programs

  • Magma
    [n eq 0 select 1 else (&*[(&*[GCD(j,k): k in [1..n]]): j in [1..n]]): n in [0..30]]; // G. C. Greubel, Feb 07 2024
  • Maple
    f := n->mul(mul(igcd(j,k),k=1..n),j=1..n);
  • Mathematica
    a[0] = 1; a[n_] := a[n] = n*Product[GCD[k, n], {k, 1, n-1}]^2*a[n-1]; Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Apr 16 2013, after Daniel Forgues *)
  • PARI
    h(n,p)=if(nCharles R Greathouse IV, Apr 02 2013
    
  • Sage
    def A092287(n):
        R = 1
        for p in primes(n+1) :
            s = 0; r = n
            while r > 0 :
                r = r//p
                s += r*r
            R *= p^s
        return R
    [A092287(i) for i in (0..15)]  # Peter Luschny, Apr 10 2013
    

Formula

Also a(n) = Product_{k=1..n} Product_{j=1..n} lcm(1..floor(min(n/k, n/j))).
From Daniel Forgues, Apr 08 2013: (Start)
Recurrence: a(0) := 1; for n > 0: a(n) := n * (Product_{j=1..n-1} gcd(n,j))^2 * a(n-1) = n * A051190(n)^2 * a(n-1).
Formula for n >= 0: a(n) = n! * (Product_{j=1..n} Product_{k=1..j-1} gcd(j,k))^2. (End)
a(n) = n! * A224479(n)^2 (the last formula above).
a(n) = n$ * A224497(n)^4, n$ the swinging factorial A056040(n). - Peter Luschny, Apr 10 2013

Extensions

Recurrence formula corrected by Daniel Forgues, Apr 07 2013

A344522 a(n) = Sum_{1 <= i, j, k <= n} gcd(i,j,k).

Original entry on oeis.org

1, 9, 30, 76, 141, 267, 400, 624, 885, 1249, 1590, 2208, 2689, 3411, 4248, 5248, 6081, 7485, 8530, 10248, 11889, 13687, 15228, 17988, 20053, 22569, 25242, 28588, 31053, 35463, 38284, 42540, 46581, 50893, 55362, 61824, 65857, 71247, 76884, 84388, 89349, 97881, 103342
Offset: 1

Views

Author

Seiichi Manyama, May 22 2021

Keywords

Crossrefs

Programs

  • Mathematica
    a[n_] := Sum[EulerPhi[k] * Quotient[n, k]^3, {k, 1, n}]; Array[a, 50] (* Amiram Eldar, May 22 2021 *)
  • PARI
    a(n) = sum(i=1, n, sum(j=1, n, sum(k=1, n, gcd([i, j, k]))));
    
  • PARI
    a(n) = sum(k=1, n, eulerphi(k)*(n\k)^3);
    
  • PARI
    my(N=66, x='x+O('x^N)); Vec(sum(k=1, N, eulerphi(k)*x^k*(1+4*x^k+x^(2*k))/(1-x^k)^3)/(1-x))

Formula

a(n) = Sum_{k=1..n} phi(k) * floor(n/k)^3.
G.f.: (1/(1 - x)) * Sum_{k >= 1} phi(k) * x^k * (1 + 4*x^k + x^(2*k))/(1 - x^k)^3.
a(n) ~ Pi^2 * n^3 / (6*zeta(3)). - Vaclav Kotesovec, May 23 2021

A344479 Square array T(n,k), n >= 1, k >= 1, read by antidiagonals, where T(n,k) = Sum_{1 <= x_1, x_2, ..., x_k <= n} gcd(x_1, x_2, ..., x_k).

Original entry on oeis.org

1, 1, 3, 1, 5, 6, 1, 9, 12, 10, 1, 17, 30, 24, 15, 1, 33, 84, 76, 37, 21, 1, 65, 246, 276, 141, 61, 28, 1, 129, 732, 1060, 649, 267, 80, 36, 1, 257, 2190, 4164, 3165, 1417, 400, 112, 45, 1, 513, 6564, 16516, 15697, 8091, 2528, 624, 145, 55, 1, 1025, 19686, 65796, 78261, 47521, 17128, 4432, 885, 189, 66
Offset: 1

Views

Author

Seiichi Manyama, May 22 2021

Keywords

Examples

			G.f. of column 3: (1/(1 - x)) * Sum_{i>=1} phi(i) * (x^i + 4*x^(2*i) + x^(3*i))/(1 - x^i)^3.
Square array begins:
   1,  1,   1,    1,    1,     1, ...
   3,  5,   9,   17,   33,    65, ...
   6, 12,  30,   84,  246,   732, ...
  10, 24,  76,  276, 1060,  4164, ...
  15, 37, 141,  649, 3165, 15697, ...
  21, 61, 267, 1417, 8091, 47521, ...
		

Crossrefs

Columns k=1..5 give A000217, A018806, A344522, A344523, A344524.
T(n,n) gives A344525.

Programs

  • Mathematica
    T[n_, k_] := Sum[EulerPhi[j] * Quotient[n, j]^k, {j, 1, n}]; Table[T[k, n - k + 1], {n, 1, 11}, {k, 1, n}] // Flatten (* Amiram Eldar, May 22 2021 *)
  • PARI
    T(n, k) = sum(j=1, n, eulerphi(j)*(n\j)^k);

Formula

G.f. of column k: (1/(1 - x)) * Sum_{i>=1} phi(i) * ( Sum_{j=1..k} A008292(k, j) * x^(i*j) )/(1 - x^i)^k.
T(n,k) = Sum_{j=1..n} phi(j) * floor(n/j)^k.

A344525 a(n) = Sum_{1 <= x_1, x_2, ... , x_n <= n} gcd(x_1,x_2, ... ,x_n).

Original entry on oeis.org

1, 5, 30, 276, 3165, 47521, 826000, 16843792, 387723045, 10009889889, 285360865350, 8918311872516, 302888304741841, 11112685595264369, 437898699063881208, 18447025862624951488, 827242515246907227633, 39346558373191515582161
Offset: 1

Views

Author

Seiichi Manyama, May 22 2021

Keywords

Crossrefs

Main diagonal of A344479.

Programs

  • Mathematica
    a[n_] := Sum[EulerPhi[k] * Quotient[n, k]^n, {k, 1, n}]; Array[a, 20] (* Amiram Eldar, May 22 2021 *)
  • PARI
    a(n) = sum(k=1, n, eulerphi(k)*(n\k)^n);
    
  • Python
    from sympy import totient
    def A344525(n): return sum(totient(k)*(n//k)**n for k in range(1,n+1)) # Chai Wah Wu, Aug 05 2024

Formula

a(n) = Sum_{k=1..n} phi(k) * floor(n/k)^n.
a(n) ~ n^n. - Vaclav Kotesovec, May 23 2021

A064951 a(n) = Sum_{1 <= x, y <= n} lcm(x, y).

Original entry on oeis.org

1, 7, 28, 72, 177, 303, 604, 948, 1497, 2127, 3348, 4272, 6313, 8119, 10324, 13060, 17701, 20995, 27512, 32132, 38453, 45779, 57440, 64664, 77689, 89935, 104704, 117948, 141525, 154755, 183616, 205472, 231113, 258959, 290564, 314720, 364041
Offset: 1

Views

Author

Vladeta Jovovic, Oct 28 2001

Keywords

Comments

a(n) is also the entrywise 1-norm of the n X n LCM matrix.

Crossrefs

Programs

  • Mathematica
    Table[nn = n;Total[Level[Table[Table[LCM[i, j], {i, 1, nn}], {j, 1, nn}], {2}]], {n, 1, 37}] (* Geoffrey Critzer, Jan 14 2015 *)
  • PARI
    { a=0; for (n=1, 1000, a+=n*sum(k=1, n, n/gcd(n, k)); write("b064951.txt", n, " ", a) ) } \\ Harry J. Smith, Oct 01 2009

Formula

a(n) = a(n-1) + 2*A051193(n) - n = a(n-1) + n*A057660(n) = Sum_{1 <= i <= j <= n} (j^2/gcd(i, j)). - Henry Bottomley, Oct 29 2001
a(n) ~ 3 * zeta(3) * n^4 / (2*Pi^2). - Vaclav Kotesovec, May 29 2021

A178881 Sum of all pairs of greatest common divisors for (i,j) where 1 <= i < j <= n.

Original entry on oeis.org

0, 1, 3, 7, 11, 20, 26, 38, 50, 67, 77, 105, 117, 142, 172, 204, 220, 265, 283, 335, 379, 420, 442, 518, 558, 607, 661, 737, 765, 870, 900, 980, 1052, 1117, 1199, 1331, 1367, 1440, 1526, 1666, 1706, 1859, 1901, 2025, 2169, 2258, 2304, 2496, 2580, 2725
Offset: 1

Views

Author

Enric Cusell (cusell(AT)gmail.com), Jun 20 2010

Keywords

Comments

You could also be looking for the case where i = j is allowed, which gives A272718(n) = a(n) + n*(n+1)/2.

Examples

			Denote gcd(i,j) by (i,j), then a(6) = (1,2) + (1,3) + (1,4) + (1,5) + (1,6) + (2,3) + (2,4) + (2,5) + (2,6) + (3,4) + (3,5) + (3,6) + (4,5) + (4,6) + (5,6) = 20. - _Jianing Song_, Feb 07 2021
		

Crossrefs

Partial sums of A006579.

Programs

  • Mathematica
    f[p_, e_] := (e*(p - 1)/p + 1)*p^e; s[n_] := Times @@ f @@@ FactorInteger[n] - n; Accumulate[Array[s, 100]] (* Amiram Eldar, Dec 10 2024 *)
  • PARI
    a(n)=sum(k=1, n, eulerphi(k)*(n\k)^2)/2-n*(n+1)/4 \\ Charles R Greathouse IV, Apr 11 2016
    
  • PARI
    first(n)=my(v=vector(n),t); for(k=1,n, t=eulerphi(k); for(m=k,n, v[m] += t*(m\k)^2)); v/2-vector(n,k,k*(k+1)/4) \\ Charles R Greathouse IV, Apr 11 2016

Formula

a(n) = Sum_{i=1..n-1, j=i+1..n} gcd(i,j).
From Jianing Song, Feb 07 2021: (Start)
a(n) = (A018806(n) - n*(n+1)/2) / 2 = (Sum_{k=1..n} phi(k)*(floor(n/k))^2 - n*(n+1)/2) / 2, phi = A000010.
a(n) = A018806(n) - A272718(n).
According to Bordellès (2007), a(n) = (3/Pi^2)*n^2*log(n) + k*n^2 + O(n^(1+theta+epsilon)), where k = (3/Pi^2)*(gamma - 1/2 + log(A^12/(2*Pi))), gamma = A001620, A ~= 1.282427129 is the Glaisher-Kinkelin constant A074962, theta is a certain constant defined in terms of the divisor function and known to lie between 1/4 and 131/416, and epsilon is any positive number. See also A272718. (End)

A344598 a(n) = Sum_{k=1..n} phi(k) * (floor(n/k)^2 - floor((n-1)/k)^2).

Original entry on oeis.org

1, 4, 7, 12, 13, 24, 19, 32, 33, 44, 31, 68, 37, 64, 75, 80, 49, 108, 55, 124, 109, 104, 67, 176, 105, 124, 135, 180, 85, 240, 91, 192, 177, 164, 199, 300, 109, 184, 211, 320, 121, 348, 127, 292, 333, 224, 139, 432, 217, 340, 279, 348, 157, 432, 323, 464, 313, 284, 175, 660, 181
Offset: 1

Views

Author

Seiichi Manyama, May 24 2021

Keywords

Crossrefs

Programs

  • Mathematica
    a[n_] := Sum[EulerPhi[k] * First @ Differences @ (Quotient[{n - 1, n}, k]^2), {k, 1, n}]; Array[a, 50] (* Amiram Eldar, May 24 2021 *)
  • PARI
    a(n) = sum(k=1, n, eulerphi(k)*((n\k)^2-((n-1)\k)^2));
    
  • PARI
    my(N=66, x='x+O('x^N)); Vec(sum(k=1, N, eulerphi(k)*x^k*(1+x^k)/(1-x^k)^2))

Formula

Sum_{k=1..n} a(k) = A018806(n).
G.f.: Sum_{k>=1} phi(k) * x^k * (1 + x^k)/(1 - x^k)^2.
Conjecture: a(n) = Sum_{k = 1..2*n} (-1)^k * gcd(k, 4*n). Cf. A344372. - Peter Bala, Jan 01 2024

A367690 Total number of steps of Euclid's GCD algorithm to calculate gcd(x,y) for all pairs x,y in the range 1 <= x,y <= n.

Original entry on oeis.org

1, 5, 14, 26, 47, 67, 100, 136, 177, 221, 286, 338, 415, 491, 568, 652, 761, 861, 990, 1098, 1219, 1351, 1520, 1652, 1813, 1985, 2162, 2334, 2555, 2727, 2960, 3172, 3397, 3641, 3878, 4098, 4383, 4659, 4944, 5204, 5537, 5805, 6158, 6466, 6775, 7123, 7524, 7848
Offset: 1

Views

Author

Darío Clavijo, Nov 26 2023

Keywords

Comments

The number of steps to calculate gcd(x,y) is A107435(x,y) for x<=y, and is the length of the continued fraction expansion of x/y (including 0 for the integer part).
A018806(n) <= a(n) <= A064951(n).

Crossrefs

Programs

  • Maple
    g:= proc(x, y) option remember;
          `if`(y=0, 0, 1+g(y, irem(x, y)))
        end:
    a:= proc(n) option remember; `if`(n=0, 0,
          a(n-1)+n+2*add(g(n, j), j=1..n-1))
        end:
    seq(a(n), n=1..100);  # Alois P. Heinz, Nov 27 2023
  • Mathematica
    g[x_, y_] := g[x, y] = If[y == 0, 0, 1 + g[y, Mod[x, y]]];
    a[n_] := a[n] = If[n == 0, 0, a[n-1] + n + 2*Sum[g[n, j], {j, 1, n-1}]];
    Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Apr 19 2025, after Alois P. Heinz *)
  • PARI
    A107435(n, k) = if (k == 0, 0, 1 + A107435(k, n % k));
    a(n) = sum(x=1, n, sum(y=1, n, A107435(x,y)));
    print(vector(49,n,a(n)));
  • Python
    from functools import cache
    A107435 = lambda x,y: 0 if y == 0 else 1 + A107435(y, x % y)
    A049826 = lambda n: sum(A107435(n,j) for j in range(1, n))
    @cache
    def a(n):
      # Code after Alois P. Heinz
      if n == 0: return 0
      return a(n-1) + n + A049826(n) * 2
    print([a(n) for n in range(1,49)])
    

Formula

a(n) = a(n-1) + n + A049826(n) * 2 and a(1) = 1.
a(n) = a(n-1) + n + (Sum_{j=1..n-1} A107435(n,j)) * 2 and a(1) = 1.
a(n) = Sum_{x=1..n} Sum_{y=1..n} A107435(x,y). - Michel Marcus, Nov 28 2023
Showing 1-10 of 11 results. Next