A099957 -id:A099957 - cp's OEIS frontend

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

Ugo Merlone (merlone(AT)econ.unito.it) and N. J. A. Sloane, Feb 22 2006

Also, half of the number of two-dimensional threshold functions (A114146).
The line may not pass through any point. This is the "labeled" version - rotations and reflections are not taken into account (cf. A116696).
The number of ways to divide a (2n) X (2n) grid into two sets of equal size is given by 2*A099957(n). - David Applegate, Feb 23 2006
All terms are odd: the line that misses the grid contributes 1 to the total and all other lines contribute 2, 4 or 8, so the total must be odd.
What can be said about the 3-D generalization? - Max Alekseyev, Feb 27 2006

			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.
--------------------

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)

Cf. A114499, A115004, A115005, A116696 (unlabeled case), A114531, A114146.
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

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

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

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) = A141255(n) + 1. - T. D. Noe, Jun 17 2008
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

More terms from Max Alekseyev, Feb 22 2006

A099958 (1/2)*number of distinct angular positions under which an observer positioned at the center of an edge of a square lattice can see the (2n)X(2n-1) points symmetrically surrounding his position.

Original entry on oeis.org

1, 5, 13, 23, 37, 55, 75, 95, 127, 157, 185, 227, 263, 305, 357, 403, 455, 511, 571, 631, 703, 769, 833, 923, 997, 1069, 1169, 1245, 1329, 1443, 1535, 1631, 1743, 1849, 1957, 2075, 2195, 2307, 2439, 2565, 2683, 2845, 2957, 3097, 3265, 3385

Offset: 1

Hugo Pfoertner, Nov 13 2004

nonn

See A099957 for further information. Cf. A049687, A049690, A190815.

This is a bisection of A049690, that is, a(n) = Sum[k=1..2n+1, phi(2k)]. - Ralf Stephan, Nov 13 2004.

A106481 An Euler phi transform of 1/(1 - x^2).

Original entry on oeis.org

0, 1, 1, 3, 3, 7, 5, 13, 9, 19, 13, 29, 17, 41, 23, 49, 31, 65, 37, 83, 45, 95, 55, 117, 63, 137, 75, 155, 87, 183, 95, 213, 111, 233, 127, 257, 139, 293, 157, 317, 173, 357, 185, 399, 205, 423, 227, 469, 243, 511, 263, 543, 287, 595, 305, 635, 329, 671, 357, 729

Offset: 0

Paul Barry, May 03 2005

Cf. A049690, A099957.

a(n) = sum(k=0, n, if (k%2, eulerphi(n-k+1))); \\ Michel Marcus, Jun 12 2024

# uses programs from A002088 and A049690
def A106481(n): return A002088(n+1)-A049690(n+1>>1) if n&1 else A049690(n>>1) # Chai Wah Wu, Aug 04 2024

a(n) = Sum_{k=0..n} phi(n-k+1)*(k mod 2).
Euler transform of period 7 sequence [3,-2,-1,-1,-2,3,0,...].
a(2n) = A049690(n).
a(2n+1) = A099957(n).

A274401 Number of balanced linear 4-partitions of the n X n grid.

Original entry on oeis.org

0, 1, 8, 3, 16, 7, 32, 13, 48, 19, 80, 29, 96, 41, 144, 49, 176, 65, 224, 83, 256, 95, 336, 117, 368, 137, 464, 155, 512, 183, 576, 213, 640, 233, 768, 257, 816, 293, 960, 317, 1024, 357, 1120, 399, 1200, 423, 1376, 469, 1440

Offset: 1

Max Alekseyev, Jun 20 2016

D. M. Acketa, N. Divljak, J. Zunic. On balanced linear 4-partitions of the (n,n)-grid. Novi Sad Journal of Mathematics 24:1 (1994), 309-319.

Cf. A002088, A049690, A099957.

{ a(n) = if(n%2, 8*sum(m=1,(n-1)\2,eulerphi(m)), sum(m=0,(n-1)\2,eulerphi(2*m+1)) ); }

# uses programs from A002088 and A049690
def A274401(n): return (A002088(n>>1)<<3) if n&1 else A002088(n-1)-A049690((n>>1)-1) # Chai Wah Wu, Aug 04 2024

For odd n, a(n) = 8 * A002088((n-1)/2).

For even n, a(n) = A099957(n/2).

