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.

Showing 1-10 of 16 results. Next

A000938 Number of collinear point-triples in an n X n grid.

Original entry on oeis.org

0, 0, 8, 44, 152, 372, 824, 1544, 2712, 4448, 6992, 10332, 15072, 21012, 28688, 38520, 50880, 65480, 83640, 104676, 130264, 160556, 195848, 235600, 282840, 336384, 397136, 465876, 544464, 630684, 729744, 837744, 958384, 1091904, 1238520, 1400140, 1581384, 1776084
Offset: 1

Views

Author

Keywords

Comments

This is related to the no-3-in-line problem on an n X n grid.

Examples

			a(3) = 8: the 3 rows, 3 columns and 2 diagonals of a 3 X 3 grid.
		

References

  • M. A. Adena, D. A. Holton and P. A. Kelly, Some thoughts on the no-three-in-line problem, pp. 6-17 of Combinatorial Mathematics (Proceedings 2nd Australian Conf.), Lect. Notes Math. 403, 1974.
  • R. K. Guy, Unsolved combinatorial problems, pp. 121-127 of D. J. A. Welsh, editor, Combinatorial Mathematics and Its Applications. Academic Press, NY, 1971.
  • R. K. Guy and P. A. Kelly, The No-Three-Line Problem. Research Paper 33, Department of Mathematics, Univ. of Calgary, Calgary, Alberta, 1968. Condensed version in Canad. Math. Bull. Vol. 11, pp. 527-531, 1968.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Crossrefs

This is the main diagonal of the array in A334704.
Cf. A157882 for the 3-D version.

Programs

  • Maple
    a:=n->2*sum(sum((n - k + 1)*(n - m + 1)*igcd(k - 1, m - 1), k= 2.. n), m= 2.. n) - n^2*(n^2 - 1)/6;
    seq(a(n),n=2..30); # Dennis P. Walsh, Mar 02 2013
  • Mathematica
    a[n_] := 2*Sum[(n - k + 1)*(n - m + 1)*GCD[k - 1, m - 1], {m, 2, n}, {k, 2, n}] - n^2*((n^2 - 1)/6); Table[a[n], {n, 2, 30}] (* Jean-François Alcover, Jul 11 2012, after Ignacio Larrosa Cañestro *)

Formula

a(n) = 2*Sum(Sum((n - k + 1)*(n - m + 1)*gcd(k - 1, m - 1), k, 2, n), m, 2, n) - n^2(n^2 - 1)/6. - Ignacio Larrosa Cañestro, May 23 2010
a(n) = binomial(n^2, 3) - A045996(n). - Ignacio Larrosa Cañestro, May 23 2010

Extensions

Terms a(11) through a(30) from John W. Layman, Sep 21 2000
Typo in formula corrected by David Bevan, Jan 09 2012
Offset changed to 1 and initial 0 added. - N. J. A. Sloane, Jun 19 2020

A000755 No-3-in-line problem on n X n grid: total number of ways of placing 2n points on n X n grid so no 3 are in a line. No symmetries are taken into account.

Original entry on oeis.org

0, 1, 2, 11, 32, 50, 132, 380, 368, 1135, 1120, 4348, 3622, 10568, 30634, 46304, 55576, 152210
Offset: 1

Views

Author

Keywords

Comments

This means no three on any line, not just lines in the X or Y directions.

Examples

			a(3) = 2:
X X o ... o X X
X o X ... X o X
o X X ... X X o
		

References

  • M. A. Adena, D. A. Holton and P. A. Kelly, Some thoughts on the no-three-in-line problem, pp. 6-17 of Combinatorial Mathematics (Proceedings 2nd Australian Conf.), Lect. Notes Math. 403, 1974.
  • R. K. Guy, Unsolved combinatorial problems, pp. 121-127 of D. J. A. Welsh, editor, Combinatorial Mathematics and Its Applications. Academic Press, NY, 1971.
  • R. K. Guy and P. A. Kelly, The No-Three-Line Problem. Research Paper 33, Department of Mathematics, Univ. of Calgary, Calgary, Alberta, 1968. Condensed version in Canad. Math. Bull. Vol. 11, pp. 527-531, 1968.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Crossrefs

Cf. A000769 (inequivalent solutions).

Extensions

More terms from the Achim Flammenkamp web site, May 24 2005
a(17) and a(18) from Benjamin Chaffin, Apr 05 2006
Minor edits from N. J. A. Sloane, May 25 2010

A235453 Triangle T(n, k) = Number of non-equivalent (mod D_4) ways to arrange k indistinguishable points on an n X n square grid so that no three of them are collinear. Triangle read by rows.

Original entry on oeis.org

1, 0, 1, 2, 1, 1, 3, 8, 13, 15, 5, 1, 3, 21, 70, 181, 217, 142, 28, 4, 6, 49, 290, 1253, 3192, 4699, 3385, 1076, 110, 5, 6, 93, 867, 6044, 27041, 77970, 134353, 129929, 62177, 12511, 717, 11, 10, 171, 2266, 22302, 149217, 672506, 1958674, 3531747, 3695848, 2068757
Offset: 1

Views

Author

Heinrich Ludwig, Jan 12 2014

Keywords

Comments

The triangle T(n, k) is irregularly shaped: 1 <= k <= 2n. First row corresponds to n = 1.
Without the restriction "non-equivalent (mod D_4)" the numbers are given by triangle A194193. (But this one is read by antidiagonals!)
T(n, 2n) = A000769(n).
2n is an upper bound on the number of points that can be placed on the grid. For large n, it is conjectured that this bound is not reached (see MathWorld link).

Examples

			Triangle begins
1,  0;
1,  2,   1,    1;
3,  8,  13,   15,     5,     1;
3, 21,  70,  181,   217,   142,     28,      4;
6, 49, 290, 1253,  3192,  4699,   3385,   1076,   110,     5;
6, 93, 867, 6044, 27041, 77970, 134353, 129929, 62177, 12511, 717, 11;
...
		

Crossrefs

Column 1 is A008805
Column 2 is A014409
Column 3 is A235454
Column 4 is A235455
Column 5 is A235456
Column 6 is A235457
Column 7 is A235458

A272651 The no-3-in-line problem: maximal number of points from an n X n square grid so that no three lie on a line.

Original entry on oeis.org

1, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92
Offset: 1

Views

Author

N. J. A. Sloane, May 10 2016

Keywords

Comments

a(47) is the first open case.
It is conjectured that a(n) < 2n for all sufficiently large n.
A000769 has an extensive list of references and links.
Comment from Warren D. Smith, May 10 2015: 2n is a trivial upper bound, because if you pick 2n+1 points, then some three must lie on a horizontal line.
Apart from the offset this may be the same as A103517. - R. J. Mathar, May 13 2016

Crossrefs

Cf. A000769.

A219760 Martin Gardner's minimal no-3-in-a-line problem.

Original entry on oeis.org

1, 4, 4, 4, 6, 6, 8, 9, 10, 10, 12, 12, 14, 15, 16, 17, 18, 18, 20, 21, 22, 23, 24, 25, 26, 26, 28, 29, 30
Offset: 1

Views

Author

N. J. A. Sloane, Nov 29 2012

Keywords

Comments

a(n) is the minimal number of counters that can be placed on an n X n chessboard, no three in a line, such that adding one more counter on any vacant square will produce three in a line.
From Rob Pratt, Mar 29 2014: (Start)
Can be computed by using integer linear programming (ILP) as follows.
The ILP formulation uses two sets of binary decision variables:
x[i,j] = 1 if a queen appears in square (i,j), 0 otherwise
y[k] = 1 if line k contains exactly two queens, 0 otherwise
Let SQUARES[k] be the set of squares that appear in line k, and let LINES[i,j] be the set of lines that contain square (i,j), so that (i,j) is in SQUARES[k] iff k is in LINES[i,j]. Then we have the following constraints:
2 y[k] <= sum {(i,j) in SQUARES[k]} x[i,j] <= 1 + y[k] for all lines k [no 3-in-a-line, and if y[k] = 1 then exactly two queens appear in line k]
x[i,j] + sum {k in LINES[i,j]} y[k] >= 1 for all squares (i,j) [either a queen appears in square (i,j) or some line that contains square (i,j) contains exactly two queens]
The objective is to minimize the sum of all x[i,j].
(End)
From Don Knuth, Aug 26 2014: (Start)
a(26)=26: there is a solution in which every queen appears in an odd-numbered row and an odd-numbered column, and furthermore cell (i,j) is occupied if and only if cell (j,i) is occupied. Such solutions exist when n=10, 18, 26. Conversely it's known that a(n)>=n when n is even.
There are many ways to place n+1 queens that satisfy the conditions, with queens occupying only "white" squares (if the top left corner square is white), at least for n<=30.
(End)
This is for the "queens" version of the problem, where "lines" are vertical, horizontal and diagonal only. The version where lines can have any slope is A277433. - Robert Israel, Oct 26 2016

Crossrefs

Extensions

Terms a(13)-a(18) from Rob Pratt, Mar 29 2014
Terms a(19)-a(27) from Rob Pratt, Sep 05 2014
a(28)-a(29) from Andy Huchala, Apr 20 2024

A181018 Maximum number of 1's in an n X n binary matrix with no three 1's adjacent in a line along a row, column or diagonally.

Original entry on oeis.org

1, 4, 6, 9, 16, 20, 26, 36, 42, 52, 64, 74, 86, 100, 114, 130
Offset: 1

Views

Author

R. H. Hardin, Sep 30 2010

Keywords

Comments

Diagonal of A181019.
Three or more "1"s may be adjacent in an L-shape or step shape (cf. bottom of first example) or 2 X 2 square (top right of 2nd example) or similar. One possible (not always optimal) solution is therefore to fill the square with 2 X 2 squares of "1"s, separated by rows of "0"s: this yields the lower bound (n - floor(n/3))^2 = ceiling(2n/3)^2 given in FORMULA. I conjecture that this is optimal for n = 2 (mod 3) and that a(n) ~ (2n/3)^2. For n = 3k, the array can be filled with 2k(2k+1) "1"s by repeating the optimal solution for n = 3 on the diagonal, and filling the rest with 2 X 2 blocks separated by rows of "0"s, cf. the 4th example for 6 X 6. - M. F. Hasler, Jul 17 2015 [Conjecture proved to be wrong, see below. - M. F. Hasler, Jan 19 2016]
74 <= a(12) <= 77. - Manfred Scheucher, Jul 23 2015
You can repeat a 4 X 2 block [1100; 0011] infinitely in both directions and then crop the needed square. That gives ceiling(n^2/2). It eventually surpasses the solutions we've found so far: at 17*17 the pattern above gives 12*12=144 but this one ceiling(17*17/2)=145. The credit for finding this goes to Jaakko Himberg. - Juhani Heino, Aug 11 2015

Examples

			Some solutions for 6 X 6:
  0 1 1 0 1 1    0 1 1 0 1 1    0 1 1 0 1 1    0 1 1 0 1 1
  1 0 1 0 0 1    1 0 1 0 1 1    1 0 1 0 0 1    1 0 1 0 1 1
  1 1 0 0 1 0    1 1 0 0 0 0    1 1 0 0 1 0    1 1 0 0 0 0
  0 0 0 0 1 1    0 0 0 0 1 1    0 0 0 0 1 1    0 0 0 0 1 1
  1 0 1 1 0 1    1 0 1 1 0 1    1 1 0 1 0 1    1 1 0 1 0 1
  1 1 0 1 1 0    1 1 0 1 1 0    1 1 0 1 1 0    1 1 0 1 1 0
A solution with 73 ones for 12 X 12 (I replaced "0" with "." for readability):
  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 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 . 1 1 . 1 1 . . 1 1
  1 . 1 . 1 1 . 1 . 1 . 1
- _Manfred Scheucher_, Jul 23 2015
An optimal solution with 74 ones (denoted by O) for 12 X 12 (also symmetric):
  O . O . O . O O . O O .
  O O . O O . . . O O . O
  . O . O . O O . . . O O
  O . . . O O . O O . O .
  . O O . . . O . . . . O
  O O . O O . O . O O . .
  . . O O . O . O O . O O
  O . . . . O . . . O O .
  . O . O O . O O . . . O
  O O . . . O O . O . O .
  O . O O . . . O O . O O
  . O O . O O . O . O . O - _Giovanni Resta_, Jul 29 2015
		

Crossrefs

Programs

  • Java
    See Taylor link
    (MATLAB with CPLEX)
    function v = A181018(n)
    %
    Grid = [1:n]' * ones(1,n) + n*ones(n,1)*[0:n-1];
    f = -ones(n^2,1);
    A = sparse(4*(n-2)*(n-1),n^2);
    count = 0;
    for i =1:n
      for j = 1:n-2
        count = count+1;
        A(count, [Grid(i,j),Grid(i,j+1),Grid(i,j+2)]) = 1;
      end
    end
    for i = 1:n-2
      for j = 1:n
        count = count+1;
        A(count, [Grid(i,j),Grid(i+1,j),Grid(i+2,j)]) = 1;
      end
    end
    for i = 1:n-2
      for j = 1:n-2
        count = count+2;
        A(count-1,[Grid(i,j+2),Grid(i+1,j+1),Grid(i+2,j)]) = 1;
        A(count, [Grid(i,j),Grid(i+1,j+1),Grid(i+2,j+2)]) = 1;
      end
    end
    b = 2*ones(4*(n-2)*(n-1),1);
    [x,v,exitflag,output] = cplexbilp(f,A,b);
    end;
    for n = 1:11
      A(n) = A181018(n);
    end
    A % Robert Israel, Jan 14 2016

Formula

a(n) >= ceiling(2n/3)^2; a(3k) >= A002943(k) = 2k(2k+1). - M. F. Hasler, Jul 17 2015; revised by Juhani Heino, Aug 11 2015
a(n) >= ceiling(n^2/2). - Juhani Heino, Aug 11 2015

Extensions

