A254432 -id:A254432 - cp's OEIS frontend

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

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

Offset: 1

Md. Towhidul Islam, Jan 27 2015

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)

			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.

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.

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.

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

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

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

A254436 A component sequence of A254296.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 2, 1, 2, 1, 4, 3, 6, 3, 6, 5, 8, 7, 10, 7, 12, 9, 14, 11, 16, 14, 19, 17, 22, 20, 28, 23, 31, 26, 34, 32, 40, 35, 43, 38, 51, 46, 59, 51, 64, 61, 74, 71, 84, 76, 94, 86, 104, 96, 114, 108, 126, 120, 138, 132, 157, 146, 171

Offset: 1

Md. Towhidul Islam, Feb 28 2015

nonn

This sequence is a component of the formula for counting A254296.

If m=ceiling(log_3(2k)), define n=(3^(m-1)+1)/2+(3^(m-2))-k for k in the range (3^(m-1)+1)/2<=k<=(3^(m-1)-1)/2+(3^(m-2)). Then this sequence gives the first 3^(m-2) terms.

Md. Towhidul Islam, Table of n, a(n) for n = 1..6561
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.

Cf. A254296, A254430, A254431, A254432, A254433, A254435, A254437, A254438, A254439, A254440.

If m=ceiling(log_3(2k)), define n=(3^(m-1)+1)/2+(3^(m-2))-k for k in the range (3^(m-1)+1)/2<=k<=(3^(m-1)-1)/2+(3^(m-2)).

Then a(n)=Sum_{d=ceiling((3k+2)/5)..(3^(m-1)-1)/2} Sum_{p=ceiling((d-1)/3..2d-k-1} A254296(p).

A254438 Natural numbers k such that k is a multiple of its number of "feasible" partitions.

Original entry on oeis.org

1, 2, 3, 4, 6, 8, 10, 11, 12, 13, 28, 30, 33, 36, 38, 39, 40, 72, 92, 110, 114, 116, 118, 119, 120, 121, 330, 350, 355, 357, 360, 362, 363, 364, 1086, 1088, 1090, 1091, 1092, 1093, 3248, 3270, 3273, 3276, 3278, 3279, 3280, 9792, 9828, 9830, 9834, 9836, 9838, 9839, 9840, 9841, 29376, 29512, 29515, 29517, 29520, 29522, 29523, 29524

Offset: 1

Md. Towhidul Islam, Mar 01 2015

nonn

This sequence lists the natural numbers k that are divisible by A254296(k).

			For n=1,2,3, A254296(n)=1, so they are in the sequence.
For n=4,6,8,10, A254296(n)=2, so they are in the sequence.
For n=5,9, A254296(n)=2, so they are not in the sequence.

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.

Cf. A254296, A254430, A254431, A254432, A254433, A254435, A254436, A254437, A254438, A254439, A254440.

(* This program is not suitable to compute a large number of terms. *)
okQ[v_] := Module[{s=0}, For[i=1, i <= Length[v], i++, If[v[[i]] > 2s+1, Return[False], s += v[[i]]]]; Return[True]];
b[n_] := b[n] = With[{k = Ceiling[Log[3, 2 n]]}, Select[Reverse /@ IntegerPartitions[n, {k}], okQ] // Length];
Reap[Do[If[Divisible[k, b[k]], Print[k]; Sow[k]], {k, 1, 120}]][[2, 1]] (* Jean-François Alcover, Nov 03 2018 *)

a(48)-a(64) added by Md. Towhidul Islam, Apr 18 2015

A254439 Median of terms of A254296 in the range (3^(n-1)+1)/2 to (3^n-1)/2.

Original entry on oeis.org

1, 1, 2, 7, 47, 682, 23132, 1913821, 397731998, 212521309666, 297464368728296

Offset: 1

Md. Towhidul Islam, Mar 01 2015

As described in A254296, all the 'feasible' partitions of natural numbers (3^(n-1)+1)/2 to (3^n-1)/2 has n parts. A254439 lists the "median of the range ((3^(n-1)+1)/2)-th to ((3^n-1)/2)-th terms of A254296".

From conjectured formula, it appears that next terms are 1107102779611719118, 11090084422457163934046, 302002529294596303158583642. - Benedict W. J. Irwin, Nov 16 2016

			As described in sequence A254296, "feasible" partitions of the integers 41 through 121 consist of 5 parts. The number 3^(5-1) = 81 has 47 "feasible" partitions, which is the median of the range from the 41st to the 121st term of A254296.

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.

Cf. A254296, A254430, A254431, A254432, A254433, A254435, A254436, A254437, A254438, A254440.

/* C Code to make Mathematica Code for conjectured n-th term n>3 */
#include 
int main(int argc, char* argv[]){
int i, n=atoi(argv[1])-3;
printf("F[a_,x_,k_]:=Sum[x,{a,1,k}]\n");
for(i=1; i<=n; i++)printf("F[i%d,",i);
printf("3i%d-1,",n);
for(i=n-1; i>0; i--)printf("3i%d-1],",i);
printf("2]\n");
return 0;
}
/* Benedict Irwin, Nov 16 2016 */

F[a_, x_, k_] := Sum[x, {a, 1, k}]
F[i1, 3*i1 - 1, 2]
F[i1, F[i2, 3*i2 - 1, 3*i1 - 1], 2]
F[i1, F[i2, F[i3, 3*i3 - 1, 3*i2 - 1], 3*i1 - 1], 2]
F[i1, F[i2, F[i3, F[i4, 3*i4 - 1, 3*i3 - 1], 3*i2 - 1], 3*i1 - 1], 2] (* Examples of how to get first few terms, use the C code to generate the n-th term of the conjectured formula, Benedict W. J. Irwin, Nov 16 2016 *)

a(n) = A254296(3^(n-1)).

Conjecture: for n>3, a(n+3) = Sum_{i_1=1..2} Sum_{i_2=1..3*i_1-1} ... Sum_{i_n..3*i_(n-1)-1} (3*i_n - 1). - Benedict W. J. Irwin, Nov 16 2016

A254430 Number of "feasible" partitions with n parts.

Original entry on oeis.org

1, 3, 16, 183, 4804, 299558, 45834625, 17696744699, 17644374475261, 46279884666882734, 324101360547203133793

Offset: 1

Md. Towhidul Islam, Jan 30 2015

nonn

This sequence answers the question: "How many sellers can each be provided with a distinct set of n-part 'feasible' weights described in A254296?" It counts all the n-part "feasible" partitions of all the natural numbers from (3^(n-1)+1)/2 to (3^n-1)/2. Here n resembles m in A254296.

			For n=2, we count 2nd through 4th values of A254296. So a(2)=1+1+1=3.
For n=3, we count 5th through 13th values from A254296. So a(3)= 2+2+3+2+2+2+1+1+1 = 16.
For n=4, a(4)= Sum of 14th through 40th terms of A254296, that is, 183.

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.

Cf. A254296, A254431, A254432, A254433, A254435, A254436, A254437, A254438, A254439, A254440, A254442.

okQ[v_] := Module[{s = 0}, For[i = 1, i <= Length[v], i++, If[v[[i]] > 2s + 1, Return[False], s += v[[i]]]]; Return[True]];
a254296[n_] := With[{k = Ceiling[Log[3, 2n]]}, Select[Reverse /@ IntegerPartitions[n, {k}], okQ] // Length];
a[n_] := Sum[a254296[p], {p, (3^(n-1) + 1)/2, (3^n - 1)/2}];
Array[a, 5] (* Jean-François Alcover, Nov 04 2018, after Charles R Greathouse IV in A254296 *)

a(n) = Sum_{p=(3^(n-1)+1)/2..(3^n-1)/2} A254296(p).

a(9)-a(11) from Md. Towhidul Islam, Apr 18 2015

A254431 Number of "feasible" partitions of the smallest natural number of length n.

Original entry on oeis.org

1, 1, 2, 10, 131, 3887, 262555, 42240104, 16821037273, 17094916187012, 45374905859155948

Offset: 1

Md. Towhidul Islam, Jan 30 2015

The sequence lists the number of "feasible" partitions of the first natural number (3^(n-1)+1)/2 of length n. Here n resembles m in A254296 which describes "feasible" partitions.

			The smallest natural numbers "feasibly" partitionable into 1, 2, 3, 4 and 5 parts respectively are 1,2,5,14 and 41. From A254296, the number of "feasible" partitions of them are 1,1,2,10 and 131.

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.

Cf. A254296, A254430, A254432, A254433, A254435, A254436, A254437, A254438, A254439, A254440, A254442.

a(n) = A254296((3^(n-1)+1)/2).

a(10)-a(11) from Md. Towhidul Islam, Apr 18 2015

A254433 Maximum number of "feasible" partitions of length n.

Original entry on oeis.org

1, 1, 3, 12, 140, 3950, 263707, 42285095, 16825391023, 17095967464466, 45375565948693336

Offset: 1

Md. Towhidul Islam, Feb 03 2015

a(n) gives the highest value in the (3^(n-1)+1)/2-th through the (3^n-1)/2-th terms of the sequence A254296. It lists the highest possible number of "feasible" partitions into n parts.

			The numbers 2, 3 and 4 are "feasibly" partitionable into 2 parts. Each of them has 1 feasible partitions. So a(2)=1.
The numbers 14 to 40 are "feasibly" partitionable into 4 parts. Among them 16, 18, 19 and 22 each has the highest 12 "feasible" partitions. So a(4)=12.
The numbers 122 to 364 are "feasibly" partitionable into 6 parts. Among them 124 has the highest 3950 "feasible" partitions. So a(6)=3950.

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.

Cf. A254296, A254430, A254431, A254432, A254435, A254436, A254437, A254438, A254439, A254440, A254442.

The first term is 1. For n>=2, a(n) = A254296((3^(n-1)+5)/2).

a(9) corrected and a(10)-a(11) added by Md. Towhidul Islam, Apr 18 2015

A254435 Squares in A254296.

Original entry on oeis.org

1, 9, 81, 729, 1296, 23532201

Offset: 1

Md. Towhidul Islam, Feb 03 2015

They seem to be in the ((3^(n-1) + 1)/2)-th to ((3^(n-1)-1)/2 + 3^(n-2))-th values of A254296, though this is not proved. The terms are the squares of: 1, 3, 9, 27, 36, 4851.

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.

Cf. A254296, A254430, A254431, A254432, A254433, A254436, A254437, A254438, A254439, A254440, A254442.

A254442 Triangle read by rows: T(n,k) is the total number of parts of denomination k used in all n-part feasible partitions described in A254296.

Original entry on oeis.org

1, 4, 1, 1, 19, 7, 10, 3, 3, 2, 2, 1, 1, 201, 62, 124, 27, 37, 35, 42, 31, 35, 16, 16, 14, 14, 12, 12, 9, 9, 7, 7, 5, 5, 3, 3, 2, 2, 1, 1, 5020, 1271, 3551, 431, 719, 840, 1128, 851, 1051, 255, 303, 327, 369, 370, 408, 358, 387, 340, 366, 309, 330, 262, 280, 248, 264, 226, 238, 183, 183, 173, 173, 162, 162, 150, 150

Offset: 1

Md. Towhidul Islam, May 12 2015

Row n contains 3^(n-1) terms.

Sum of row n equals n*A254430(n).

			Triangle begins:
1;
4, 1, 1;
19, 7, 10, 3, 3, 2, 2, 1, 1;
201, 62, 124, 27, 37, 35, 42, 31, 35, 16, 16, 14, 14, 12, 12, 9, 9, 7, 7, 5, 5, 3, 3, 2, 2, 1, 1;
5020, 1271, 3551, 431, 719, 840, 1128, 851, 1051, 255, 303, 327, 369, 370, 408, 358, 387, 340, 366, 309, 330, 262, 280, 248, 264, 226, 238, 183, 183, 173, 173, 162, 162, 150, 150, 139, 139, 127, 127, 115, 115, 104, 104, 93, 93, 81, 81, 72, 72, 63, 63, 54, 54, 47, 47, 40, 40, 33, 33, 28, 28, 23, 23, 18, 18, 15, 15, 12, 12, 9, 9, 7, 7, 5, 5 ,3, 3, 2, 2, 1, 1;

Md. Towhidul Islam, Table of n, a(n) for n = 1..364
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.

Cf. A254296, A254431, A254432, A254433, A254435, A254436, A254437, A254438, A254439, A254440.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A254436 A component sequence of A254296.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A254438 Natural numbers k such that k is a multiple of its number of "feasible" partitions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A254439 Median of terms of A254296 in the range (3^(n-1)+1)/2 to (3^n-1)/2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Mathematica

Formula

A254430 Number of "feasible" partitions with n parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A254431 Number of "feasible" partitions of the smallest natural number of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A254433 Maximum number of "feasible" partitions of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A254435 Squares in A254296.

Views

Author

Keywords