A347581 The Barnyard sequence: a(n) is the minimum number of unit length line segments required to enclose areas of 1 through n on a square grid.

4, 9, 14, 20, 26, 33, 40, 47, 55, 63

Offset: 1

Author

Scott R. Shannon, Oct 05 2021

Keywords

• nonn
• more

Comments

The areas of size 1 through n can be created in any order and position, the only requirement being the final number of line segments used to enclose all areas is minimized. It is likely the perimeter of each area of size k, 1 <= k <= n, is the minimum possible for an area of size k, although this is unknown.

See A348149 for the total segments when the number of segments at each step is minimized.

Examples

			Example areas using the minimum number of line segments from n = 1 through n = 10 are:
.
   __
  |__|  a(1) = 4
   __ __ __
  |__|__ __|  a(2) = 9
   __ __ __
  |__|__ __|  a(3) = 14
  |__ __ __|
   __ __ __
  |__|__ __|
  |__ __ __|  a(4) = 20
  |     |
  |__ __|
   __ __ __
  |__|__ __|__
  |__ __ __|  |  a(5) = 26
  |     |     |
  |__ __|__ __|
   __ __ __
  |__|__ __|__ __ __
  |__ __ __|  |     |  a(6) = 33
  |     |     |     |
  |__ __|__ __|__ __|
         __ __ __ __
   __ __|__         |
  |__|__ __|__ __ __|
  |__ __ __|  |     |  a(7) = 40
  |     |     |     |
  |__ __|__ __|__ __|
   __ __ __ __ __ __
  |           |     |
  |__ __ __ __|     |
  |        |__ __ __|   a(8) = 47
  |__ __ __|__      |
  |     |  |  |__ __|
  |__ __|__|__ __|__|
   __ __ __ __ __ __ __
  |        |           |
  |        |__ __ __ __|
  |__ __ __|__         |
     |__|__ __|__ __ __|  a(9) = 55
     |__ __ __|  |     |
     |     |     |     |
     |__ __|__ __|__ __|
   __ __ __ __ __ __ __ __
  |         __|__   |     |
  |__ __ __|     |__|__   |
  |        |     |     |__|
  |        |     |     |  |   a(10) = 63
  |__ __ __|__ __|__ __|__|
  |              |     |__|
  |__ __ __ __ __|__ __|
.
		

Links

• Sascha Kurz, Counting polyominoes with minimum perimeter, arXiv:math/0506428 [math.CO], 2015.

Crossrefs

Cf. A348149, A001168, A291808, A291809, A328020, A291806, A172477, A006983.