a(11)-a(12) from M. F. Hasler, Jul 20 2015
a(12) deleted by Manfred Scheucher, Jul 23 2015
a(12) from Giovanni Resta, Jul 29 2015
PARI code (which implemented a conjectured formula shown to underestimate) deleted by Peter J. Taylor, Jan 06 2016
a(13)-a(15) from Peter J. Taylor, Jan 09 2016
a(16) from Peter J. Taylor, Jan 14 2016

A213222 Minimum number of distinct slopes formed by n noncollinear points in the plane.

Original entry on oeis.org

3, 4, 4, 6, 6, 8, 8, 10, 10, 12, 12, 14, 14, 16, 16, 18, 18, 20, 20, 22, 22, 24, 24, 26, 26, 28, 28, 30, 30, 32, 32, 34, 34, 36, 36, 38, 38, 40, 40, 42, 42, 44, 44, 46, 46, 48, 48, 50, 50, 52, 52, 54, 54, 56, 56, 58, 58, 60, 60, 62, 62, 64, 64, 66, 66, 68, 68, 70, 70, 72, 72, 74, 74, 76, 76, 78, 78, 80, 80, 82, 82, 84
Offset: 3

Views

Author

Keywords

Comments

Scott formulated the problem (on the basis of a similar problem of Erdős), gave bounds, and conjectured the formula which Unger later proved.
Also the edge chromatic number of the n-polygon diagonal intersection graph. - Eric W. Weisstein, Mar 23 2018

References

  • Martin Aigner and Gunter M. Ziegler, Proofs from THE BOOK, Second Edition, Springer-Verlag, Berlin, 2000. Chapter 10.

Crossrefs

Cf. A000217 (maximum number of slopes, with offset 1).

Programs

  • Magma
    [2*Floor(n/2): n in [3..100]]; // Vincenzo Librandi, Mar 29 2014
  • Maple
    A213222:=n->`if`(n = 3, 3, 2*floor(n/2)); seq(A213222(n), n=3..100); # Wesley Ivan Hurt, Mar 28 2014
  • Mathematica
    CoefficientList[Series[(3 + x - 3 x^2 + x^3)/((1 + x) (1 - x)^2), {x, 0, 100}], x] (* Vincenzo Librandi, Mar 29 2014 *)
    LinearRecurrence[{1,1,-1},{3,4,4,6},100] (* Harvey P. Dale, Dec 29 2024 *)
  • PARI
    a(n)=if(n>3,n\2*2,3)
    

Formula

a(n) = 2*floor(n/2) for n > 3.
G.f.: x^3*(3+x-3*x^2+x^3)/((1+x)*(1-x)^2). [Bruno Berselli, Mar 04 2013]

A037189 Number of ways of placing 4n points on 2n X 2n grid so no 3 are in a line (solutions with either 90-degree rotational symmetry or full symmetry).

Original entry on oeis.org

0, 0, 3, 4, 6, 4, 13, 13, 7, 16, 8, 23, 36, 58, 92, 101, 172, 281, 337, 541, 746
Offset: 1

Views

Author

Keywords

Crossrefs

Cf. A000769.

Extensions

More terms (from Flammenkamp) from N. J. A. Sloane, May 24 2005
Edited by N. J. A. Sloane, Aug 29 2008 at the suggestion of R. J. Mathar

A212807 Number of ways to place 2n points on a 2n X 2n square array of points such that no three points are collinear and the configuration has 90-degree rotational symmetry.

Original entry on oeis.org

1, 1, 3, 4, 7, 4, 13, 13, 7, 16, 8, 23, 36, 58, 92, 101, 172, 281, 337, 541, 746
Offset: 1

Views

Author

N. J. A. Sloane, May 29 2012

Keywords

Comments

No such arrangement is possible on a 2n+1 X 2n+1 grid.

Crossrefs

Cf. A000769.

Extensions

a(11)-a(21) from Giovanni Resta, Mar 22 2013 (data from A. Flammenkamp's website)

A225623 Number of ways to arrange 2n queens on an n X n chessboard, with no more than 2 queens in each row, column or diagonal.

Original entry on oeis.org

0, 1, 2, 11, 92, 1097, 19448, 477136, 14244856, 537809179, 24194010708, 1317062528249
Offset: 1

Views

Author

Vaclav Kotesovec, Aug 04 2013

Keywords

Comments

This problem is slightly different from A000769 or A219760. In the first example on an 8 x 8 board, the queens c7, d5 and e3 (or queens a2, c5 and e8) are in a line, but such case is allowed. The elementary step can be only [0,1], [1,0] or [1,1], not for example [1,2] or [2,3].

Crossrefs

Extensions

Definition clarified by Vaclav Kotesovec, Dec 18 2014
a(10)-a(12) from Martin Ehrenstein, Jan 09 2022
Showing 1-10 of 16 results. Next