Joshua Zucker - cp's OEIS frontend

A199769 Number of brackets in distinct sets with fewest possible elements.

1, 2, 3, 4, 4, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10

Offset: 1

Joshua Zucker, Nov 10 2011

nonn

			There are three repetitions of 5 because of the sets {{{{{}}}}}, {{{}, {{}}}}, and {{{{}}}, {}}.

Alois P. Heinz, Table of n, a(n) for n = 1..11306

Differences of A198759. Also n repeated A004111(n) times.

b:= proc(n) a(n):= `if`(n<2, n, add(a(n-k)*add(b(d)*d*
     (-1)^(k/d+1), d=numtheory[divisors](k)), k=1..n-1)/(n-1))
    end:
T:= n-> n$b(n):
seq(T(n), n=1..10);  # Alois P. Heinz, May 05 2023

a(n) = A198759(n+1) - A198759(n).

Second set in example corrected by Rick L. Shepherd, May 22 2013

A145500 a(n) = n! / A156832(n).

Original entry on oeis.org

1, 2, 6, 8, 5, 8, 7, 16, 36, 30, 66, 81, 78, 126, 84, 320, 272, 576, 1824, 2048, 640, 315, 322, 231, 525, 195, 648, 256, 261, 216, 217, 336, 330, 680, 2100, 3780, 1554, 7168, 4446, 1680, 15744, 7380, 560, 572, 1170, 3588, 14664, 5031, 5096, 3900

Offset: 1

Robert G. Wilson v and Joshua Zucker, Feb 16 2009

nonn

a(n) is the smallest integer such that 1/(n*b(n-1)) + 1/a(n) = 1/b(n), where b(n) = n!/A145499(n) takes only integer values and always divides n!. - Charlie Neder, Dec 02 2018

Charlie Neder, Table of n, a(n) for n = 1..1000
Charlie Neder, Python 3 program for computing this sequence and A145499

A152125 Consider a square grid with side n consisting of n^2 cells (or points); a(n) is the minimal number of points that can be painted black so that, out of any four points forming a square with sides parallel to the sides of the grid, at least one of the four is black.

Original entry on oeis.org

0, 1, 2, 4, 8, 12, 17, 23, 30, 39, 48, 59, 71

Offset: 1

Joshua Zucker, Mar 25 2009

On a 4 X 4 square grid, there are 14 lattice squares parallel to the axes. What is the fewest dots you can remove from the grid such that at least one vertex of each of the 14 squares is removed? The answer is a(4) = 4. In general a(n) is the answer for an n X n grid.
This is a "set covering problem", which can be handled by integer linear programming for small n. - Robert Israel, Mar 25 2009
This sequence is complementary to A227133: A227133(n) + a(n) = n^2.

			1 X 1: 0 dots, since there are already no squares,
2 X 2: 1 dot, any vertex will do,
3 X 3: 2 dots, the center kills all the small squares and you need one corner to kill the big square,
a(4) = 4: there are 4 disjoint squares, so it must be at least 4, and with a little more work you can find a set of 4 dots that work.
From _Robert Israel_: (Start)
For the 5 X 5 case, Maple confirms that the optimal solution is 8 dots,
which can be placed at
[1, 1], [1, 3], [2, 2], [2, 3], [3, 0], [3, 1], [3, 2], [4, 4]
For the 6 X 6 case, Maple tells me that the optimal solution is 12 dots,
which can be placed at
[0, 5], [1, 1], [1, 2], [1, 4], [2, 0], [2, 3], [2, 4], [3, 1], [3, 3],
[4, 0], [4, 4], [5, 2]
For the 7 X 7 case, Maple tells me that the optimal solution is 17 dots,
which can be placed at
[0, 0], [1, 2], [1, 3], [1, 5], [2, 1], [2, 4], [2, 5], [3, 2], [3, 3],
[3, 4], [4, 1], [4, 2], [4, 5], [5, 1], [5, 3], [5, 4], [6, 6]
For n=9, at least a(9) = 30 points (.) have to be removed while 51 (X) of 81 are remaining. The solution is unique (congruent images being ignored).
      . X X X X X . X .
      X . X . . X X X X
      X X . . X . X . X
      X . . X X X X . .
      X X X . X . . X X
      X . X X X . . . X
      . X X . . X X . X
      X X . X . X . X X
      . X X X X X X X .
