OFFSET
0,2
COMMENTS
Also, number of intersections of a halfspace with an n X n grid. While A114043 counts cuts, this sequence counts sides of cuts. The only difference between this and twice A114043 is that this makes sense for the empty grid. This is the "labeled" version - rotations and reflections are not taken into account. - David Applegate, Feb 24 2006
In the terminology of Koplowitz et al., this is the number of linear dichotomies on a square grid. - N. J. A. Sloane, Mar 14 2020
LINKS
Chai Wah Wu, Table of n, a(n) for n = 0..10000
M. A. Alekseyev. On the number of two-dimensional threshold functions, arXiv:math/0602511 [math.CO], 2006-2010; doi:10.1137/090750184, SIAM J. Disc. Math. 24(4), 2010, pp. 1617-1631.
M. A. Alekseyev, M. Basova, N. Yu. Zolotykh. On the minimal teaching sets of two-dimensional threshold functions. SIAM J. Disc. Math. 29(1), 2015, pp. 157-165.
Jack Koplowitz, Michael Lindenbaum and A. Bruckstein, The number of digital straight lines on an N*N grid, IEEE Transactions on Information Theory 36.1 (1990): 192-197. See D(n).
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
FORMULA
For n>0, a(n) = 2*A114043(n).
For n>0, a(n) = 8*n^2 - 12*n + 6 + 4*Sum_{i=2..n-1} (n-i)*(2n-i)*phi(i). - Chai Wah Wu, Aug 15 2021
MATHEMATICA
a[0] = 1; a[n_] := 4 Sum[(n-i)(n-j) Boole[CoprimeQ[i, j]], {i, 1, n-1}, {j, 1, n-1}] + 4 n^2 - 4 n + 2;
PROG
(Python)
from sympy import totient
def A114146(n): return 1 if n == 0 else 8*n**2-12*n+6 + 4*sum(totient(i)*(n-i)*(2*n-i) for i in range(2, n)) # Chai Wah Wu, Aug 15 2021
CROSSREFS
The following eight sequences are all essentially the same. The simplest is A115004(n), which we denote by z(n). Then A088658(n) = 4*z(n-1); A114043(n) = 2*z(n-1)+2*n^2-2*n+1; A114146(n) = 2*A114043(n); A115005(n) = z(n-1)+n*(n-1); A141255(n) = 2*z(n-1)+2*n*(n-1); A290131(n) = z(n-1)+(n-1)^2; A306302(n) = z(n)+n^2+2*n. - N. J. A. Sloane, Feb 04 2020
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Feb 22 2006
EXTENSIONS
Definition corrected by Max Alekseyev, Oct 23 2008
a(0)=1 prepended by Max Alekseyev, Jan 23 2015
STATUS
approved