A116696 Take an n X n square grid of points in the plane; a(n) = number of non-isomorphic ways to divide the points into two sets using a straight line.

Original entry on oeis.org

1, 3, 6, 15, 29, 59, 99, 170, 262, 401, 570, 816, 1103, 1499, 1956, 2534, 3195, 4041, 4980, 6153, 7448, 8985, 10674, 12704, 14899, 17473, 20262, 23467, 26914, 30905, 35138, 39996, 45191, 50997

Offset: 1

David Applegate, Feb 23 2006

The line may not pass through any point. This is the "unlabeled" version - rotations and reflections are taken into account. See A114043 for the "labeled" version.

			Examples: the two sets are indicated by X's and o's.
a(2) = 3:
XX oX oo
XX XX XX
--------------------
a(3) = 7:
XXX oXX ooX ooo ooX ooo
XXX XXX XXX XXX oXX oXX
XXX XXX XXX XXX XXX XXX
--------------------
a(4)= 15:
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
----
XXXX XXXX XXXX XXXX XXXX
XXXo XXXX XXXX XXXo XXXo
XXoo Xooo oooo Xooo XXoo
Xooo oooo oooo oooo oooo

Cf. A114043, A099957.

if n is even, then a(n) = (A114043(n) + 6n + 3 + 2 A099957(n/2))/8 if n is odd, then a(n) = (A114043(n) + 6n + 1)/8

A360452 Number of fractions c/d with |c| <= d <= 2n and odd denominator when factors of 2 are canceled.

Original entry on oeis.org

0, 3, 7, 15, 27, 39, 59, 83, 99, 131, 167, 191, 235, 275, 311, 367, 427, 467, 515, 587, 635, 715, 799, 847, 939, 1023, 1087, 1191, 1271, 1343, 1459, 1579, 1651, 1747, 1879, 1967, 2107, 2251, 2331, 2451, 2607, 2715, 2879, 3007, 3119, 3295, 3439, 3559, 3703, 3895, 4015

Offset: 0

M. F. Hasler, Mar 26 2023

Using d <= 2n or d <= 2n-1 gives the same result, therefore we use 2n and not just n for the upper limit of the denominator. Indeed, using an even d will only yield the same simplified fractions with odd denominators as one gets for d/2.

			For n = 0, there is no possible fraction, since the denominator can't be zero.
For n = 1, we have a(1) = #{ -1/1, 0/1, 1/1} = 3; using denominator d = 2 would not give other elements with odd denominator after cancellations, cf. comments.
For n = 2, we have a(2) = #{-1/1, -2/3, -1/3, 0, 1/3, 2/3, 1/1} = 7.
For n = 3, we have a(3) = #{-1/1, -4/5, -2/3, -3/5, -2/5, -1/3, -1/5, 0, 1/5, 1/3, 2/5, 3/5, 2/3, 4/5, 1/1} = 15. As explained in comments, only odd d are useful.

Cf. A099957, A049691.

a(n)=#Set(concat([[c/d|c<-[-d..d],d && denominator(c/d)%2]|d<-[0..n*2]])) \\ For illustration only. Remove the # to see the elements. Obviously the code could be optimized.

apply( {A360452(n) = sum(i=0, n-1, eulerphi(2*i+1))*2+!!n}, [0..10]) \\ This should be used to define the "official" function A360452.

# uses programs from A002088 and A049690
def A360452(n): return (A002088((n<<1)-1)-A049690(n-1)<<1)|1 if n else 0 # Chai Wah Wu, Aug 04 2024

a(n) = 2*A099957(n)+1 for n > 0.

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A099958 (1/2)*number of distinct angular positions under which an observer positioned at the center of an edge of a square lattice can see the (2n)X(2n-1) points symmetrically surrounding his position.

Views

Author

Keywords

Crossrefs

Formula

A106481 An Euler phi transform of 1/(1 - x^2).

Views

Author

Keywords

Crossrefs

Programs

PARI

Python

Formula

A274401 Number of balanced linear 4-partitions of the n X n grid.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Python

Formula

A116696 Take an n X n square grid of points in the plane; a(n) = number of non-isomorphic ways to divide the points into two sets using a straight line.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A360452 Number of fractions c/d with |c| <= d <= 2n and odd denominator when factors of 2 are canceled.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

PARI

Python

Formula