Robert Gerbicz - cp's OEIS frontend

A262355 Minimal number of circles needed to intersect all the points of an n X n grid.

1, 1, 3, 3, 5, 6, 8, 8, 11, 11, 14, 15

Offset: 1

Robert Gerbicz, Sep 19 2015

The n=2 and n=8 cases each have a unique solution.
a(13)=18 or 19; a(14)=19 or 20.
Lim a(n)/n^2=0. Moreover a(n)=O(n^2/sqrt(log(n))) is also true: use concentric circles with center=(0,0), for the squared distance to the points d^2=x^2+y^2<2*n^2 but with Landau's theorem there are only O(u/sqrt(log(u))) integers up to u which are in the form of x^2+y^2, use this for u=2*n^2 to get the theorem (obviously r=d for the radius). A closer center to the grid's center could give fewer circles, for example use center=(floor(n/2),floor(n/2)).

			In a two-dimensional vector format the optimal circles are given as the first two terms are the coordinates of the center, the third is the squared radius. If you don't see a particular n value then consider a larger one: for example, as a(9)=a(10), it is enough to give the circles only for n=10. Short Pari code to check these solutions: f(v,n)={a=matrix(n,n,i,j,0);L=length(v);for(i=1,L,x0=v[i][1];y0=v[i][2];r2=v[i][3];for(x=0,n-1,for(y=0,n-1,d2=(x-x0)^2+(y-y0)^2-r2;if(d2==0,a[x+1,y+1]=1)))); s=sum(i=1,n,sum(j=1,n,a[i,j]));print("Using ",L," circles, covered "s," points on the [0,",n-1"]^2 grid.")} Call for example f(v,8), where v is the vector listed for n=8.
n=2: 1 circle: v=[[1/2, 1/2, 1/2]];
n=4: 3 circles: v=[[3/2, 1/2, 5/2], [3/2, 3/2, 5/2], [3/2, 5/2, 5/2]];
n=5: 5 circles: v=[[3/2, 1/2, 5/2], [3/2, 3/2, 5/2], [1/2, 1/2, 25/2], [5/2, 5/2, 5/2], [13/6, 17/6, 85/18]];
n=6; 6 circles: v=[[3/2, 1/2, 5/2], [5/2, 2, 25/4], [5/2, 3, 25/4], [3/2, 9/2, 5/2], [7/2, 1/2, 5/2], [7/2, 9/2, 5/2]];
n=8: 8 circles: v=[[7/2, 7/2, 25/2], [5/2, 5/2, 25/2], [7/2, 7/2, 37/2], [5/2, 9/2, 25/2], [9/2, 5/2, 25/2], [9/2, 9/2, 25/2], [7/2, 7/2, 5/2], [7/2, 7/2, 1/2]];
n=10: 11 circles: v=[[9/2, 9/2, 25/2], [11/2, 11/2, 25/2], [7/2, 7/2, 25/2], [7/2, 11/2, 25/2], [11/2, 7/2, 25/2], [9/2, 9/2, 65/2], [9/2, 9/2, 53/2], [9/2, 9/2, 37/2], [9/2, 9/2, 5/2], [9/2, 1/2, 41/2], [9/2, 17/2, 41/2]];
n=11: 14 circles: v=[[13/2, 13/2, 25/2], [13/2, 9/2, 25/2], [11/2, 11/2, 25/2], [9/2, 13/2, 25/2], [9/2, 9/2, 25/2], [11/2, 11/2, 65/2], [11/2, 11/2, 5/2], [11/2, 11/2, 37/2], [9/2, 11/2, 65/2], [11/2, 9/2, 65/2], [15/2, 15/2, 125/2], [9/2, 9/2, 65/2], [11/2, -1/2, 61/2], [11/2, 21/2, 41/2]];
n=12: 15 circles: v=[[11/2, 11/2, 65/2], [13/2, 11/2, 65/2], [9/2, 11/2, 65/2], [15/2, 11/2, 25/2], [9/2, 11/2, 25/2], [15/2, 11/2, 65/2], [13/2, 11/2, 25/2], [11/2, 15/2, 13/2], [11/2, 7/2, 13/2], [7/2, 11/2, 65/2], [7/2, 11/2, 25/2], [11/2, 19/2, 65/2], [11/2, 3/2, 65/2], [103/10, 11/2, 1517/50], [7/10, 11/2, 1517/50]];

Mersenne Forum, Circles Puzzle
Erich Friedman (archive), Circles Through Points

For circular arcs, see A187679.

A188669 a(n) = ceiling(binomial(2*n-1,n-1)/n).

Original entry on oeis.org

1, 2, 4, 9, 26, 77, 246, 805, 2702, 9238, 32066, 112674, 400024, 1432736, 5170584, 18783763, 68635478, 252087092, 930138522, 3446163221, 12815663678, 47820430994, 178987624514, 671825076732, 2528212128756, 9536894864387, 36054433808299, 136583760727865, 518401146543812, 1971076359414358, 7506908923471954, 28634752202227978

Offset: 1

Robert Gerbicz and N. J. A. Sloane, Apr 07 2011

nonn

A useful lower bound when studying certain problems involving compositions.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

See A201058, A201059 for numerators and denominators without ceiling. - F. Chapoton, Aug 15 2021

[Ceiling(Binomial(2*n-1,n-1)/n): n in [1..60]]; // Vincenzo Librandi, Sep 07 2016

Table[Ceiling[Binomial[2 n - 1, n - 1]/n], {n, 35}]  (* Harvey P. Dale, Apr 09 2011 *)

A178916 Triangular array a(n,k) read by rows: nextprime(kn!)-kn!. For 1<=k<=n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 5, 5, 1, 1, 7, 1, 7, 7, 1, 7, 7, 1, 7, 7, 7, 11, 11, 1, 1, 19, 1, 1, 23, 11, 17, 1, 11, 1, 1, 11, 17, 29, 1, 1, 13, 1, 13, 1, 29, 11, 29, 1, 13, 1, 11, 11, 1, 1, 17, 1, 13, 17, 29, 1, 47, 13, 1, 13, 19, 17, 29, 1, 17, 59, 1, 1, 29, 1, 41, 29, 1, 1

Offset: 1

Dmitry Kamenetsky, Dec 29 2010 Robert Gerbicz, Dec 29 2010

Conjecture: for every n>1 and 1<=k<=n there is a prime in the interval [k*n!+1, k*n!+3*n*log(n)^2]. [Robert Gerbicz, Dec 28 2010]

			Triangle begins:
1
1,1
1,1,1
5,5,1,1
7,1,7,7,1
7,7,1,7,7,7
11,11,1,1,19,1,1
23,11,17,1,11,1,1,11
17,29,1,1,13,1,13,1,29
11,29,1,13,1,11,11,1,1,17
1,13,17,29,1,47,13,1,13,19,17
29,1,17,59,1,1,29,1,41,29,1,1

Flatten[Table[NextPrime[k*n!] - k*n!, {n, 12}, {k, n}]]

A180293 Number of arrangements of n indistinguishable balls in n boxes with the maximum number of balls in any box equal to n-3.

Original entry on oeis.org

1, 50, 195, 392, 672, 1080, 1650, 2420, 3432, 4732, 6370, 8400, 10880, 13872, 17442, 21660, 26600, 32340, 38962, 46552, 55200, 65000, 76050, 88452, 102312, 117740, 134850, 153760, 174592, 197472, 222530, 249900, 279720, 312132, 347282, 385320

Offset: 4

R. H. Hardin, formula from Robert Gerbicz in the Sequence Fans Mailing List, Aug 24 2010

nonn

R. H. Hardin, Table of n, a(n) for n=4..59

(n-3)rd entry in rows of A180281.

Empirical: a(n) = n*binomial(n+1, n-2) for n>6.

A180292 Number of arrangements of n indistinguishable balls in n boxes with the maximum number of balls in any box equal to n-2.

Original entry on oeis.org

1, 18, 50, 90, 147, 224, 324, 450, 605, 792, 1014, 1274, 1575, 1920, 2312, 2754, 3249, 3800, 4410, 5082, 5819, 6624, 7500, 8450, 9477, 10584, 11774, 13050, 14415, 15872, 17424, 19074, 20825, 22680, 24642, 26714, 28899, 31200, 33620, 36162, 38829, 41624

Offset: 3

R. H. Hardin, formula from Robert Gerbicz in the Sequence Fans Mailing List, Aug 24 2010

nonn

R. H. Hardin, Table of n, a(n) for n=3..59

(n-2)nd entry in rows of A180281.

Empirical: a(n)=n*binomial(n,n-2) for n>4.

A180300 Number of arrangements of n indistinguishable balls in n boxes with the maximum number of balls in any box equal to n-10.

Original entry on oeis.org

1, 73788, 1645215, 6838832, 16011905, 30931296, 55439448, 95585220, 160286166, 262462010, 420630210, 660990330, 1020099795, 1548293760, 2314026000, 3409331640, 4956643692, 7117231968, 10101573944, 14182012680, 19708107276

Offset: 11

R. H. Hardin, formula from Robert Gerbicz in the Sequence Fans Mailing List, Aug 24 2010

nonn

R. H. Hardin, Table of n, a(n) for n=11..59

n-10th entry in rows of A180281.

Empirical: a(n)=n*binomial(n+8,n-2) for n>20.

A180294 Number of arrangements of n indistinguishable balls in n boxes with the maximum number of balls in any box equal to n-4.

Original entry on oeis.org

1, 140, 735, 1652, 2970, 4950, 7865, 12012, 17745, 25480, 35700, 48960, 65892, 87210, 113715, 146300, 185955, 233772, 290950, 358800, 438750, 532350, 641277, 767340, 912485, 1078800, 1268520, 1484032, 1727880, 2002770, 2311575, 2657340, 3043287

Offset: 5

R. H. Hardin, formula from Robert Gerbicz in the Sequence Fans Mailing List, Aug 24 2010

nonn

R. H. Hardin, Table of n, a(n) for n=5..59

n-4th entry in rows of A180281.

Empirical: a(n) = n*binomial(n+2,n-2) for n>8.

A180296 Number of arrangements of n indistinguishable balls in n boxes with the maximum number of balls in any box equal to n-6.

Original entry on oeis.org

1, 1106, 9912, 27600, 54450, 96030, 160888, 259896, 406980, 620160, 922488, 1343034, 1917993, 2691920, 3719100, 5065060, 6808230, 9041760, 11875500, 15438150, 19879587, 25373376, 32119472, 40347120, 50317960, 62329344, 76717872

Offset: 7

R. H. Hardin, formula from Robert Gerbicz in the Sequence Fans Mailing List, Aug 24 2010

nonn

R. H. Hardin, Table of n, a(n) for n=7..59

n-6th entry in rows of A180281.

Empirical: a(n) = n*binomial(n+4,n-2) for n>12.

A180295 Number of arrangements of n indistinguishable balls in n boxes with the maximum number of balls in any box equal to n-5.

Original entry on oeis.org

1, 392, 2716, 6804, 12825, 22022, 36036, 56784, 86632, 128520, 186048, 263568, 366282, 500346, 672980, 892584, 1168860, 1512940, 1937520, 2457000, 3087630, 3847662, 4757508, 5839904, 7120080, 8625936, 10388224, 12440736, 14820498

Offset: 6

R. H. Hardin, formula from Robert Gerbicz in the Sequence Fans Mailing List, Aug 24 2010

nonn

R. H. Hardin, Table of n, a(n) for n=6..59

n-5th entry in rows of A180281

Empirical: a(n)=n*binomial(n+3,n-2) for n>10

A180297 Number of arrangements of n indistinguishable balls in n boxes with the maximum number of balls in any box equal to n-7.

Original entry on oeis.org

1, 3138, 35850, 110715, 228294, 412698, 705341, 1162800, 1860480, 2899248, 4412826, 6575976, 9614000, 13813800, 19536660, 27232920, 37458720, 50895000, 68368950, 90878112, 119617344, 156008864, 201735600, 258778080, 329455104

Offset: 8

R. H. Hardin, formula from Robert Gerbicz in the Sequence Fans Mailing List, Aug 24 2010

nonn

R. H. Hardin, Table of n, a(n) for n=8..59

n-7th entry in rows of A180281

Empirical: a(n)=n*binomial(n+5,n-2) for n>14

cp's OEIS Frontend

User: Robert Gerbicz

A262355 Minimal number of circles needed to intersect all the points of an n X n grid.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A188669 a(n) = ceiling(binomial(2*n-1,n-1)/n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

A178916 Triangular array a(n,k) read by rows: nextprime(k*n!)-k*n!. For 1<=k<=n.

Views

Author

Keywords

Comments

Examples

Programs

Mathematica

A180293 Number of arrangements of n indistinguishable balls in n boxes with the maximum number of balls in any box equal to n-3.

Views

Author

Keywords

Links

Crossrefs

Formula

A180292 Number of arrangements of n indistinguishable balls in n boxes with the maximum number of balls in any box equal to n-2.

Views

Author

Keywords

Links

Crossrefs

Formula

A180300 Number of arrangements of n indistinguishable balls in n boxes with the maximum number of balls in any box equal to n-10.

Views

Author

Keywords

Links

Crossrefs

Formula

A180294 Number of arrangements of n indistinguishable balls in n boxes with the maximum number of balls in any box equal to n-4.

Views

Author

Keywords

Links

Crossrefs

Formula

A180296 Number of arrangements of n indistinguishable balls in n boxes with the maximum number of balls in any box equal to n-6.

Views

Author

Keywords

Links

Crossrefs

Formula

A180295 Number of arrangements of n indistinguishable balls in n boxes with the maximum number of balls in any box equal to n-5.

Views

Author

Keywords

Links

Crossrefs

Formula

A180297 Number of arrangements of n indistinguishable balls in n boxes with the maximum number of balls in any box equal to n-7.

Views

Author

Keywords

Links

Crossrefs

Formula

A178916 Triangular array a(n,k) read by rows: nextprime(kn!)-kn!. For 1<=k<=n.