login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A186053 Smallest perimeter among all sets of nonnegative integers whose volume (sum) is n. 8
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, 12, 13, 14, 11, 12, 10, 8, 16, 16, 13, 14, 15, 12, 13, 11, 9, 16, 17, 17, 14, 15, 16, 13, 14, 12, 10, 16, 17, 18, 18, 15, 16, 17, 14, 15, 13, 11, 22, 17, 18, 19, 19, 16, 17 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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.

If t(n) is a triangular number t(n)=n*(n+1)/2, then a(t(n))=n.

Devlin: "We consider a certain variation of the 'isoperimetric problem' adopted for subsets of nonnegative integers. More specifically, we explore the sequence P(n) as described in OEIS A186053. We provide the first exact formulas for P(n) including multiple recursive relations involving auxiliary functions as well as concise and satisfying representations and quasi-explicit formulas. We also discuss some of the intricate fractal-like symmetry of the sequence as well as the development of algorithms for computing P(n). We conclude with open questions for further research." [Jonathan Vos Post, Jul 17 2011].

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]

LINKS

Joerg Arndt and Alois P. Heinz, Table of n, a(n) for n = 0..2000 (terms n = 0..201 from Joerg Arndt)

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.

FORMULA

a(n) = A002024(n) + A182298(A025581(n)) unless n is one of the 114 known counter-examples 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).]

EXAMPLE

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.

MAPLE

b:= proc(n, i, t) option remember; `if`(n=0 and i<>0, `if`(t>1, i+1, 0),

      `if`(i<0, 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);  # Alois P. Heinz, Jul 23 2013

MATHEMATICA

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}]

(* Second program: *)

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 *)

CROSSREFS

Cf. A227538.

Sequence in context: A119989 A137605 A242348 * A133082 A130265 A187214

Adjacent sequences:  A186050 A186051 A186052 * A186054 A186055 A186056

KEYWORD

nonn

AUTHOR

John W. Layman, Feb 11 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 18 17:56 EST 2017. Contains 294894 sequences.