(End)

Ed Wynn, A comparison of encodings for cardinality constraints in a SAT solver, arXiv:1810.12975 [cs.LO], 2018.

See A227133 for an equivalent version of this problem.
A227116 treats an analogous question but for equilateral triangles instead of squares.
A000330 gives the number of subsquares in a square grid of side n.
Cf. also A240443.

a(5)-a(7) from Robert Israel, Mar 25 2009
a(8)-a(9) from Heinrich Ludwig, Jul 01 2013
a(10) from Giovanni Resta, Jul 14 2013 (see A152125).
Reworded definition to align this with several similar sequences (A227133, A240443, A227116, etc.). - N. J. A. Sloane, Apr 19 2016
a(11)-a(13) (using A227133) from Alois P. Heinz, May 05 2023

A137295 P-positions in sparse Atomic Wari, octal game .37.

Original entry on oeis.org

0, 3, 11, 19, 29, 45, 71, 97, 123, 149, 175, 313, 407

Offset: 1

Joshua Zucker, Mar 15 2008

The sequence is only conjectured to be finite as of the publication in 1996, but there are definitely no more terms under 200000, so the conjecture seems extremely likely to be true.

			A player can remove one seed from any pile, or remove two seeds from any pile and optionally split the remainder into two piles.
A pile of 3 is a P-position because whether the player to move takes 1 or 2, the next player takes 2 or 1 and wins.

J. Erickson, "Sowing Games", in Nowakowski (ed), Games of No Chance, 1996, p. 295.

J. Erickson, Sowing Games article from Games of No Chance.

A137294 A polynomial-time algorithm for moving all seeds into one pot in a class of sowing positions.

Original entry on oeis.org

0, 1, 3, 4, 7, 10, 12, 13, 17, 22, 26, 31, 34, 37, 39, 40, 45, 52, 58, 67, 72, 79, 85, 94, 98, 103, 107, 112, 115, 118, 120, 121, 127, 136, 144, 157, 164, 175, 185, 202, 208, 217, 225, 238, 245, 256, 266, 283, 288, 295, 301, 310, 315, 322, 328, 337, 341, 346, 350

Offset: 1

Joshua Zucker, Mar 15 2008

a(n) is asymptotic to O(n^(log base 2 of 3)) according to the reference.
The reference also gives a(2^k) = 1/2 (3^k - 1).
Numerical experiments indicate that a(n) ~ 0.5 or 0.6 * n^(log base 2 of 3). The coefficient seems to oscillate back and forth between 0.5 and 0.6.
The reference also points out that it is possible, by choosing a less efficient recursive algorithm for getting all the seeds in one pot, to simulate the Towers of Hanoi algorithm and obtain 2^(n-1) - 1 moves for a(n) instead.

			Starting with 1 all the seeds are already in one pot so a(1) = 0 moves.
Starting with 11, move to 2, so a(2) = 1.
Starting with 111, move to 201 and then 012 and then 003, so a(3) = 3 moves.
Starting with 1111, move to 0211, 0202, 0013, 0004, so a(4) = 4 moves.
Starting with 11111, move to 02111, 02102, 03002, 00113, 00203, 00014, 00005, a(5) = 7 moves.

J. Erickson, "Sowing Games", in Nowakowski (ed), Games of No Chance, 1996. P. 289 is the most relevant page.

Joshua Zucker, Table of n, a(n) for n = 1..1000
J. Erickson, Sowing Games article from Games of No Chance.

Cf. A000225 is the Towers of Hanoi sequence. A003462 has a(2^n).

T(1) = 0; T(2m) = 3T(m) + 1; T(2m+1) = 2T(m) + T(m+1) + 2 (from p. 289 of Erickson in Nowakowski reference above).

A137201 "Ungodly" numbers: numbers that, in some base b > 6, contain the string 666 at least once in their expansion.

Original entry on oeis.org

342, 438, 546, 666, 685, 798, 942, 950, 1028, 1098, 1266, 1275, 1371, 1446, 1462, 1638, 1666, 1714, 1842, 1974, 2004, 2057, 2058, 2129, 2286, 2394, 2395, 2396, 2397, 2398, 2399, 2400, 2486, 2526, 2666, 2670, 2733, 2743, 2778, 2998, 3042, 3086, 3295

Offset: 1

Joshua Zucker, Mar 04 2008

Max Alekseyev asked if there are an infinite number of godly numbers.

			342 is in the sequence because 342 = 666_7.
685 is in the sequence because 685 = 1666_7.
99968 is in the sequence because 99968 = 3666B_13.

Joshua Zucker, Mar 04 2008, Table of n, a(n) for n = 1..2938

Cf. A121205 (numbers that in some base b are represented exactly as 666, so it is a subsequence of this sequence).

A135417 Number of mountain numbers (see A134941) with n digits.

Original entry on oeis.org

1, 0, 8, 56, 252, 784, 1792, 3108, 4166, 4352, 3544, 2232, 1068, 376, 92, 14, 1

Offset: 1

Suggested by Jonathan Vos Post, Nov 24 2007 and computed by Hans Havermann and Joshua Zucker, Nov 25 2007

The total number is 21846.

			Contribution from _Reinhard Zumkeller_, May 25 2010: (Start)
a(1) = A178334(9) = 1;
a(2) = A178334(99) - A178334(9) = 1 - 1 = 0;
a(3) = A178334(999) - A178334(99) = 9 - 1 = 8;
a(4) = A178334(9999) - A178334(999) = 65 - 9 = 56. (End)

A125764 Array of partial sums of rows of array in A086271, read by antidiagonals.

Original entry on oeis.org

1, 3, 2, 6, 7, 3, 10, 15, 12, 4, 15, 26, 27, 18, 5, 21, 40, 48, 42, 25, 6, 28, 57, 75, 76, 60, 33, 7, 36, 77, 108, 120, 110, 81, 42, 8, 45, 100, 147, 174, 175, 150, 105, 52, 9, 55, 126, 192, 238, 255, 240, 196, 132, 63, 10, 66, 155, 243, 312, 350, 351, 315, 248, 162, 75, 11

Offset: 1

Jonathan Vos Post and Joshua Zucker, Feb 03 2007

Row 3 is = 3rd triangular number + 3rd square + 3rd pentagonal number + 3rd hexagonal number + ... + 3rd k-gonal number. First column is triangular numbers. A086271 Rectangular array T(n,k) of polygonal numbers, by diagonals.

			Partial row sum array begins:
1 | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ... n.
2 | 3, 7, 12, 18, 25, 33, 42, 52, (n(n+1)/2)-3.
3 | 6, 15, 27, 42, 60, 81, 105, ... (3/2)n^2 + (9/2) n.
4 | 10, 26, 48, 76, 110, 150, ... 3n^2 + 7n.
5 | 15, 40, 75, ... 5n^2 + 10n.
6 | 21, 57, 108, ... (15/2)n^2 + (27/2)n.

Eric Weisstein's World of Mathematics, Polygonal Number. See equation (4), our partial sums are on this as array element values.

Cf. A000096, A000217, A000290, A000326, A000384, A086270, A086271, A086272, A086273.

A086271 := proc(n,k) k*binomial(n,2)+n ; end: A125764 := proc(n,k) add(A086271(n,i),i=1..k) ; end: for d from 1 to 15 do for k from 1 to d do printf("%d, ",A125764(d-k+1,k)) ; od: od: # R. J. Mathar, Nov 02 2007

