This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A234951 #35 Jul 09 2025 04:15:00 %S A234951 1,1,2,1,3,3,1,3,4,4,1,4,5,6,5,1,4,6,7,7,6,1,4,6,9,9,9,7,1,5,7,9,11, %T A234951 11,10,8,1,5,7,10,12,14,13,12,9,1,5,8,11,13,14,15,15,13,10,1,5,8,11, %U A234951 13,16,16,18,17,15,11,1,5,8,12,14,17,18,19,20,19 %N A234951 Array read by antidiagonals upwards: T(n,k) (n>=1, k>=1) is the solution to the (n,k) stick problem. %C A234951 For the precise definition of T(n,k) see Section 2.4 of Bertagnolli (2013). %H A234951 A. Bertagnolli, <a href="http://ajbertagnolli.com/wp-content/uploads/2013/10/sticks2.pdf">The Stick Problem</a>, 2013. %F A234951 No (nontrivial) rows or columns have so far been identified. %F A234951 Comments from _Don Reble_, Jan 14 2014: (Start) %F A234951 The second row is floor(3K/2). %F A234951 Part A) With K-1 ones and floor(K/2) twos, one can't make a K-sided polygon. (Total sticks: floor(3K/2)-1.) %F A234951 There aren't enough ones for a length-1 K-polygon. %F A234951 The total length is <= (K-1)+K, not enough for a length-2 K-polygon. %F A234951 Part B) With A ones and floor(3K/2)-A twos, one can make a K-sided polygon. %F A234951 If there are K or more ones, make a length-1 K-polygon. %F A234951 If not, then A<K. In any case, one can make length-2 polygon with %F A234951 Q=[floor(3K/2)-A + floor(A/2)] sides. %F A234951 A<K implies A-floor(A/2) = ceiling(A/2) <= floor(K/2) %F A234951 Q = floor(3K/2)-A + floor(A/2) %F A234951 = floor(3K/2) - (A - floor(A/2)) %F A234951 >= floor(3K/2) - floor(K/2) %F A234951 = K + floor(K/2) - floor(K/2) = K %F A234951 So the length-2 polygon has at least K sides. %F A234951 --- %F A234951 The third row is 2K-1. The 2K-2 counterexamples are [0,K-1,K-1] %F A234951 (as hinted by Bertagnolli's 4.2). %F A234951 Part B) With A ones, B twos, and 2K-1-(A+B) threes, one can make a K-sided polygon. %F A234951 If there are K or more ones, or K or more twos, make a 1-or-2-length. %F A234951 If not, then A<K and B<K. In any case, one can make a length-3 %F A234951 polygon with Q=[2K-1-(A+B) + min(A,B)] sides. %F A234951 A+B = max(A,B) + min(A,B), so %F A234951 Q = 2K-1 - (A+B) + min(A,B) = 2K-1 - max(A,B) > 2K-1 - K = K-1 %F A234951 The length-3 polygon has more than K-1 sides, so at least K. %F A234951 (End) %F A234951 Comments from _Alex Meiburg_, Jan 14 2014: (Start) %F A234951 Indeed, I think he mentions that in the paper. It's nice to have a proof though. %F A234951 I'm particularly curious about column two -- it seems to be a pretty simple question, really; it answers the questions "How many items between 1 and N can you pick, such that no two nonzero, non-intersecting subsets have the same sum". This is NP Hard to check (very close to the knapsack problem) in a specific instance, but one would hope that it has some sort of simple solution. %F A234951 I have the following proof that each row grows asymptotically linearly (and, I believe, with a periodic deviation from the exact linear fit): View the problem of picking the x_i objects, for i=1 to n, as picking a point in Z^n. That is, the tuples they list in their paper e.g. (0,4,4) as a counterexample, corresponds to the point (0,4,4) in 3-space. Now each of the constraints can be modeled by a set of hyperplanes. For instance, each n has the limitation that x_1<k, which corresponds to the restriction on making k sides of length 1. For sides of length 2, we have x_2 + floor(x_1/2)<k, where the left hand side the maximum sides of length 2 constructible as a function of x_1 and x_2. For sides of length 3, the expression is a bit more complex: x_3 + min(x_2, x_1) + max(0,floor((x_1-x_2)/3))<k. The min/max are responsible for describing either the case where we have more 1s than 2s, in which case it simplifies to x_3+x_2+floor((x_1-x_2)/3), or the case where we have more 2s than 1s, in which case it simplifies to x_3+x_1. These two cases can be combined into one Boolean condition, then, based on which of the two cases is true. %F A234951 The condition corresponding to sides of length 4 would then be floor(x_2/2) + min(x_3, x_1)<k. It can similarly be split based on which of the two cases is true, then. We could look at sides of length 5 and above, but obviously these are rendered superfluous by the lower numbers. The condition is as follows, then, for the full case of n=3: %F A234951 (x_1<k) && (x_2 + floor(x_1/2)<k) && ( (x_3+x_2+floor((x_1-x_2)/3)<k && x_1>=x_2) || (x_3+x_1<k && x_2>=x_1) ) & ( ((floor(x_2 / 2)+x_3<k) && (x_3<=x_1) || ((floor(x_2 / 2)+x_1<k) && (x_1<=x_3))) %F A234951 It should be clear that any kind of expression involving max/min can be split up similarly. The general algorithm for generating such an algorithm for any n is to look at each side length (until the maximum side length is reached, which can be bounded by n(n+1)/2, because in order to make k copies of that we already have at least k-1 copies of one of the numbers from 1 to n), find the various permutations that generate it, put them in a max() function to choose the one that will generate the most, and then break this max apart into several conditions. %F A234951 This Boolean expression, no matter how complicated, is only composed of linear combinations and floors (the only non-linear element, which I'm going to call pseudo-linear) -- and, crucially, is fixed for a given n, so we can change k and the condition remains the same. In n-space, this condition defines a polytope -- if it were just a bunch of inequalities joined with &&, then we would have the simplex problem; with the max, we get concavities in our solution space. Still, it's entirely pseudo-linear. %F A234951 The problem is maximizing x_1+x_2+x_3..., amid these conditions. This maximum solution is then the "counterexample", and adding one more is necessarily outside of the solution set. %F A234951 All of these pseudo-linear conditions only deviate by a bounded value from a true linear condition. It's not hard to see that, as k varies and these hyperplanes move, they add a constant linear amount to that maximizing vertex - look at solutions of the simplex algorithm with a similar setup. Thus, as k varies, the sequence as a whole grows roughly linearly. The only deviations are due to the floor functions, which are periodic. This leads me to believe that the deviation from an "exact" linear solution is periodic as well, although I'm not sure how to prove this or find the period exactly. %F A234951 (End) %e A234951 The array begins: %e A234951 n\k| 1 2 3 4 5 6 7 8 9 10 ... %e A234951 -------------------------------------- %e A234951 1 | 1 2 3 4 5 6 7 8 9 10 ... %e A234951 2 | 1 3 4 6 7 9 10 12 13 15 ... %e A234951 3 | 1 3 5 7 9 11 13 15 17 19 ... %e A234951 4 | 1 4 6 9 11 14 15 18 20 23 ... %e A234951 5 | 1 4 6 9 12 14 16 19 21 24 ... %e A234951 6 | 1 4 7 10 13 16 18 21 ... %e A234951 7 | 1 5 7 11 13 17 ... %e A234951 8 | 1 5 8 11 14 ... %e A234951 9 | 1 5 8 12 ... %e A234951 10 | 1 5 8 12 ... %e A234951 11 | 1 5 ... %e A234951 12 | 1 5 ... %e A234951 13 | 1 6 ... %e A234951 14 | 1 6 ... %e A234951 ... %K A234951 nonn,tabl,nice %O A234951 1,3 %A A234951 _N. J. A. Sloane_, Jan 12 2014