cp's OEIS Frontend

A186053 Smallest perimeter among all sets of nonnegative integers whose volume (sum) is n.

%I A186053 #72 Feb 28 2020 02:04:40
%S A186053 0,1,2,2,4,5,3,6,7,6,4,8,8,9,7,5,10,11,9,10,8,6,11,12,13,10,11,9,7,14,
%T A186053 12,13,14,11,12,10,8,16,16,13,14,15,12,13,11,9,16,17,17,14,15,16,13,
%U A186053 14,12,10,16,17,18,18,15,16,17,14,15,13,11,22,17,18,19,19,16,17
%N A186053 Smallest perimeter among all sets of nonnegative integers whose volume (sum) is n.
%C A186053 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.
%C A186053 For all partitions into distinct parts (with first part 0 implied), the perimeter of a set is the sum of parts p such that not both of p-1 and p+1 are in the partition.  The partition with smallest perimeter is sometimes, but not often unique. For example, there are three partitions of volume 37 achieving the minimal perimeter 16, namely [ 0 1 2 3 4 5 6 7 x 9 ], [ x 2 x 5 6 7 8 9 ], and [0 x 2 x 5 6 7 8 9 ] (where x is for one or more skipped parts), but there is only one partition of 36 with minimal perimeter 8, namely [ 0 1 2 3 4 5 6 7 8 ]. [_Joerg Arndt_, Jun 03 2013]
%H A186053 Joerg Arndt and Alois P. Heinz, <a href="/A186053/b186053.txt">Table of n, a(n) for n = 0..2000</a> (terms n = 0..201 from Joerg Arndt)
%H A186053 Patrick Devlin, <a href="http://arxiv.org/abs/1107.2954">Sets with High Volume and Low Perimeter</a>, arXiv:1107.2954 [math.CO], 2011.
%H A186053 Patrick Devlin, <a href="http://arxiv.org/abs/1202.1331">Integer Subsets with High Volume and Low Perimeter</a>, arXiv:1202.1331 [math.CO], 2012.
%H A186053 Patrick Devlin, <a href="http://www.emis.de/journals/INTEGERS/papers/m32/m32.Abstract.html">Integer Subsets with High Volume and Low Perimeter</a>, INTEGERS, Vol. 12, #A32.
%H A186053 J. Miller, F. Morgan, E. Newkirk, L. Pedersen and D. Seferis, <a href="http://www.jstor.org/stable/10.4169/math.mag.84.1.037">Isoperimetric Sets of Integers</a>, Math. Mag. 84 (2011) 37-42.
%F A186053 If t(n) is a triangular number t(n)=n*(n+1)/2, then a(t(n))=n.
%F A186053 a(n) = A002024(n) + A182298(A025581(n)) unless n is one of the 114 known counterexamples listed in A182246.  This allows the n-th term to be calculated in order log(log(n)) time using constant memory.  The first n terms can be calculated in order n time (using order n memory). [Result and details in above listed paper by _Patrick Devlin_ (2012).]
%e A186053 For n=8, the set S={0,1,2,5} has sum 8 and the perimeter 7 (the sum of 2 and 5).  No other set of volume 8 has a smaller perimeter, so a(8)=7.
%p A186053 b:= proc(n, i, t) option remember; `if`(n=0 and i<>0, `if`(t>1, i+1, 0),
%p A186053       `if`(i<0, infinity, min(`if`(t>1, i+1, 0)+b(n, i-1, iquo(t, 2)),
%p A186053       `if`(i>n, NULL, `if`(t=2, i+1, 0)+b(n-i, i-1, iquo(t, 2)+2)))))
%p A186053     end:
%p A186053 a:= n-> b(n$2, 0):
%p A186053 seq(a(n), n=0..100);  # _Alois P. Heinz_, Jul 23 2013
%t A186053 notBoth[lst_List] := Select[lst, !MemberQ[lst, #-1] || !MemberQ[lst, #+1]&]; Table[s=Select[IntegerPartitions[n], Length[#]==Length[Union[#]]&]; s=Append[#,0]&/@s; Min[Table[Plus@@notBoth[i], {i,s}]], {n,40}]
%t A186053 (* Second program: *)
%t A186053 b[n_, i_, t_] := b[n, i, t] = If[n == 0 && i != 0, If[t > 1, i+1, 0], If[ i<0, 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_, Aug 29 2016, after _Alois P. Heinz_ *)
%Y A186053 Cf. A227538.
%K A186053 nonn
%O A186053 0,3
%A A186053 _John W. Layman_, Feb 11 2011