

A254296


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


13



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, 5, 3, 3, 3, 2, 2, 2, 1, 1, 1, 131, 136, 140, 133, 137, 140, 133, 136, 138, 129, 131, 134, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,5


COMMENTS

Define a feasible partition of an nkilogram 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 nkilogram Stone into Minimum Number of Weights to Weigh All Integral Weights from 1 to n kg(s) on a Twopan Balance, arXiv:1502.07730 [math.CO], 2015.


FORMULA

Let us suppose, a(0)=1 and for (3^(m1)+1)/2<=n<=(3^m1)/2, m=ceiling(log_3(2n)).
Then for (3^(m1)+1)/2<=n<=(3^(m1)+1)/2+(3^(m2)),a(n)=Sum{s=ceiling((n1)/3..floor((2n+3^(m2)1)/4)}a(s)Sum{d=ceiling((3n+2)/5)..(3^(m1)1)/2}Sum{p=ceiling((d1)/3..2dn1}a(p)
and for (3^(m1)+1)/2+3^(m2)+1<=n<=(3^m1)/2, a(n)=Sum_{s=ceiling((n1)/3)..(3^(m1)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}] (* JeanFranç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.
When we calculate a(n) for (3^(m1)+1)/2+3^(m2)+1 <= n <= (3^m1)/2 starting from n=(3^m1)/2 backwards, we get the sequence A062051 which is also the triplication of the terms of sequence A005704.
Sequence in context: A259977 A115312 A237721 * A248371 A237768 A237705
Adjacent sequences: A254293 A254294 A254295 * A254297 A254298 A254299


KEYWORD

nonn,look


AUTHOR

Md. Towhidul Islam, Jan 27 2015


STATUS

approved



