A254442 -id:A254442 - 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).

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.

A254432 Natural numbers with the maximum number of "feasible" partitions of length m.

Original entry on oeis.org

1, 2, 3, 4, 7, 16, 18, 19, 22, 43, 46, 124, 367, 1096, 3283, 9844, 29527, 88576, 265723, 797164, 2391487, 7174456, 21523363, 64570084, 193710247, 581130736, 1743392203, 5230176604

Offset: 1

Md. Towhidul Islam, Jan 30 2015

nonn

Sequence A254296 describes "feasible" partitions and gives the number of all "feasible" partitions of all natural numbers. We must take the value of m from there.
Here we list the natural numbers with the highest number of "feasible" partitions of length m. Such numbers are unique for all m except for m=[2,4,5].
For m>=6, there is a unique natural number with the maximum number of "feasible" partitions.

			Natural numbers with maximum "feasible" partitions are unique for all m except for m=[2,4,5].
For m=1, the number 1 has 1 "feasible" partition.
For m=2, three numbers 2,3 and 4 each has the highest 1 "feasible" partition.
For m=3, the number 7 has the highest 3 "feasible" partitions.
For m=4, four numbers 16,18,19 and 22 each has the highest 12 "feasible" partitions.
For m=5, two numbers 43 and 46 each has 140 "feasible" partitions.
For m=6, the number 124 has the highest 3950 "feasible" partitions.
For m=7, the number 367 has the highest 263707 "feasible" partitions.
For m=8, the number 1096 has the highest 42285095 "feasible" partitions.

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, A254433, A254435, A254436, A254437, A254438, A254439, A254440, A254442.

For the first 11 values, there is no specific formula.
For n>=12, a(n) = (3^(m-7)+5)/2.
Recursively, for n>=13, a(n) = 3*a(n-1)-5.

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

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

Comments

Links

Crossrefs

A254432 Natural numbers with the maximum number of "feasible" partitions of length m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula