|
| |
|
|
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 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.
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
|
|
|
|
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
|
|
|
CROSSREFS
|
Cf. A254296, A254430, A254431, A254432, A254433, A254435, A254436, A254437, A254438, A254439, A254440, A254442.
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.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
