cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A289233 Largest number of disjoint point triples that can be chosen from an n X n X n triangular point grid, each point triple forming a 2 X 2 X 2 triangle.

Original entry on oeis.org

0, 1, 1, 3, 4, 6, 9, 11, 15, 18, 22, 26, 30, 35, 39, 45, 50, 56, 63, 69, 77, 84, 92, 100, 108, 117, 125, 135, 144, 154, 165, 175, 187, 198, 210, 222, 234, 247, 259, 273, 286, 300, 315, 329, 345, 360, 376, 392, 408, 425, 441, 459, 476, 494, 513, 531, 551, 570
Offset: 1

Views

Author

Heinrich Ludwig, Jul 08 2017

Keywords

Comments

A001840(n-1) = floor(n*(n+1)/6) is a trivial upper bound for a(n), which is not reached for n = 3, 5, 6, 8, 15, 17, 18, 20 but for all other n <= 21.
From Jon E. Schoenfield, Aug 16 2017: (Start)
If n is even, then the bottom three rows of points can be assembled into n-1 of the 3-point triangles; e.g., the full grid for n = 8 has 8*9/2 = 36 points, of which the 21 points in the bottom three rows can be assembled into 7 three-point triangles as follows, leaving the remaining 15 points in the same triangular arrangement as in the full grid for the n = 5 case:
.
Row 1: .
.
Row 2: . .
.
Row 3: . . .
.
Row 4: . . . .
.
Row 5: . . . . .
.
Row 6: 2---2 4---4 6---6
. \ / \ / \ /
Row 7: 1 2 3 4 5 6 7
. / \ / \ / \ / \
Row 8: 1---1 3---3 5---5 7---7
.
Thus, if n is even, then a(n) >= a(n-3) + n - 1.
Similarly, if n mod 3 = 2, then the bottom two rows of points can be assembled into (2n-1)/3 of the 3-point triangles; e.g., of the 36 points in the full grid for n = 8, the 15 points in the bottom two rows can be assembled into 5 three-point triangles as follows, leaving the remaining 21 points in the same triangular arrangement as in the full grid for the n=6 case:
.
Row 1: .
.
Row 2: . .
.
Row 3: . . .
.
Row 4: . . . .
.
Row 5: . . . . .
.
Row 6: . . . . . .
.
Row 7: 1 2---2 3 4---4 5
. / \ \ / / \ \ / / \
Row 8: 1---1 2 3---3 4 5---5
.
Thus, if n mod 3 = 2, then a(n) >= a(n-2) + (2n-1)/3.
Given the terms through a(21) = 77, the two lower bounds above and the upper bound a(n) <= floor(n(n+1)/6) are sufficient to establish that a(22) = 84, a(23) = 92, a(24) = 100, a(26) = 117, and a(28) = 135. (A solution with 108 three-point triangles can be constructed on the n = 25 grid.)
Conjecture: a(n) = floor((n(n+1) - floor(((n+3) mod 12)/6))/6); i.e., the upper bound floor(n(n+1)/6) can be reached unless n(n+1)/2 is a multiple of 3 and (n+3) mod 12 >= 6, in which case a(n) falls short of the upper bound by 1. (End)
a(31) = 165, a(33) = 187, a(34) = 198, a(35) = 210, a(36) = 222, a(37) = 234, a(38) = 247, and a(40) = 273. - Rob Pratt, Dec 19 2017
From Jon E. Schoenfield, Dec 21 2017: (Start)
If we refer to a triangular grid with n points on each side simply as an "n-triangle", then for any n > 13, the n-triangle can be broken into an (n-12)-triangle, a 12-triangle, and a parallelogram-shaped grid with 12 points on each of two opposite sides and n-12 points on each of the other two sides (with n-12 > 1). E.g., we can break the 21-triangle into (1) a 9-triangle, (2) a 12-triangle, and (3) a 9 X 12 parallelogram grid:
_________
1 ^
1 1 |
1 1 1 |
1 1 1 1 |
1 1 1 1 1 9
1 1 1 1 1 1 |
1 1 1 1 1 1 1 |
1 1 1 1 1 1 1 1 |
1 1 1 1 1 1 1 1 1__v
_______________
2 3 3 3 3 3 3 3 3 3 ^
2 2 3 3 3 3 3 3 3 3 3 |
2 2 2 3 3 3 3 3 3 3 3 3 |
2 2 2 2 3 3 3 3 3 3 3 3 3 |
2 2 2 2 2 3 3 3 3 3 3 3 3 3 |
2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 12
2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 |
2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 |
2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 |
2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 |
2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 |
2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 ____v
| || |
|<---------12---------->||<-------9------->|
.
All points of a 2 X 12 parallelogram grid and all points of a 3 X 12 parallelogram grid can be assembled into 3-point triangles using the simple patterns
.
o o o o .
o . o . .
. . o o .
o o o . .
o . o o .
. . and o . .
o o o o .
o . o . .
. . o o .
o o o . .
o . o o .
. . o . .
.
respectively, so those patterns can be combined to assemble a k X 12 parallelogram completely into 3-point triangles for any k > 1. Thus, since both the 12-triangle and the (n-12) X 12 parallelogram grid can be completely assembled into 3-point triangles for any n > 13, we have, for n > 13, a(n) >= a(n-12) + a(12) + (n-12)*12/3, which reduces to a(n) >= a(n-12) + 4n - 22. In particular, if the trivial upper bound floor(n*(n+1)/6) is reached by a(n), then it is also reached by a(n+12k) for any positive integer k. Given a(1)..a(12), this is sufficient to prove that a(n) = floor(n*(n+1)/6) except when n mod 12 is 3, 5, 6, or 8; in those cases, a(n) >= floor(n*(n+1)/6) - 1. (End)
Theorem 1.1 of the Conway and Lagarias link indicates that all the points can be covered by 3-point triangles iff n mod 12 = 0, 2, 9, or 11. That fact, together with the above results for a(n) in the specific cases for n in [1, 3..8, 10] and the recursive lower bound a(n) >= a(n-12) + 4n - 22, is sufficient to prove that a(n) = floor(n*(n+1)/6) - d where d is 1 when n mod 12 is in [3, 5, 6, 8] and 0 otherwise. - Jon E. Schoenfield, Dec 26 2017

Examples

			From a 21 X 21 X 21 point grid up to 77 disjoint 2 X 2 X 2 triangles (aaa, bbb, ...) can be chosen. Selections like the one below with no point left are very rare compared to C(400, 77). 400 is the total number of 2 X 2 X 2 triangles in the 21-grid.
                        a
                       a a
                      c c b
                     d c b b
                    d d f f e
                   h h g f e e
                  i h g g k k j
                 i i l m m k j j
                p p l l m n q q o
               r p s t t n n q o o
              r r s s t u w w x x v
             y a a b b u u w z x v v
            y y a c b d f f z z g g e
           j j h c c d d f i k k g e e
          l j h h m m n n i i k o o p p
         l l w w q m r n s x x t o u p v
        y z z w q q r r s s x t t u u v v
       y y z f f a g g b h h c i i d j j e
      k k l l f a a g b b h c c i d d j e e
     m k n l o u u p v v q w w r x x s y y t
    m m n n o o u p p v q q w r r x s s y t t

Links

Crossrefs

Cf. A001840, A289222, A289229.

Programs

  • Mathematica
    f[n_] := Floor[n (n +1)/6] - If[ !MemberQ[{3, 5, 6, 8}, Mod[n, 12]], 0, 1]; Array[f, 58] (* or *)
CoefficientList[ Series[(-x +x^2 -x^3 +x^4 -x^5)/((-1 +x)^3 (1 +x -x^3 +x^5 +x^6)), {x, 0, 57}], x] (* or *)
LinearRecurrence[{2, 0, -1, -2, 2, 1, 0, -2, 1}, {0, 1, 1, 3, 4, 6, 9, 11, 15}, 58] (* Robert G. Wilson v, Dec 26 2017 *)

Formula

G.f.: x*(1 - x + x^2 - x^3 + x^4) / ((1 - x)^3*(1 + x + x^2)*(1 - x^2 + x^4)) (conjectured). - Colin Barker, Jul 08 2017
a(n) = floor(n*(n+1)/6) except when n mod 12 is 3, 5, 6, or 8; in those cases, a(n) = floor(n*(n+1)/6) - 1. - Jon E. Schoenfield, Dec 25 2017

Extensions

a(22)-a(26) from Jon E. Schoenfield, Aug 16 2017
a(27)-a(28) from Rob Pratt, Dec 19 2017
More terms from Jon E. Schoenfield, Dec 25 2017

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.