A264041 -id:A264041 - cp's OEIS frontend

A264667 Number of optimal solutions to the maximal number of diagonals problem studied in A264041.

2, 4, 28, 108, 2, 13968, 480, 7914054, 433284, 18726123500, 256, 178290006448984, 14454384, 6631290958957860856, 1401615406696, 941558205279187913101914, 1767136, 500995759754153499284692617816, 31163356068736, 984452644453618816989710782436259368

Offset: 1

Rob Pratt, Nov 20 2015

nonn

Solutions that differ by a rotation and/or reflection are counted as different. - N. J. A. Sloane, Nov 20 2015

The paper by Boyland et al. gives a(13) = 14454384 and a(15) = 1401615406696. - Eric M. Schmidt, Aug 30 2017

			For n=2 the 4 solutions are:
.\
\\
--
/.
//
--
\\
\.
--
//
./
--
where the dot indicates an empty cell.

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.

Cf. A264041.

a(8)-a(13) from Andrew Howroyd, Feb 03 2018

a(14)-a(20) from Andrew Howroyd, Jun 22 2018

A299017 Intersection of A264041 and A000217.

Original entry on oeis.org

1, 3, 6, 10, 21, 36, 55, 78, 105, 136, 171, 210, 253, 300, 351

Offset: 1

Colin Barker, Jan 31 2018

Cf. A000217, A264041.

Conjectures (Start)
G.f.: x*(1 + 6*x^4 - 3*x^5) / (1 - x)^3.
a(n) = 6 - 7*n + 2*n^2 for n>3.
a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) for n>3.
(End)

A260708 a(2n) = n(2n+1), a(2n+7) = a(2n+1) + 12*n + 28, with a(1)=1, a(3)=6, a(5)=16.

Original entry on oeis.org

0, 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, 566, 595, 636, 666, 709, 741, 786, 820, 868, 903, 953, 990, 1042, 1081, 1136, 1176, 1233, 1275, 1334, 1378

Offset: 0

Paul Curtz, Nov 17 2015

Conjecture: this sequence is 0 followed by A264041.
After 3, if a(n) is prime then n == 1 (mod 6).
a(n) is a square for n = 0, 1, 5, 8, 145, 288, 1777, 6533, 9800, 168097, 332928, 2051425, 7539845, ...

			a(0) = 0*1 = 0,
a(1) = 1,
a(2) = 1*3 = 3,
a(3) = 6,
a(4) = 2*5 = 10,
a(5) = 16,
a(6) = 3*7 = 21,
a(7) = a(1) +12*0 +28 = 29, etc.

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

Cf. A000217, A008615, A014105, A260160, A260699, A264041.

LinearRecurrence[{1, 1, -1, 0, 0, 1, -1, -1, 1}, {0, 1, 3, 6, 10, 16, 21, 29, 36}, 50] (* Bruno Berselli, Nov 18 2015 *)

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

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

From Colin Barker, Nov 17 2015: (Start)
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)).
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>8. (End)
a(2*k)   = A000217(2*k) by definition; for odd indices:
a(6*k+1) = 18*k^2 + 10*k + 1,
a(6*k+3) = 2*(9*k^2 + 11*k + 3),
a(6*k+5) = 2*(k + 1)*(9*k + 8), that is A178574.
a(n) = A260699(n) + A008615(n).
a(n) = n*(n + 1)/2 + (1 - (-1)^n)*floor(n/6 + 1/3)/2. [Bruno Berselli, Nov 18 2015]

Edited by Bruno Berselli, Nov 18 2015

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

A260160 a(n) = a(n-2) + a(n-6) - a(n-8) with n>8, the first eight terms are 0 except that for a(5) = a(7) = 1.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 2, 0, 2, 0, 2, 0, 3, 0, 3, 0, 3, 0, 4, 0, 4, 0, 4, 0, 5, 0, 5, 0, 5, 0, 6, 0, 6, 0, 6, 0, 7, 0, 7, 0, 7, 0, 8, 0, 8, 0, 8, 0, 9, 0, 9, 0, 9, 0, 10, 0, 10, 0, 10, 0, 11, 0, 11, 0, 11, 0, 12, 0, 12, 0, 12, 0, 13, 0, 13, 0, 13, 0, 14, 0, 14, 0, 14

Offset: 1

Jean-François Alcover and Paul Curtz, Nov 09 2015

Sequence related to A264041 (1 is the offset of A264041).

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

Cf. A000004 (second bisection), A000217, A002264 (for the first bisection), A264041.

with(numtheory): P:= proc(q) local n; for n from 0 to q do
print((1-(-1)^n)*floor(n/6+1/3)/2); od; end: P(100); # Paolo P. Lava, Nov 12 2015

