OFFSET
1,5
COMMENTS
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.
From Robert G. Wilson v, Feb 04 2015: (Start)
Records: 1, 2, 3, 10, 11, 12, 131, 136, 140, 3887, 3921, 3950, 262555, 263112, 263707, 42240104, 42262878, 42285095, 16821037273, 16823225535, 16825391023, ..., .
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, ..., .
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, ..., .
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, ..., .
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, ..., .
3 occurs at: 7, 32, 33, 34, 113, 114, 115, 356, 357, 358, 1085, 1086, 1087, 3272, 3273, 3274, 9833, 9834, 9835, ..., .
5 occurs at: 29, 30, 31, 110, 111, 112, 353, 354, 355, 1082, 1083, 1084, 3269, 3270, 3271, 9830, 9831, 9832, ..., . (End)
LINKS
Md. Towhidul Islam, Table of n, a(n) for n = 1..88573
Md. Towhidul Islam, Formula for number of feasible partitions of n
Md Towhidul Islam & Md Shahidul Islam, 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, arXiv:1502.07730 [math.CO], 2015.
FORMULA
Let us suppose, a(0)=1 and for (3^(m-1)+1)/2<=n<=(3^m-1)/2, m=ceiling(log_3(2n)).
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)
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).
EXAMPLE
For n=3, minimum number of weights m is 2. The only "feasible" set of weights is [1,2]. So, a(3)=1.
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.
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.
MATHEMATICA
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 *)
PROG
(PARI) ok(v)=my(s); for(i=1, #v, if(v[i]>2*s+1, return(0), s+=v[i])); 1
a(n)=my(k=ceil(log(2*n)/log(3))); #select(ok, partitions(n, , k)) \\ Charles R Greathouse IV, Feb 02 2015
CROSSREFS
Cf. A254296, A254430, A254431, A254432, A254433, A254435, A254436, A254437, A254438, A254439, A254440, A254442.
KEYWORD
nonn,look
AUTHOR
Md. Towhidul Islam, Jan 27 2015
STATUS
approved