A114043 Take an n X n square grid of points in the plane; a(n) = number of ways to divide the points into two sets using a straight line.
1, 7, 29, 87, 201, 419, 749, 1283, 2041, 3107, 4493, 6395, 8745, 11823, 15557, 20075, 25457, 32087, 39725, 48935, 59457, 71555, 85253, 101251, 119041, 139351, 161933, 187255, 215137, 246691, 280917, 319347, 361329, 407303
Offset: 1
Examples
Examples: the two sets are indicated by X's and o's. a(2) = 7: XX oX Xo XX XX oo oX XX XX XX Xo oX XX oX -------------------- a(3) = 29: XXX oXX ooX ooo ooX ooo XXX XXX XXX XXX oXX oXX XXX XXX XXX XXX XXX XXX -1- -4- -8- -4- -4- -8- Total = 29 -------------------- a(4)= 87: XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXo XXXo XXXo XXoo XXoo XXXX XXXo XXoo Xooo oooo XXoo Xooo oooo Xooo oooo --1- --4- --8- --8- --4- --4- --8- --8- --8- --8- XXXX XXXX XXXX XXXX XXXX XXXo XXXX XXXX XXXo XXXo XXoo Xooo oooo Xooo XXoo Xooo oooo oooo oooo oooo --4- --8- --2- --4- --8- Total = 87. --------------------
Links
- T. D. Noe, Table of n, a(n) for n = 1..1000
- Max 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, and N. Yu. Zolotykh. On the minimal teaching sets of two-dimensional threshold functions. SIAM Journal on Discrete Mathematics 29:1 (2015), 157-165. doi:10.1137/140978090. See Eq. (11).
- N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
Crossrefs
Cf. A099957.
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
Programs
-
Mathematica
a[n_] := 2*Sum[(n - i)*(n - j)*Boole[CoprimeQ[i, j]], {i, 1, n - 1}, {j, 1, n - 1}] + 2*n^2 - 2*n + 1; Array[a, 40] (* Jean-François Alcover, Apr 25 2016, after Max Alekseyev *) -
Python
from sympy import totient def A114043(n): return 4*n**2-6*n+3 + 2*sum(totient(i)*(n-i)*(2*n-i) for i in range(2,n)) # Chai Wah Wu, Aug 15 2021
Formula
Let V(m,n) = Sum_{i=1..m, j=1..n, gcd(i,j)=1} (m+1-i)*(n+1-j); then a(n+1) = 2*(n^2 + n + V(n,n)) + 1. - Max Alekseyev, Feb 22 2006
a(n) ~ (3/Pi^2) * n^4. - Max Alekseyev, Feb 22 2006
a(n) = 4*n^2 - 6*n + 3 + 2*Sum_{i=2..n-1} (n-i)*(2n-i)*phi(i). - Chai Wah Wu, Aug 15 2021
Extensions
More terms from Max Alekseyev, Feb 22 2006
Comments