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

%I #38 Feb 15 2017 09:26:59

%S 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,

%T 12,13,14,11,12,10,9,16,17,13,14,15,12,13,11,10,16,17,18,14,15,16,13,

%U 14,12,11,16,17,18,19,15,16,17,14,15,13,12,22,17,18,19

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

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

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

%H Alois P. Heinz, <a href="/A227538/b227538.txt">Table of n, a(n) for n = 0..5000</a>

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

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

%e a(0) = 0: the empty partition [] has perimeter 0.

%e a(1) = 1: [1] has perimeter 1.

%e a(3) = 3: [1,2], [3] have perimeter 3.

%e a(6) = 4: [1,2,3] has perimeter 4.

%e 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.

%e a(10) = 5: [1,2,3,4] has perimeter 5.

%e a(15) = 6: [1,2,3,4,5] has perimeter 6.

%e a(29) = 15: [1,2,3,4,5,6,8] has perimeter 1+6+8 = 15.

%e a(30) = 12: [4,5,6,7,8] has perimeter 12.

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

%p `if`(i<1, infinity, min(`if`(t>1, i+1, 0)+b(n, i-1, iquo(t, 2)),

%p `if`(i>n, NULL, `if`(t=2, i+1, 0)+b(n-i, i-1, iquo(t, 2)+2)))))

%p end:

%p a:= n-> b(n$2, 0):

%p seq(a(n), n=0..100);

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

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

%K nonn,look,hear

%O 0,3

%A _Alois P. Heinz_, Jul 16 2013