Gareth McCaughan - cp's OEIS frontend

User: Gareth McCaughan

Gareth McCaughan has authored 4 sequences.

A272718 Partial sums of gcd-sum sequence A018804.

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

Gareth McCaughan, May 05 2016

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

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

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Olivier Bordellès, A note on the average order of the gcd-sum function, Journal of Integer Sequences, Vol. 10 (2007), Article 07.3.3.

Partial sums of A018804.

Cf. A018806, A000010, A001620, A074962, A178881.

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

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

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)

A112675 Number of directed Hamiltonian paths on a triangular grid, n vertices on each side.

Original entry on oeis.org

1, 6, 24, 228, 3936, 132624, 8762040, 1156532424, 306700450536, 164818597404924, 180360080611682424, 403600060221250880496, 1853096813379189131728692, 17504763708306471241857275208

Offset: 1

Gareth McCaughan, Dec 30 2005

This sequence counts paths in a triangular region of the familiar 2-dimensional lattice in which each point has 6 neighbors (sometimes called either the "triangular" or the "hexagonal" lattice), visiting every vertex of the region exactly once. The paths are not assumed to be closed. A path and its reversal are not considered equivalent.

Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, Triangular Grid Graph
Index entries for sequences related to graphs, Hamiltonian

Cf. A003763, A112676.

a(8)-a(14) from Andrew Howroyd, Nov 02 2015

A112676 Number of (undirected) Hamiltonian cycles on a triangular grid, n vertices on each side.

Original entry on oeis.org

1, 1, 1, 3, 26, 474, 17214, 1371454, 231924780, 82367152914, 61718801166402, 97482824713311442, 323896536556067453466, 2262929852279448821099932, 33231590982432936619392054662, 1025257090790362187626154669771934, 66429726878393651076826663971376589034

Offset: 1

Gareth McCaughan, Dec 30 2005

nonn

This sequence counts cycles in a triangular region of the familiar 2-dimensional lattice in which each point has 6 neighbors (sometimes called either the "triangular" or the "hexagonal" lattice), visiting every vertex of the region exactly once and returning to the starting vertex. Cycles differing only in orientation or starting point are not considered distinct.

			a(3) = 1, the only Hamiltonian cycle being the obvious one running around the edge of the triangle.

Andrey Zabolotskiy, Table of n, a(n) for n = 1..20 [from Pettersson's tables]
András Kaszanyitzky, Triangular fractal approximating graphs and their covering paths and cycles, arXiv:1710.09475 [math.CO], 2017. See Table 1.
Ville Pettersson, Graph Algorithms for Constructing and Enumerating Cycles and Related Structures, Dissertation, Aalto, Finland, 2015.
Ville H. Pettersson, Enumerating Hamiltonian Cycles, The Electronic Journal of Combinatorics, Volume 21, Issue 4, 2014.
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Eric Weisstein's World of Mathematics, Triangular Grid Graph
Index entries for sequences related to graphs, Hamiltonian

Cf. A003763, A112675, A174589, A266513.

# Using graphillion
from graphillion import GraphSet
def make_n_triangular_grid_graph(n):
    s = 1
    grids = []
    for i in range(n + 1, 1, -1):
        for j in range(i - 1):
            a, b, c = s + j, s + j + 1, s + i + j
            grids.extend([(a, b), (a, c), (b, c)])
        s += i
    return grids
def A112676(n):
    if n == 1: return 1
    universe = make_n_triangular_grid_graph(n - 1)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles(is_hamilton=True)
    return cycles.len()
print([A112676(n) for n in range(1, 12)])  # Seiichi Manyama, Nov 30 2020

For n>1, a(n) = A174589(n)/2.

a(11)-a(16) from Andrew Howroyd, Nov 03 2015

a(17) from Pettersson by Andrey Zabolotskiy, May 23 2017

A094060 Number of walks of length n on hexagonal grid that start and end at the origin. Intermediate returns to the origin are not permitted.

Original entry on oeis.org

1, 0, 6, 12, 54, 216, 1032, 4896, 24606, 125040, 651348, 3432168, 18331992, 98814816, 537343632, 2942475552, 16214888286, 89835783264, 500116783740, 2795958732024, 15690597591636, 88354191756816, 499060719941616, 2826794871554112, 16052536475622792

Offset: 0

Gareth McCaughan, Jun 10 2004

Alois P. Heinz, Table of n, a(n) for n = 0..1291 (first 97 terms from Ludovic Schwob)

Cf. A002898, A054474.

b:= proc(n) option remember; `if`(n<3, [1,0,6][n+1], ((n-1)*
      n*b(n-1) +24*(n-1)^2*b(n-2) +36*(n-1)*(n-2)*b(n-3))/n^2)
    end:
a:= proc(n) option remember; `if`(n=0, 1,
      b(n)-add(a(n-i)*b(i), i=1..n-1))
    end:
seq(a(n), n=0..23);  # Alois P. Heinz, Dec 07 2020

b[n_] := b[n] = If[n<3, {1, 0, 6}[[n+1]], ((n-1)n b[n-1] + 24(n-1)^2* b[n-2] + 36(n-1)(n-2) b[n-3])/n^2];
a[n_] := a[n] = If[n==0, 1, b[n] - Sum[a[n-i] b[i], {i, 1, n-1}]];
a /@ Range[0, 23] (* Jean-François Alcover, Jan 14 2021, after Alois P. Heinz *)

seq(n)={my(g=sum(m=0, n, (3*m)!/m!^3*x^(2*m)*(1+2*x)^m, O(x*x^n))); Vec(2-1/g)} \\ Andrew Howroyd, Aug 09 2025

INVERTi transform of A002898. - R. J. Mathar, Sep 29 2020

cp's OEIS Frontend

User: Gareth McCaughan

A272718 Partial sums of gcd-sum sequence A018804.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A112675 Number of directed Hamiltonian paths on a triangular grid, n vertices on each side.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A112676 Number of (undirected) Hamiltonian cycles on a triangular grid, n vertices on each side.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

Extensions

A094060 Number of walks of length n on hexagonal grid that start and end at the origin. Intermediate returns to the origin are not permitted.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula