A186053 -id:A186053 - cp's OEIS frontend

A182298 Smallest complementary perimeter, as defined in the comments, among all sets of nonnegative integers whose volume (sum) is n.

0, 2, 4, 3, 6, 5, 4, 7, 7, 6, 5, 10, 8, 8, 7, 6, 12, 11, 9, 9, 8, 7, 11, 13, 12, 10, 10, 9, 8, 15, 12, 14, 13, 11, 11, 10, 9, 17, 16, 13, 15, 14, 12, 12, 11, 10, 17, 18, 17, 14, 16, 15, 13, 13, 12, 11, 16, 18, 19, 18, 15, 17, 16, 14, 14, 13, 12, 21, 17, 19, 20

Offset: 0

Patrick Devlin, Apr 23 2012

nonn

The volume and perimeter of a set S of nonnegative integers are introduced in the reference. The volume is defined simply as the sum of the elements of S, and the perimeter is defined as the sum of the elements of S whose predecessor and successor are not both in S. The complementary perimeter (introduced in the link) of S is the perimeter of the complement of S in the set of nonnegative integers.

			For n=8, the set S={0,1,3,4} has volume (total sum) 8 and complementary perimeter (the sum of 2 and 5) is 7.  No other set of volume 8 has a smaller complementary perimeter, so a(8)=7.
Similarly, for n=11, the set S={2,4,5} has volume 11=2+4+5 and complementary perimeter 10=1+3+6.  This is the smallest among all sets with volume 11, so a(11)=10.

Martin Ehrenstein, Table of n, a(n) for n = 0..250
Patrick Devlin, Sets with High Volume and Low Perimeter, arXiv:1107.2954 [math.CO], 2011.
Patrick Devlin, Integer Subsets with High Volume and Low Perimeter, arXiv:1202.1331 [math.CO], 2012.
Patrick Devlin, Integer Subsets with High Volume and Low Perimeter, INTEGERS, Vol. 12, #A32.
J. Miller, F. Morgan, E. Newkirk, L. Pedersen and D. Seferis, Isoperimetric Sets of Integers, Math. Mag. 84 (2011) 37-42.

Cf. A186053.

Following the notation in the link, for n >= 0, write n = (0+1+2+...+f(n)) - g(n), be the representation of n with f(n) and g(n) minimal such that 0 <= g(n) <= f(n). Then f(n) = A002024(n) = round(sqrt(2n)), and g(n) = A025581(n) = f(n)*(f(n)+1)/2 - n.

Finally, let Q(n):=a(n), and let P(n):=A186053(n). Then unless n is one of the 177 known counterexamples tabulated in the link, we have P(n) = f(n) + Q(g(n)), and Q(n) = 1 + f(n) + P(g(n)).

More terms from Martin Ehrenstein, Nov 16 2023

A182372 Number of distinct sets of nonnegative integers with perimeter n, as defined in the comments.

Original entry on oeis.org

2, 2, 3, 4, 6, 8, 11, 14, 19, 24, 31, 39, 50, 61, 77, 94, 117, 141, 173, 208, 253, 302, 363, 431, 516, 609, 723, 850, 1003, 1174, 1379, 1607, 1878, 2181, 2537, 2936, 3404, 3925, 4532, 5212, 5998, 6877, 7890, 9021, 10320, 11771, 13427, 15277, 17385, 19734, 22401, 25375, 28739, 32485

Offset: 0

John W. Layman, Apr 26 2012

nonn

The volume and perimeter of a set S of nonnegative integers are introduced in the reference. The volume is defined simply as the sum of the elements of S, and the perimeter is defined as the sum of the elements of S whose predecessor and successor are not both in S.
Conjecture: number of partitions of n into two sorts of parts such that no two successive parts are the same sort (as the order of sorts in a run of identical parts is immaterial, there can be at most two parts of same size), see example. - Joerg Arndt, Jun 01 2013
The conjecture of Arndt [namely that a(n) = A227134(n) + A227135(n)] has been verified for n < 1200. - Patrick Devlin, Jul 02 2013
a(n) is also the number of ways to write n as the sum of nonnegative integers, t_1 < t_2 < ... < t_k, such that (i) each such integer is labeled "E" or "F", (ii) t_1 is labeled "E", (iii) if t_j - t_{j-1} = 1, then t_j is labeled "F", and (iv) the label "F" does not appear twice in a row. (This includes the empty sum for the case n=0.) See examples. - Patrick Devlin, Jul 03 2013

			G.f.: 2 + 2*x + 3*x^2 + 4*x^3 + 6*x^4 + 8*x^5 + 11*x^6 + 14*x^7 + 19*x^8 + ...
G.f.: 2/(1-x) + x^2*(1+x)/((1-x)*(1-x^2)) + x^4*(1+x)/((1-x)*(1-x^2)*(1-x^3)) + x^6*(1+x^2)/((1-x)*(1-x^2)*(1-x^3)*(1-x^4)) + x^9*(1+x^2)/((1-x)*(1-x^2)*(1-x^3)*(1-x^4)*(1-x^5)) + x^12*(1+x^3)/((1-x)*(1-x^2)*(1-x^3)*(1-x^4)*(1-x^5)*(1-x^6)) + ... - _Paul D. Hanna_, Jul 06 2013
From _Joerg Arndt_, Jun 01 2013: (Start)
##:   set     perimeter  sum(perimeter)
00:  .......  .......     0 (empty set)
01:  ......1  ......1     0
02:  .....1.  .....1.     1
03:  .....11  .....11     1
04:  ....1..  ....1..     2
05:  ....1.1  ....1.1     2
06:  ....11.  ....11.     3
07:  ....111  ....1.1     2
08:  ...1...  ...1...     3
09:  ...1..1  ...1..1     3
10:  ...1.1.  ...1.1.     4
11:  ...1.11  ...1.11     4
12:  ...11..  ...11..     5
13:  ...11.1  ...11.1     5
14:  ...111.  ...1.1.     4
15:  ...1111  ...1..1     3
16:  ..1....  ..1....     4
17:  ..1...1  ..1...1     4
18:  ..1..1.  ..1..1.     5
19:  ..1..11  ..1..11     5
20:  ..1.1..  ..1.1..     6
21:  ..1.1.1  ..1.1.1     6
22:  ..1.11.  ..1.11.     7
23:  ..1.111  ..1.1.1     6
24:  ..11...  ..11...     7
25:  ..11..1  ..11..1     7
26:  ..11.1.  ..11.1.     8
27:  ..11.11  ..11.11     8
28:  ..111..  ..1.1..     6
29:  ..111.1  ..1.1.1     6
30:  ..1111.  ..1..1.     5
31:  ..11111  ..1...1     4
The last set contribution to a(n) n has index 2^(n+1)-1, so the statistics is complete up to 4.
We find a(1)=2, a(1)=2, a(2)=2, and a(4)=6.
(End)
The six sets {4}, {0,4}, {1,3}, {0,1,3}, {1,2,3}, and {0,1,2,3,4}, and no others, have perimeter 4, so a(4)=6.
From _Joerg Arndt_, Jun 01 2013: (Start)
There are a(9) = 24 partitions of 9 into two sorts of parts such that no two successive parts are of same sort (format "P:S" for "part:sort"):
01:  [ 1:0  1:1  2:0  2:1  3:0  ]
02:  [ 1:0  1:1  2:0  5:1  ]
03:  [ 1:0  1:1  3:0  4:1  ]
04:  [ 1:0  1:1  7:0  ]
05:  [ 1:0  2:1  3:0  3:1  ]
06:  [ 1:0  2:1  6:0  ]
07:  [ 1:0  3:1  5:0  ]
08:  [ 1:0  8:1  ]
09:  [ 2:0  2:1  5:0  ]
10:  [ 2:0  3:1  4:0  ]
11:  [ 2:0  7:1  ]
12:  [ 3:0  6:1  ]
13:  [ 4:0  5:1  ]
14:  [ 9:0  ]
15:  [ 1:1  2:0  2:1  4:0  ]
16:  [ 1:1  2:0  6:1  ]
17:  [ 1:1  3:0  5:1  ]
18:  [ 1:1  4:0  4:1  ]
19:  [ 1:1  8:0  ]
20:  [ 2:1  3:0  4:1  ]
21:  [ 2:1  7:0  ]
22:  [ 3:1  6:0  ]
23:  [ 4:1  5:0  ]
24:  [ 9:1  ]
There are A227134(9)=14 and A227135(9)= 10 such partitions where the first part is respectively of sort 0 and 1.
The corresponding sets and perimeters are (format as in first example)
0042:  .....1.1.1.  .....1.1.1.   9
0043:  .....1.1.11  .....1.1.11   9
0046:  .....1.111.  .....1.1.1.   9
0048:  .....11....  .....11....   9
0049:  .....11...1  .....11...1   9
0058:  .....111.1.  .....1.1.1.   9
0059:  .....111.11  .....1.1.11   9
0070:  ....1...11.  ....1...11.   9
0072:  ....1..1...  ....1..1...   9
0073:  ....1..1..1  ....1..1..1   9
0079:  ....1..1111  ....1..1..1   9
0120:  ....1111...  ....1..1...   9
0121:  ....1111..1  ....1..1..1   9
0132:  ...1....1..  ...1....1..   9
0133:  ...1....1.1  ...1....1.1   9
0135:  ...1....111  ...1....1.1   9
0252:  ...111111..  ...1....1..   9
0253:  ...111111.1  ...1....1.1   9
0258:  ..1......1.  ..1......1.   9
0259:  ..1......11  ..1......11   9
0510:  ..11111111.  ..1......1.   9
0512:  .1.........  .1.........   9
0513:  .1........1  .1........1   9
1023:  .1111111111  .1........1   9
(End)
From _Patrick Devlin_, Jul 03 2013: (Start)
The six sets {4}, {0,4}, {1,3}, {0,1,3}, {1,2,3}, and {0,1,2,3,4}, and no others, have perimeter 4, so a(4)=6.  These sets correspond to the labeled partitions (allowing 0 as a part)  [4E], [0E, 4E], [1E, 3E], [0E, 1F, 3E], [1E, 3F], and [0E, 4F] (respectively).
To explain this bijection further, the partition itself (e.g., 32 = 0 + 2 + 4 + 5 + 9 + 12) corresponds to which integers of the set will contribute to the perimeter.  Thus, this unlabeled partition of 32 corresponds to the family of sets of the form {0, ??, 2, ??, 4, 5, ??, 9, ??, 12}.  Then we only need to decide for each gap (here represented as ??) whether or not to fill it in ("F") with the corresponding string of consecutive integers or to leave it empty ("E").  This decision making process is equivalent to labeling each integer immediately following a gap with "F" or "E" (to denote if the gap is filled or empty) subject to the four 'rules' above [Rules (ii) and (iii) force the appropriate labelings for places where there are no gap (in this example, before 0 and before 5).  And rule (iv) ensures that consecutive gaps are not both filled (in order to preserve the 'boundary' of the set).].
In the unlabeled example 32 = 0 + 2 + 4 + 5 + 9 + 12, as we begin to label, rules (ii) and (iii) force us to have [0E, 2?, 4?, 5F, 9?, 12?].  Then since we may not have two consecutive labels of "F", we are forced to have [0E, 2?, 4E, 5F, 9E, 12?].  We can then label 2 as either "F" or "E" (which determines whether or not 1 is in the set), and we can independently label 12 as "F" or "E" (which determines whether or not {10, 11} is in the set).  For instance, the labeling [0E, 2E, 4E, 5F, 9E, 12F] corresponds to the set {0, 2, 4, 5, 9, 10, 11, 12}, which has perimeter 32.
Given an unlabeled partition, after the partially labeling that's forced to satisfy rules (ii), (iii), and (iv), then the number of ways to extend this partial labeling to a valid labeling is related to the Fibonacci numbers (in a clear but perhaps useless way).
Noting that a(n) is the same as counting these 'labeled partitions' (allowing 0 as a part) may help prove the conjecture of Arndt [namely that a(n) = A227134(n) + A227135(n)].
(End)

Joerg Arndt, Table of n, a(n) for n = 0..200
Patrick Devlin, Integer Subsets with High Volume and Low Perimeter, arXiv:1202.1331 [math.CO], 2012.
J. Miller, F. Morgan, E. Newkirk, L. Pedersen and D. Seferis, Isoperimetric Sets of Integers, Math. Mag. 84 (2011) 37-42.

Cf. A186053, A182298.

Cf. A227134 (corresponding partitions, first sort = 0), A227135 (first sort = 1).

a(n):=proc(n) # This computes a(n) in order n^3 time and order n^2 memory
     return givenMax(n, n);
end proc:
## This helper function finds the number of sets with perimeter n
## and maximum element AT MOST m
givenMax:=proc(n, m) option remember:
  # Begin base cases
  if((n=0) and (m < 0)) then return 1: fi:
  if((n=0) and (m >=0)) then return 2: fi:
  if((n<0)) then return 0: fi:
  if((n>0) and (m < 1)) then return 0: fi:
  # End base cases
  # Conditions based on the largest element
  # of {-1, 0, 1, 2, ..., m} NOT in the sets of interest
  return   givenMax(n, m-1)  + givenMax(n-m, m-2) + add(givenMax(n-m-(m-k), m-k-2), k=1..m);
end proc:
# Patrick Devlin, Jul 02 2013

a[n_] := givenMax[n, n];
givenMax[n_, m_] := givenMax[n, m] = Which[n == 0 && m < 0, 1, n == 0 && m >= 0, 2, n < 0, 0, n > 0 && m < 1, 0, True, givenMax[n, m - 1]  + givenMax[n-m, m-2] + Sum[givenMax[n - m - (m-k), m - k - 2], {k, 1, m}]];
Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Dec 14 2017, after Patrick Devlin *)

{A002620(n)=floor(n/2)*ceil(n/2)}
{a(n)=polcoeff(2/(1-x+x*O(x^n)) + sum(m=2,sqrtint(4*n)+1, x^A002620(m+1)*(1+x^(m\2))/prod(k=1,m,1-x^k+x*O(x^n))),n)}
for(n=0,60,print1(a(n),", ")) \\ Paul D. Hanna, Jul 06 2013

G.f.: 2/(1-x) + Sum_{n>=2} x^A002620(n+2)*(1 + x^[n/2]) / Product_{k=1..n} (1-x^k), where A002620(n) = floor(n/2)*ceiling(n/2) forms the quarter-squares. - Paul D. Hanna, Jul 06 2013

Prepended a(0) and added more terms, Joerg Arndt, Jun 01 2013

Changed a(0) = 2, allowing the empty set, Patrick Devlin, Jul 02 2013

A227538 Smallest k such that a partition of n into distinct parts with perimeter k exists.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 4, 7, 8, 6, 5, 9, 8, 9, 7, 6, 11, 12, 9, 10, 8, 7, 11, 12, 13, 10, 11, 9, 8, 15, 12, 13, 14, 11, 12, 10, 9, 16, 17, 13, 14, 15, 12, 13, 11, 10, 16, 17, 18, 14, 15, 16, 13, 14, 12, 11, 16, 17, 18, 19, 15, 16, 17, 14, 15, 13, 12, 22, 17, 18, 19

Offset: 0

Alois P. Heinz, Jul 16 2013

The perimeter is the sum of all parts having less than two neighbors.

a(n) is also the smallest perimeter among all sets of positive integers whose volume (sum) is n. - Patrick Devlin, Jul 23 2013

			a(0) = 0: the empty partition [] has perimeter 0.
a(1) = 1: [1] has perimeter 1.
a(3) = 3: [1,2], [3] have perimeter 3.
a(6) = 4: [1,2,3] has perimeter 4.
a(7) = 7: [1,2,4], [3,4], [2,5], [1,6], [7] have perimeter 7; no partition of 7 into distinct parts has a smaller perimeter.
a(10) = 5: [1,2,3,4] has perimeter 5.
a(15) = 6: [1,2,3,4,5] has perimeter 6.
a(29) = 15: [1,2,3,4,5,6,8] has perimeter 1+6+8 = 15.
a(30) = 12: [4,5,6,7,8] has perimeter 12.

Alois P. Heinz, Table of n, a(n) for n = 0..5000

Cf. A227344, A186053 (smallest perimeter among all sets of nonnegative integers).

b:= proc(n, i, t) option remember; `if`(n=0, `if`(t>1, i+1, 0),
      `if`(i<1, infinity, min(`if`(t>1, i+1, 0)+b(n, i-1, iquo(t, 2)),
      `if`(i>n, NULL, `if`(t=2, i+1, 0)+b(n-i, i-1, iquo(t, 2)+2)))))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..100);

b[n_, i_, t_] := b[n, i, t] = If[n==0, If[t>1, i+1, 0], If[i<1, Infinity, Min[If[t>1, i+1, 0] + b[n, i-1, Quotient[t, 2]], If[i>n, Infinity, If[t == 2, i+1, 0] + b[n-i, i-1, Quotient[t, 2]+2]]]]]; a[n_] := b[n, n, 0]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Feb 15 2017, translated from Maple *)

a(n) = min { k : A227344(n,k) > 0 }.

a(A000217(n)) = n+1 for n>1.

A182321 Number of iterations of A025581(n) required to reach 0.

Original entry on oeis.org

0, 1, 2, 1, 3, 2, 1, 2, 3, 2, 1, 4, 2, 3, 2, 1, 3, 4, 2, 3, 2, 1, 2, 3, 4, 2, 3, 2, 1, 3, 2, 3, 4, 2, 3, 2, 1, 4, 3, 2, 3, 4, 2, 3, 2, 1, 3, 4, 3, 2, 3, 4, 2, 3, 2, 1, 2, 3, 4, 3, 2, 3, 4, 2, 3, 2, 1

Offset: 0

Patrick Devlin, Apr 24 2012

nonn

Following the notation in the link, for n >= 0, let n = (0 + 1 + 2 + ... + f(n)) - g(n) be the representation of n with f(n) and g(n) minimal such that 0 <= g(n) <= f(n).  Then f(n) = A002024(n) = round(sqrt(2n)), and g(n) = A025581(n) = f(n)*(f(n)+1)/2 - n.
With this notation, a(n) is the number of iterations of g(n) needed to reach 0.
The sequence a(n) is essentially the function phi(n) of the link.
The sequence a(n) has a high degree of fractal-like symmetry.  Consider, for instance, the sequence in the triangular array (read left to right then top to bottom, with the term for a(0) on top):
           0
           1
        2  1
     3  2  1
  2  3  2  1
Then the rows of this triangle (read from right to left) are simply 1+a(n).
a(n) is related to the recurrence between A186053 and A182298.
For n >= 1, a(n) is the number of terms in the minimal alternating triangular-number representation of n+1, defined at A255974. - Clark Kimberling, Apr 10 2015

			g(8) = 2, g(2) = 1, g(1) = 0.  Therefore a(8) = 3.

Clark Kimberling, Table of n, a(n) for n = 0..1000
Patrick Devlin, Integer Subsets with High Volume and Low Perimeter, arXiv:1202.1331v1 [math.CO]

Cf. A025581, A002024, A255974.

# With this code, the n-th term of the sequence is given by a call to a(n)
f:=n->round(sqrt(2*n)): g:=n->f(n)*(f(n)+1)/2-n:
a:=proc(n) option remember:
  if n < 1 then return 0: fi: return 1 + a(g(n)):
end proc:

(* This program computes the sequence as the number of terms in the minimal alternative triangular-number representation of n+1. *)
b[n_] := n (n + 1)/2; bb = Table[b[n], {n, 0, 1000}];
s[n_] := Table[b[n], {k, 1, n}];
h[1] = {1}; h[n_] := Join[h[n - 1], s[n]]; g = h[100]; r[0] = {0};
r[n_] := If[MemberQ[bb, n], {n}, Join[{g[[n]]}, -r[g[[n]] - n]]];
Join[{0}, Rest[Table[Length[r[n]], {n, 0, 100}]]] (* A182321 for n >= 1 *)
(* Clark Kimberling, Apr 10 2015 *)

The Devlin link shows a(n) < log_2(log_2(n/2)) + 2.

cp's OEIS Frontend

A182245 Integers n such that either (a) A186053(n) does not equal A002024(n) + A182298(A025581(n)) or (b) A182298(n) does not equal 1 + A002024(n) + A186053(A025581(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A182246 Integers n such that A186053(n) does not equal A002024(n) + A182298(A025581(n)).

Views

Author

Keywords

Comments

Links

A182266 Integers n such that A182298(n) does not equal 1 + A002024(n) + A186053(A025581(n)).

Views

Author

Keywords

Comments

Links

A182298 Smallest complementary perimeter, as defined in the comments, among all sets of nonnegative integers whose volume (sum) is n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A182372 Number of distinct sets of nonnegative integers with perimeter n, as defined in the comments.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A227538 Smallest k such that a partition of n into distinct parts with perimeter k exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A182321 Number of iterations of A025581(n) required to reach 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula