A260708 -id:A260708 - cp's OEIS frontend

A264041 a(n) is the maximum number of diagonals that can be placed in an n X n grid made up of 1 X 1 unit squares when diagonals are placed in the unit squares in such a way that no two diagonals may cross or intersect at an endpoint.

1, 3, 6, 10, 16, 21, 29, 36, 46, 55, 68, 78, 93, 105, 122, 136, 156, 171, 193, 210, 234, 253, 280, 300, 329, 351, 382, 406, 440, 465, 501, 528

Offset: 1

Gabriella Pinter, Stephen Wasielewski, Peter Boyland, Ivan Roth, G. Christopher Hruska, Jeb Willenbring, Oct 22 2015

In other words, largest number of nonintersecting vertex-disjoint diagonals / and \ that can be packed in an n X n grid.
/ and \ cannot be adjacent horizontally or vertically.
Two \ cannot be adjacent on a northwest-to-southeast diagonal, two / cannot be adjacent on a southwest-to-northeast diagonal.
We also extended this to m X n grids, and have some limited results.
a(n) is the size of a maximum independent set in a graph with vertices (x,y,z), x=1..n, y=1..n, z=1..2, with edges joining (x,y,z) to (x,y,3-z), (x+1,y,3-z), and (x,y+1,3-z), (x,y,1) to (x+1,y-1,1) and (x,y,2) to (x+1,y+1,2). - Robert Israel, Nov 01 2015
From Rob Pratt, Nov 09 2015: (Start)
382 <= a(27) <= 383.
a(29) = 440.
For the number of optimal solutions see A264667. (End)
Conjecture: partial sums of A260307. - Sean A. Irvine, Jul 15 2022
From Aleksandr V. Novozhilov, Apr 01 2025: (Start)
a(27) = 382.
a(31) = 501.
566 <= a(33) <= 567.
636 <= a(35) <= 637. (End)
a(35) = 636, proved using SCIP ILP solver. - Aleksandr V. Novozhilov, Apr 09 2025

			For a(2) = 3, an optimal configuration is
   //
   ./
(This is best seen using a fixed-width font. It is better to use "." instead of " " for blank squares, because " " tends to disappear.)
Note that the bottom left square can't have / because that would conflict with the / at top right, or \ because that would conflict with its horizontal and vertical neighbors.
For a(3) = 6, an optimal configuration is
   ///
   ../
   /./
For a(4) = 10, an optimal configuration may be depicted, with the grid lines explicitly drawn, as
   +-+-+-+-+
   |/| |\|\|
   +-+-+-+-+
   |/| |\| |
   +-+-+-+-+
   |/| | | |
   +-+-+-+-+
   |/|/|/|/|
   +-+-+-+-+
or, using "o" and "." to represent used and unused vertices, as
   .-o-o-o-.
   |/| |\|\|
   o-o-o-o-o
   |/| |\| |
   o-o-.-o-.
   |/| | | |
   o-o-o-o-o
   |/|/|/|/|
   o-o-o-o-.
For a(5) = 16, an optimal configuration is
   ///.\
   ../.\
   \\.\\
   \./..
   \.///
For more examples, see the link "Optimal configurations for n=1..32".

Peter Boyland, Gabriella Pintér, István Laukó, Ivan Roth, Jon E. Schoenfield, and Stephen Wasielewski, On the Maximum Number of Non-intersecting Diagonals in an Array, Journal of Integer Sequences, Vol. 20 (2017), Article 17.2.4.
Robert Israel, Code for MATLAB with CPLEX
Robert Israel, Optimal configurations for n=1..26
Mathematics StackExchange, How to solve 5x5 grid with 16 diagonals
Aleksandr V. Novozhilov, Optimal configurations for n=1..32
NRICH, Distinct Diagonals
Gabriella Pinter, Figure used to illustrate proof of lower bound in n=6k-1 case, k=1,2,3
Gabriella Pinter, Lower bound for the case n = 6k-1, Oct 27 2015
Gabriella Pinter, Solution when there are an even number of rows of cells
Yaohui Zhu, Kaiming Sun, Zhengdong Luo, and Lingfeng Wang, Progressive Self-Learning for Domain Adaptation on Symbolic Regression of Integer Sequences, Proc. 39th AAAI Conf. Artif. Intel. (2025) Vol. 39, No. 1, 1692-1699. See p. 1698.