a(k,n) = (k*(k-1)/2)n^2 + (k*(k+3)/4)n. a(k,n) = row k of array of partial sums = k-th triangular number + k-th square + k-th pentagonal number + k-th hexagonal number + ... = A000217(k) + A000290(k) + A000326(k) + A000384(k) + ... a(1,n) = n. a(2,n) = (n(n+1)/2)-3 = A000217(n) - 3. a(3,n) = 3*n(n+3)/2 = A000096 with offset 3.

More terms from R. J. Mathar, Nov 02 2007

Keyword tabl added by Michel Marcus, Apr 08 2013

A125845 n-digit numbers having n divisors each with a different number of digits.

Original entry on oeis.org

1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 121, 169, 289, 361, 529, 841, 961, 1111, 1133, 1177, 1199, 1243, 1313, 1331, 1339, 1391, 1397, 1417, 1441, 1469, 1507, 1529, 1639, 1651, 1661, 1703, 1717, 1727, 1751, 1781

Offset: 1

Joshua Zucker, Dec 11 2006

A subsequence of A095862.

			1 is the only one-digit number with only one factor. Two-digit primes are the only two-digit numbers in the list since they have a one-digit factor (1) and a two-digit factor (themselves). Three-digit squares of two-digit primes are the only three-digit numbers in the list, since only numbers of the form p^2 can have three factors.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Sam Vandervelde, The Mandelbrot Competition, round 2, 2006-07, asked for the smallest composite number in this list.

A125315 gives the smallest n-digit number of this form for each n.

A124479 From the game of Quod: number of "squares" on an n X n array of points with the four corner points deleted.

Original entry on oeis.org

0, 1, 11, 37, 88, 175, 311, 511, 792, 1173, 1675, 2321, 3136, 4147, 5383, 6875, 8656, 10761, 13227, 16093, 19400, 23191, 27511, 32407, 37928, 44125, 51051, 58761, 67312, 76763, 87175, 98611, 111136, 124817, 139723, 155925, 173496, 192511, 213047, 235183, 259000

Offset: 2

Joshua Zucker, Dec 18 2006

We count all squares whose vertices are among the points; the sides of the squares need not be horizontal or vertical.

			So for n=3 we have 5 points:
.....O
....OOO
.....O
The only square is formed by the 4 outer points, agreeing with a(3)=1.
For n=4 we have 12 points:
.....OO
....OOOO
....OOOO
.....OO
There are 5 unit squares, 4 tilted ones with sides sqrt(2) and 2 tilted ones with sides sqrt(5), agreeing with a(4)=11.

Ian Stewart, How To Cut A Cake: and Other Mathematical Conundrums, Chap. 7.

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

Drop[CoefficientList[Series[x^3(1+6x-8x^2+3x^3)/(1-x)^5,{x,0,50}],x],2] (* or *) LinearRecurrence[{5,-10,10,-5,1},{0,1,11,37,88},50] (* Harvey P. Dale, Apr 16 2022 *)

a(n) = (n^4 - n^2 - 48*n + 84)/12.

G.f.: x^3*(1+6*x-8*x^2+3*x^3)/(1-x)^5. [Colin Barker, May 21 2012]

Additional comments from Dean Hickerson, Dec 18 2006

cp's OEIS Frontend

User: Joshua Zucker

A199769 Number of brackets in distinct sets with fewest possible elements.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

Extensions

A145500 a(n) = n! / A156832(n).

Views

Author

Keywords

Comments

Links

A152125 Consider a square grid with side n consisting of n^2 cells (or points); a(n) is the minimal number of points that can be painted black so that, out of any four points forming a square with sides parallel to the sides of the grid, at least one of the four is black.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A137295 P-positions in sparse Atomic Wari, octal game .37.

Views

Author

Keywords

Comments

Examples

References

Links

A137294 A polynomial-time algorithm for moving all seeds into one pot in a class of sowing positions.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A137201 "Ungodly" numbers: numbers that, in some base b > 6, contain the string 666 at least once in their expansion.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A135417 Number of mountain numbers (see A134941) with n digits.

Views

Author

Keywords

Comments

Examples

A125764 Array of partial sums of rows of array in A086271, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

Extensions

A125845 n-digit numbers having n divisors each with a different number of digits.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs