Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
%I #57 Apr 17 2016 11:41:22
%S 1,1,1,1,2,2,3,2,2,2,1,1,1,10,11,12,11,12,12,11,11,12,9,9,9,7,7,7,5,5,
%T 5,3,3,3,2,2,2,1,1,1,131,136,140,133,137,140,133,136,138,129,131,134,
%U 125,126,128,117,119,120,109,110,111,101,102,102,92,92,93,81,81,81,72,72,72,63,63,63,54,54,54,47,47,47,40,40,40,33,33,33
%N The number of partitions of n having the minimum number of summands such that all integers from 1 to n can be represented as the sum of the summands times one of {-1, 0, 1}.
%C Define a feasible partition of an n-kilogram stone as an ordered partition of minimum possible m parts W_1 <= W_2 <= ... <= W_m broken from the stone such that all integral weights from 1 to n can be weighed in one weighing using the parts/weights on a two pan balance. The minimum m for any n is m=ceiling(log_3(2n)). This sequence gives the number of feasible partitions of n.
%C From _Robert G. Wilson v_, Feb 04 2015: (Start)
%C Records: 1, 2, 3, 10, 11, 12, 131, 136, 140, 3887, 3921, 3950, 262555, 263112, 263707, 42240104, 42262878, 42285095, 16821037273, 16823225535, 16825391023, ..., .
%C Possible values: 1, 2, 3, 5, 7, 9, 10, 11, 12, 15, 18, 23, 28, 33, 40, 47, 54, 63, 72, 81, 92, 93, 101, 102, 105, ..., .
%C First occurrence on k, or 0 if not present: 1, 5, 7, 0 29, 0, 26, 0, 23, 14, 15, 16, 0, 0, 98, 0, 0, 95, 0, 0, 0, 0, 92, ..., .
%C 1 occurs at: 1, 2, 3, 4, 11, 12, 13, 38, 39, 40, 119, 120, 121, 362, 363, 364, 1091, 1092, 1093, 3278, 3279, 3280, 9839, 9840, 9841, ..., .
%C 2 occurs at: 5, 6, 8, 9, 10, 35, 36, 37, 116, 117, 118, 359, 360, 361, 1088, 1089, 1090, 3275, 3276, 3277, 9836, 9837, 9838, ..., .
%C 3 occurs at: 7, 32, 33, 34, 113, 114, 115, 356, 357, 358, 1085, 1086, 1087, 3272, 3273, 3274, 9833, 9834, 9835, ..., .
%C 5 occurs at: 29, 30, 31, 110, 111, 112, 353, 354, 355, 1082, 1083, 1084, 3269, 3270, 3271, 9830, 9831, 9832, ..., . (End)
%H Md. Towhidul Islam, <a href="/A254296/b254296.txt">Table of n, a(n) for n = 1..88573</a>
%H Md. Towhidul Islam, <a href="/A254296/a254296_1.pdf">Formula for number of feasible partitions of n</a>
%H Md Towhidul Islam & Md Shahidul Islam, <a href="http://arxiv.org/abs/1502.07730">Number of Partitions of an n-kilogram Stone into Minimum Number of Weights to Weigh All Integral Weights from 1 to n kg(s) on a Two-pan Balance</a>, arXiv:1502.07730 [math.CO], 2015.
%F Let us suppose, a(0)=1 and for (3^(m-1)+1)/2<=n<=(3^m-1)/2, m=ceiling(log_3(2n)).
%F Then for (3^(m-1)+1)/2<=n<=(3^(m-1)+1)/2+(3^(m-2)),a(n)=Sum{s=ceiling((n-1)/3..floor((2n+3^(m-2)-1)/4)}a(s)-Sum{d=ceiling((3n+2)/5)..(3^(m-1)-1)/2}Sum{p=ceiling((d-1)/3..2d-n-1}a(p)
%F and for (3^(m-1)+1)/2+3^(m-2)+1<=n<=(3^m-1)/2, a(n)=Sum_{s=ceiling((n-1)/3)..(3^(m-1)-1)/2}a(s).
%e For n=3, minimum number of weights m is 2. The only "feasible" set of weights is [1,2]. So, a(3)=1.
%e For n=7, m is 3. The "feasible" sets of weights are [1,1,5], [1,2,4], [1,3,3]. So, a(7)=3.
%e For n=19, m is 4. The "feasible" sets of weights are [1,1,4,13], [1,1,5,12], [1,2,3,13], [1,2,4,12], [1,2,5,11], [1,2,6,10], [1,2,7,9], [1,3,3,12], [1,3,4,11], [1,3,5,10], [1,3,6,9], [1,3,7,8]. There are no other "feasible" sets. So, a(19)=12.
%t okQ[v_] := Module[{s=0}, For[i=1, i <= Length[v], i++, If[v[[i]] > 2*s+1, Return[ False], s += v[[i]] ] ]; Return[True]]; a[n_] := With[{k = Ceiling[Log[3, 2n]]}, Select[Reverse /@ IntegerPartitions[n, {k}], okQ] // Length]; Table[a[n], {n, 1, 88}] (* _Jean-François Alcover_, Feb 03 2015, after _Charles R Greathouse IV_ *)
%o (PARI) ok(v)=my(s);for(i=1,#v,if(v[i]>2*s+1,return(0),s+=v[i]));1
%o a(n)=my(k=ceil(log(2*n)/log(3))); #select(ok, partitions(n,,k)) \\ _Charles R Greathouse IV_, Feb 02 2015
%Y Cf. A254296, A254430, A254431, A254432, A254433, A254435, A254436, A254437, A254438, A254439, A254440, A254442.
%Y When we calculate a(n) for (3^(m-1)+1)/2+3^(m-2)+1 <= n <= (3^m-1)/2 starting from n=(3^m-1)/2 backwards, we get the sequence A062051 which is also the triplication of the terms of sequence A005704.
%K nonn,look
%O 1,5
%A _Md. Towhidul Islam_, Jan 27 2015