Cf. A000217 (triangular numbers), A260708 (the same?), A264938 (first bisection?), A264667.

Cf. A299017 (intersection with A000217).

Theorem: a(2*n) = n*(2n+1) (the even-indexed terms among the triangular numbers A000217). More generally, for the 2k X m case, the optimal solution is k*(m+1). See third Pinter link for proof.
Theorem: a(6*n-1) >= n + 3*n*(6*n-1). See second Pinter link for proof.
Theorem: a(n) <= a(n-2) + 2*n.
Empirical g.f.: x*(1 + 2*x + 2*x^2 + 2*x^3 + 3*x^4 + x^5 + x^6) / ((1 - x)^3*(1 + x)^2*(1 - x + x^2)*(1 + x + x^2)). - Robert Israel, Nov 01 2015. Corrected by Colin Barker, Jan 31 2018
a(n) = a(n-1) + a(n-2) - a(n-3) + a(n-6) - a(n-7) - a(n-8) + a(n-9) for n>9 (conjectured). - Colin Barker, Jan 31 2018
a(n) = n*(n+1)/2 for n even, floor(n*(n/2+2/3)+1/6) for n odd (conjecture). - Bill McEachen, Aug 11 2025

Additional comments and terms a(9)-a(26) from Robert Israel, Nov 01 2015
This entry is the result of merging two independent submissions, merged by N. J. A. Sloane, Nov 11 2015
Cases n=27, n=31 proved using SCIP ILP solver by Aleksandr V. Novozhilov, Apr 01 2025

A260699 a(2n+6) = a(2n) + 12n + 20, a(2n+1) = (n+1)(2*n+1), with a(0)=0, a(2)=2, a(4)=9.

Original entry on oeis.org

0, 1, 2, 6, 9, 15, 20, 28, 34, 45, 53, 66, 76, 91, 102, 120, 133, 153, 168, 190, 206, 231, 249, 276, 296, 325, 346, 378, 401, 435, 460, 496, 522, 561, 589, 630, 660, 703, 734, 780, 813, 861, 896, 946, 982, 1035, 1073

Offset: 0

Paul Curtz, Nov 16 2015

Sequence extended to left:
..., 36, 29, 21, 16, 10, 6, 3, 1, 0, 0, 1, 2, 6, 9, 15, 20, 28, 34, ...,
where 0, 1, 3, 6, 10, 16, 21, 29, 36, 46, ... is A260708.
After 2, if a(n) is prime then n == 4 (mod 6).
a(n) is a square for n = 0, 1, 4, 49, 52, 192, 1681, 4948, 57121, 60388, 221952, 1940449, 5710372, ...

			a(0) = 0,
a(1) = 1*1 = 1,
a(2) = 2,
a(3) = 2*3 = 6,
a(4) = 9,
a(5) = 3*5 = 15,
a(6) = a(0) + 12*0 + 20 = 20, etc.

Index entries for linear recurrences with constant coefficients, signature (1,1,-1,0,0,1,-1,-1,1).

Cf. A000217, A264041, A260708.

[n*(n+1)/2-(1+(-1)^n)*Floor(n/6+2/3)/2: n in [0..50]]; // Bruno Berselli, Nov 18 2015

LinearRecurrence[{1, 1, -1, 0, 0, 1, -1, -1, 1}, {0, 1, 2, 6, 9, 15, 20, 28, 34}, 50] (* Bruno Berselli, Nov 18 2015 *)