LinearRecurrence[{0, 1, 0, 0, 0, 1, 0, -1}, {0, 0, 0, 0, 1, 0, 1, 0}, 100]
Table[(1 - (-1)^n) (Floor[n/6 + 1/3]/2), {n, 1, 90}] (* Bruno Berselli, Nov 10 2015 *)

concat(vector(4), Vec(x^5/(1-x^2-x^6+x^8) + O(x^100))) \\ Altug Alkan, Nov 10 2015

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

G.f.: x^5/(1-x^2-x^6+x^8).
a(n) = A264041(n) - n*(n+1)/2, 026).
a(n) = (1-(-1)^n)*floor(n/6+1/3)/2. [Bruno Berselli, Nov 10 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

A260690 Array read by antidiagonals: D(w,h) is the maximum number of diagonals that can be placed in a w X h grid made up of 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.

Original entry on oeis.org

1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 6, 5, 5, 6, 6, 8, 8, 6, 6, 7, 7, 10, 10, 10, 7, 7, 8, 8, 12, 12, 12, 12, 8, 8, 9, 9, 14, 14, 16, 14, 14, 9, 9, 10, 10, 16, 16, 18, 18, 16, 16, 10, 10, 11, 11, 18, 18, 21, 21, 21, 18, 18, 11, 11, 12, 12, 20, 20, 24, 24, 24, 24, 20, 20, 12, 12

Offset: 1

Gabriella Pinter and Jon E. Schoenfield, Nov 15 2015

In other words, D(w,h) is the largest number of nonintersecting vertex-disjoint diagonals that can be packed in a w X h grid.
For the results for square grids (i.e., w=h), see A264041.
If at least one of the two dimensions is even, then the simple packing using the nested L-shape pattern as described in the third Pinter link at A264041 gives an optimal solution, and formulas for the number of diagonals are given below.
If, however, both dimensions are odd, it may be more difficult to find a way to pack the maximum number of diagonals or to determine what that maximum number D(w,h)is. D(w,h) is known (see Example section) for all odd-odd pairs (w,h) in which at least one dimension is less than 19.
Let L(w,h) be the number of diagonals packed in a w X h grid using the nested L-shape pattern described above, and define K(w,h) as the margin by which the number of diagonals in an optimal solution exceeds the number that would be packed using the nested L-shape pattern; i.e., K(w,h) = D(w,h) - L(w,h). If at least one of the two dimensions is even, then K(w,h) = 0; values of K(w,h) when both w and h are odd are shown in a table in the Example section.
Let B(w,h) be the number of optimal solutions (i.e., distinct configurations of D(w,h) diagonals) for a w X h grid; then known results for odd-odd pairs (w,h) include B(1,1) = 2; B(3,3) = 28; B(5,5) = 2; B(7,7) = 480, B(7,9) = 32; B(9,9) = 433284, B(9,11) = 85328, B(9,13) = 7568, B(9,15) = 256; B(11,11) = 256, ..., B(11,17) = 15813376, B(11,19) = 980224, B(11,21) = 25088. The relative scarcity of optimal solutions at a given dimension pair (w,h) may be seen as indicative of the amount of "slack" available for construction of an optimal solution at that pair; e.g., among cases with w=11, there are relatively few solutions (only 256) at h=11 (a (w,h) combination at which a K(w,h)=2 solution is just barely possible), while solutions at h values where K(w,h)=1 do not exist at all for h>21, are just possible at h=21, and become extremely plentiful as h is decreased from 21 to 13.

			The table begins as follows:
.
  h\w| 1  2  3  4  5  6  7  8  9 10 11 12 13
  ---+--------------------------------------
    1| 1  2  3  4  5  6  7  8  9 10 11 12 13
    2| 2  3  4  5  6  7  8  9 10 11 12 13 14
    3| 3  4  6  8 10 12 14 16 18 20 22 24 26
    4| 4  5  8 10 12 14 16 18 20 22 24 26 28
    5| 5  6 10 12 16 18 21 24 27 30 33 36 39
    6| 6  7 12 14 18 21 24 27 30 33 36 39 42
    7| 7  8 14 16 21 24 29 32 37 40 44 48 52
    8| 8  9 16 18 24 27 32 36 40 44 48 52 56
    9| 9 10 18 20 27 30 37 40 46 50 56 60 66
   10|10 11 20 22 30 33 40 44 50 55 60 65 70
   11|11 12 22 24 33 36 44 48 56 60 68 72 79
   12|12 13 24 26 36 39 48 52 60 65 72 78 84
   13|13 14 26 28 39 42 52 56 66 70 79 84 93
.
If at least one of the dimensions (w,h) is even, the exact value of D(w,h) is given by the appropriate formula in the Formula section. A table consisting of only the terms for which both dimensions are odd begins as follows:
.
  h\w| 1   3   5   7   9  11  13  15  17  19  21  23  25
  ---+--------------------------------------------------
    1| 1   3   5   7   9  11  13  15  17  19  21  23  25
    3| 3   6  10  14  18  22  26  30  34  38  42  46  50
    5| 5  10  16  21  27  33  39  45  51  57  63  69  75
    7| 7  14  21  29  37  44  52  60  68  76  84  92 100
    9| 9  18  27  37  46  56  66  76  85  95 105 115 125
   11|11  22  33  44  56  68  79  91 103 115 127 138 150
   13|13  26  39  52  66  79  93 107 120 134 148 162 176
   15|15  30  45  60  76  91 107 122 138 154 169 185 201
   17|17  34  51  68  85 103 120 138 156 173 191 209 227
   19|19  38  57  76  95 115 134 154 173 193 213 232 252
   21|21  42  63  84 105 127 148 169 191 213 234 256 278
   23|23  46  69  92 115 138 162 185 209 232 256 280 303
   25|25  50  75 100 125 150 176 201 227 252 278 303 329
.
The table below shows (with known 0 values replaced by periods and unknown values left blank, for readability) the differences by which D(w,h) exceeds the number of diagonals resulting from application of the simple nested L-shape pattern referred to above:
.
                 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5
  h\w| 1 3 5 7 9 1 3 5 7 9 1 3 5 7 9 1 3 5 7 9 1 3 5 7 9 1
  ---+----------------------------------------------------
    1| . . . . . . . . . . . . . . . . . . . . . . . . . .
    3| . . . . . . . . . . . . . . . . . . . . . . . . . .
    5| . . 1 . . . . . . . . . . . . . . . . . . . . . . .
    7| . . . 1 1 . . . . . . . . . . . . . . . . . . . . .
    9| . . . 1 1 1 1 1 . . . . . . . . . . . . . . . . . .
   11| . . . . 1 2 1 1 1 1 1 . . . . . . . . . . . . . . .
   13| . . . . 1 1 2 2 1 1 1 1 1 1 1 . . . . . . . . . . .
   15| . . . . 1 1 2 2 2 2 1 1 1 1 1 1 1 1 1 . . . . . . .
   17| . . . . . 1 1 2 3 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 . .
   19| . . . . . 1 1 2 2 3 3 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
   21| . . . . . 1 1 1 2 3 3 3 3 2 2 2 2 2 2
   23| . . . . . . 1 1 2 2 3 4 3 3 3
   25| . . . . . . 1 1 2 2 3 3 4 4
   27| . . . . . . 1 1 1 2 2 3 4
   29| . . . . . . 1 1 1 2 2 3     5
   31| . . . . . . . 1 1 2 2
   33| . . . . . . . 1 1 1 2
   35| . . . . . . . 1 1 1 2
   37| . . . . . . . 1 1 1 2
   39| . . . . . . . . 1 1
   41| . . . . . . . . 1 1
   43| . . . . . . . . 1 1
   45| . . . . . . . . 1 1
   47| . . . . . . . . 1 1
   49| . . . . . . . . . 1
   51| . . . . . . . . . 1

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.

A264041 gives the terms along the main diagonal.

D(n,n) = A264041(n).
If exactly one of the dimensions w and h is even, then D(w,h) = x*(y+1)/2 where x and y are the even and odd dimensions, respectively.
If both dimensions are even, then D(w,h) = (x/2)*(y+1) where x is the smaller dimension.
If both dimensions are odd, it can be shown (see Links) that D(w,h) >= (2*s-1)*t + floor((2*sqrt(s^2-s*t+t^2) - 2*s + t)/3) where s = (max(w,h)+1)/2 and t = (min(w,h)+1)/2.

cp's OEIS Frontend

A264667 Number of optimal solutions to the maximal number of diagonals problem studied in A264041.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A299017 Intersection of A264041 and A000217.

Views

Author

Keywords

Crossrefs

Formula

A260708 a(2n) = n*(2*n+1), a(2n+7) = a(2n+1) + 12*n + 28, with a(1)=1, a(3)=6, a(5)=16.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Sage

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

A260160 a(n) = a(n-2) + a(n-6) - a(n-8) with n>8, the first eight terms are 0 except that for a(5) = a(7) = 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

Extensions

A260690 Array read by antidiagonals: D(w,h) is the maximum number of diagonals that can be placed in a w X h grid made up of 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

A260708 a(2n) = n(2n+1), a(2n+7) = a(2n+1) + 12*n + 28, with a(1)=1, a(3)=6, a(5)=16.

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