[n*(n+1)/2-(1+(-1)^n)*floor(n/6+2/3)/2 for n in (0..50)] # Bruno Berselli, Nov 18 2015

G.f.: x*(1 + x + 3*x^2 + 2*x^3 + 2*x^4 + 2*x^5 + x^6)/((1 - x)^3*(1 + x)^2*(1 - x + x^2)*(1 + x + x^2)).
a(n) = a(n-1) +  a(n-2) - a(n-3) + a(n-6) - a(n-7) - a(n-8) + a(n-9).
a(2*k+1) = A000217(2*k+1) by definition; for even indices:
a(6*k)   = 2*k*(9*k + 1),
a(6*k+2) = 2*(9*k^2 + 7*k + 1),
a(6*k+4) = 18*k^2 + 26*k + 9.
a(n) = n*(n + 1)/2 - (1 + (-1)^n)*floor(n/6 + 2/3)/2. [Bruno Berselli, Nov 18 2015]

Edited by Bruno Berselli, Nov 17 2015

A264938 a(n) = n(2n-1) + floor(n/3).

Original entry on oeis.org

0, 1, 6, 16, 29, 46, 68, 93, 122, 156, 193, 234, 280, 329, 382, 440, 501, 566, 636, 709, 786, 868, 953, 1042, 1136, 1233, 1334, 1440, 1549, 1662, 1780, 1901, 2026, 2156, 2289, 2426, 2568, 2713, 2862, 3016, 3173, 3334, 3500, 3669, 3842, 4020, 4201, 4386, 4576, 4769

Offset: 0

Paul Curtz, Nov 29 2015

Sequence extended to the left:
..., 133, 102, 76, 53, 34, 20, 9, 2, 0, 1, 6, 16, 29, 46, 68, 93, ...
Conjecture: after 0, a(n) provides the first bisection of A264041.
Conjecture: 2, 9, 20, 34, 53, 76, 102, 133, ... is A248121.

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for two-way infinite sequences
Index entries for linear recurrences with constant coefficients, signature (2,-1,1,-2,1).

Second bisection of A260708.
Cf. A000217, A002264, A016777, A016969, A017197, A017641, A099837, A248121, A256320, A260699, A264041.
Cf. A171452: A000217(n-1) + A002264(n).

[n*(2*n-1)+Floor(n/3): n in [0..60]]; // Vincenzo Librandi, Dec 02 2015

seq(n*(2*n-1) + floor(n/3), n=0..100); # Robert Israel, Dec 02 2015

Table[n (2 n - 1) + Floor[n/3], {n, 0, 50}] (* Vincenzo Librandi, Dec 02 2015 *)
LinearRecurrence[{2,-1,1,-2,1},{0,1,6,16,29},60] (* Harvey P. Dale, Oct 13 2020 *)

concat(0, Vec(x*(1+x)^2*(1+2*x)/((1-x)^3*(1+x+x^2)) + O(x^100))) \\ Colin Barker, Dec 02 2015

a(n) = n*(2*n-1) + n\3; \\ Altug Alkan, Dec 01 2015

a(n) = a(n-3) + 12*n - 20 for n>2.
From Colin Barker, Dec 02 2015: (Start)
a(n) = 2*a(n-1) - a(n-2) + a(n-3) - 2*a(n-4) + a(n-5) for n>4.
G.f.: x*(1+x)^2*(1+2*x) / ((1-x)^3*(1+x+x^2)).
(End)
a(n) = A000217(2n-1) + A002264(n).
a(n) + a(-n) = 3*A256320(n).
a(n +8) - a(n -7) = 20*A016777(n).
a(n+16) - a(n-14) = 20*A016969(n).
a(n+23) - a(n-22) = 20*A017197(n).
a(n+31) - a(n-29) = 20*A017641(n).
Generalization of the previous four formulas:
a(n+30*k +8) - a(n-30*k -7) = 20*(4*k+1)*(3*n+1).
a(n+30*k+16) - a(n-30*k-14) = 20*(2*k+1)*(6*n+5).
a(n+30*k+24) - a(n-30*k-21) = 20*(4*k+3)*(3*n+4).
a(n+30*k+32) - a(n-30*k-28) = 20*(2*k+2)*(6*n+11).
E.g.f.: (6*x^2+4*x-1)*exp(x)/3 + (cos(sqrt(3)*x/2)/3 +sqrt(3)*sin(sqrt(3)*x/2)/9)*exp(-x/2). - Robert Israel, Dec 02 2015

Edited by Bruno Berselli, Dec 01 2015

A260307 a(n) = a(n-1) + a(n-2) - a(n-3) + a(n-6) - a(n-7) - a(n-8) + a(n-9) with a(0) - a(8) as shown below.

Original entry on oeis.org

1, 2, 3, 4, 6, 5, 8, 7, 10, 9, 13, 10, 15, 12, 17, 14, 20, 15, 22, 17, 24, 19, 27, 20, 29, 22, 31, 24, 34, 25, 36, 27, 38, 29, 41, 30, 43, 32, 45, 34, 48, 35, 50, 37, 52, 39, 55, 40, 57, 42, 59, 44, 62, 45, 64, 47, 66, 49, 69, 50, 71, 52, 73, 54, 76, 55, 78

Offset: 0

Paul Curtz, Nov 22 2015

A260708 difference table rows have the same nine-step recurrence:
0, 1, 3,  6, 10, 16, 21, 29, 36, 46, 55, 65, 78,  93, ...
1, 2, 3,  4,  6,  5,  8,  7, 10,  9, 13, 10, 15,  12, ...     = a(n)
1, 1, 1,  2, -1,  3, -1,  3, -1,  4, -3,  5, -3,   5, ...     = b(n)
0, 0, 1, -3,  4, -4,  4, -4,  5, -7,  8, -8,  8,  -8, ... (see A042965(n)).
(b(2n) + b(2n+1) = A052901(n+2).)

G. C. Greubel, Table of n, a(n) for n = 0..1500
Index entries for linear recurrences with constant coefficients, signature (0,1,0,0,0,1,0,-1).

Cf. A004767, A010718, A042965, A047212, A047282, A052901, A152467, A260160 (eight-step recurrence), A260699 (nine-step recurrence), A260708.

I:=[1,2,3,4,6,5,8,7];[n le 8 select I[n] else Self(n-2) + Self(n-6) - Self(n-8): n in [1..70]]; // Vincenzo Librandi, Dec 26 2015

RecurrenceTable[{a[n] == a[n-2] + a[n-6] - a[n-8], a[0]=1, a[1]=2, a[2]=3, a[3]=4, a[4]=6, a[5]=5, a[6]=8, a[7]=7}, a, {n,0,100}] (* G. C. Greubel, Nov 23 2015 *)

Vec((x^6+x^5+3*x^4+2*x^3+2*x^2+2*x+1)/((x-1)^2*(x+1)^2*(x^2-x+1)*(x^2+x+1)) + O(x^100)) \\ Colin Barker, Nov 22 2015

vector(100, n, n--; n + (-1)^n *((n+2)\6) + 1) \\ Altug Alkan, Nov 24 2015

a(2n) = A047282(n). a(2n+1) = A047212(n+1).
a(n) = A260708(n+1) - A260708(n).
a(n+6) = a(n) + period of length 2: repeat 7, 5.
a(2n) + a(2n+1) = 3 + 4*n.
a(n) = n + 1 + (-1)^n*A152467(n+2).
From Colin Barker, Nov 22 2015: (Start)
a(n) = a(n-2) + a(n-6) - a(n-8) for n>7.
G.f.: (x^6+x^5+3*x^4+2*x^3+2*x^2+2*x+1) / ((x-1)^2*(x+1)^2*(x^2-x+1)*(x^2+x+1)).
(End)

A265228 Interleave the even numbers with the numbers that are congruent to {1, 3, 7} mod 8.

Original entry on oeis.org

0, 1, 2, 3, 4, 7, 6, 9, 8, 11, 10, 15, 12, 17, 14, 19, 16, 23, 18, 25, 20, 27, 22, 31, 24, 33, 26, 35, 28, 39, 30, 41, 32, 43, 34, 47, 36, 49, 38, 51, 40, 55, 42, 57, 44, 59, 46, 63, 48, 65, 50, 67, 52, 71, 54, 73, 56, 75, 58, 79, 60, 81, 62, 83, 64, 87, 66

Offset: 0

Paul Curtz, Dec 06 2015

b(n) denotes the sequence:
0, 0, 0, 0, 0, 0, 1, -1, 1, -1, 1, -1, 1, 2, -2, 2, -2, 2, -2, 2, 3, -3, 3, -3, 3, -3, 3, 4, -4, ..., and
c(n) = n + b(n) = n + floor((n+1)/7)*(-1)^((n+1) mod 7) provides:
0, 1, 2, 3, 4, 5, 7, 6, 9, 8, 11, 10, 13, 15, 12, 17, 14, 19, 16, 21, 23, 18, 25, 20, 27, 22, 29, ..., which is a permutation of A001477.
a(n) differs from c(n) because c(n) contains the terms of the form 8*k+5.

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (0,1,0,0,0,1,0,-1).

Cf. A001477, A004770, A005843, A047529, A079979, A260160, A260699, A260708.

lim = 11; Riffle[Range[0, 6 lim, 2], Select[Range[8 lim], MemberQ[{1, 3, 7}, Mod[#, 8]] &]] (* Michael De Vlieger, Dec 06 2015 *)

concat(0, Vec(x*(1+2*x+2*x^2+2*x^3+4*x^4+2*x^5+x^6)/((1-x)^2 *(1+x)^2*(1-x+x^2)*(1+x+x^2)) + O(x^100))) \\ Colin Barker, Dec 06 2015

vector(100, n, n--; n+(1-(-1)^n)*floor(n/6+1/3)) \\ Altug Alkan, Dec 09 2015

a(n) = n + 2*A260160(n) = n + (1-(-1)^n)*floor(n/6+1/3). Therefore, for odd n, a(n) = A047529((n+1)/2); otherwise, a(n) = n.
a(n) = a(n-6) - (-1)^n + 7.
a(n) = A260708(n) - A260699(n-1) - A079979(n+3), with A260699(-1) = 0.
From Colin Barker, Dec 06 2015: (Start)
a(n) = a(n-2) + a(n-6) - a(n-8) for n > 7.
G.f.: x*(1+2*x+2*x^2+2*x^3+4*x^4+2*x^5+x^6) / ((1-x)^2*(1+x)^2*(1-x+x^2)*(1+x+x^2)). (End)

cp's OEIS Frontend

A264041 a(n) is the maximum number of diagonals that can be placed in an n X n grid made up of 1 X 1 unit squares when diagonals are placed in the unit squares in such a way that no two diagonals may cross or intersect at an endpoint.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A260699 a(2n+6) = a(2n) + 12*n + 20, a(2n+1) = (n+1)*(2*n+1), with a(0)=0, a(2)=2, a(4)=9.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Sage

Formula

Extensions

A264938 a(n) = n*(2*n-1) + floor(n/3).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

Extensions

A260307 a(n) = a(n-1) + a(n-2) - a(n-3) + a(n-6) - a(n-7) - a(n-8) + a(n-9) with a(0) - a(8) as shown below.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Formula

A265228 Interleave the even numbers with the numbers that are congruent to {1, 3, 7} mod 8.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A260699 a(2n+6) = a(2n) + 12n + 20, a(2n+1) = (n+1)(2*n+1), with a(0)=0, a(2)=2, a(4)=9.

A264938 a(n) = n(2n-1) + floor(n/3).