A chain problem

[Ali Sada]

Hi everyone,

What are the triangular numbers, ( T(n) ), such that a chain of rods with lengths 1, 2, ..., ( n ) (connected by hinges) can be arranged to form a rectangle with a perimeter exactly equal to ( T(n) (i.e. using each rod exactly once without any loss or overlap)?

Best,

Ali

[Robert Israel]

So you want to partition the set {1 .. n} into four subsets, each with sum n*(n+1)/8.  Obviously you need that to be an integer, so n == 7 or 8 (mod 8). 

If n = 8*k + 7, we can first partition into 4*k+3 pairs and one singleton, each summing to 8*k+7, then take any partition of these 4*k+4 sets into four families of k+1.  Similarly, if n = 8*k, start by partitioning into 4*k pairs, each summing to 8*k+1.

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/CACOfRNpVryGMoqXYc24UQ4SdZ_4yksYX1qvPfpsswKV5s6Basg%40mail.gmail.com.

[M F Hasler]

On Thu, Mar 13, 2025 at 10:44 AM Robert Israel <isra...@gmail.com> wrote:

So you want to partition the set {1 .. n} into four subsets, each with sum n*(n+1)/8.  Obviously you need that to be an integer, so n == 7 or 8 (mod 8). 

If n = 8*k + 7, we can first partition into 4*k+3 pairs and one singleton, each summing to 8*k+7, then take any partition of these 4*k+4 sets into four families of k+1.  Similarly, if n = 8*k, start by partitioning into 4*k pairs, each summing to 8*k+1.

but "connected by hinges" means that they must be taken in order, so  T(n')-T(n'') =  T(n'')-T(n''') =  T(n'''')-T(n''') = T(n)/4 for some n'''', n''', n'', n' < n.

-Maximilian

[Brendan]

Ali wrote "rectangle", not "square".

Brendan/

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAFqvfd8pmn1V0j3UqNfLLdHG4ncWfG_Ch8O4DMb95CvfxUi4Lg%40mail.gmail.com.

[M F Hasler]

On Thu, Mar 13, 2025 at 11:07 AM Brendan <brend...@gmail.com> wrote:

Ali wrote "rectangle", not "square".

yes, sorry, thus :

T(n')-T(n'') =  T(n'''')-T(n''') = A

 T(n'')-T(n''') = B such that  A+B = T(n)/2 for some n'''', n''', n'', n' < n.

But not just "partition {1...n} in 4 sets".

-M

Brendan/

On Fri, Mar 14, 2025 at 2:01 AM M F Hasler <mha...@dsi972.fr> wrote:

On Thu, Mar 13, 2025 at 10:44 AM Robert Israel <isra...@gmail.com> wrote:

So you want to partition the set {1 .. n} into four subsets, each with sum n*(n+1)/8.  Obviously you need that to be an integer, so n == 7 or 8 (mod 8). 

If n = 8*k + 7, we can first partition into 4*k+3 pairs and one singleton, each summing to 8*k+7, then take any partition of these 4*k+4 sets into four families of k+1.  Similarly, if n = 8*k, start by partitioning into 4*k pairs, each summing to 8*k+1.

[Allan Wechsler]

As usual I started by seeing if people had worked on a simpler problem. This problem is, essentially, find triangular numbers A and B, A < B, such that A + B and 2B are also triangular. Looking for simple conditions to drop, I just ignored A and asked, what are the triangular numbers B such that 2B is also triangular? This turns out to be discussed in oeis.org/A075528 and oeis.org/A029549, the latter of which has a nice recurrence relation. So somebody could probably easily search for solutions to Ali's chain problem; I'm guessing that there are an infinite family of them.

This makes me wonder whether there are three-layer triangular numbers, that is, numbers B such that 2B and 3B are also triangular?

On Thu, Mar 13, 2025 at 11:07 AM Brendan <brend...@gmail.com> wrote:

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAJeNNUj8uNRPNaokR9FUPyLs28nR7FWmgkK-tuq7Vx5pNBymmg%40mail.gmail.com.

[Ali Sada]

Thank you all for your responses. I really appreciate them.

If we use Rober's approach, then we have two subsets with each sum n*(n+1)/4.  These two subsets are partitioned into five numbers r1,r2,r3,r4, and r5.

Area = k1*k2

T(n) = 2k1+2k2

We don't necessarily start at the corner.

1) We start at a point on one of the sides. We move r1 steps, let's say down. The length we have so far is T(r1), but this is not a full side yet.

2) Then, we move r2 steps to the left. The length of the side here is k2 = T(r2)+r1*r2.

3) Then we move up r3 steps. The length of this side is k1 = T(r3)+ r3*(r1+r2).

4) Then we move right r4 steps. The length of this side is k2 = T(r4)+r4*(r1+r2+r3)

5) Then we go back down r5 steps. This distance is T(r5)+r5*(r1+r2+r3+r4). We add this to T(r1) and we get the first side, k1.

I think that Allan's solution works in the special case where r1 = 0 (i.e. we start at the corner). Is that correct?

We have 6 unknowns (n,r1,r2,r3,r4,45), and we have four equations

n=r1+r2+r3+r4+r5

T(n) = 2k1+2k2

k2 =T(r2)+r1*r2 = T(r4)+r4*(r1+r2+r3)

k1 = T(r3)+ r3*(r1+r2) = T(r5)+r5*(r1+r2+r3+r4) +T(r1)

I don't know how to solve this!

Best,

Ali

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CADy-sGE-ZqBZZrSB0s8vEQf8GGD86%3DHi%2BxZJMOxQ-MPwxHxEPg%40mail.gmail.com.

[Allan Wechsler]

I completely missed the fact that the chain was allowed to start in the middle of a side.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CACOfRNpb9W%3D5va7Ps1fMMfDqesrsM9iRZAbFii4GYnuzwyn1Rg%40mail.gmail.com.

[M F Hasler]

On Thu, Mar 13, 2025 at 11:11 AM M F Hasler <mha...@dsi972.fr> wrote:

T(n')-T(n'') =  T(n'''')-T(n''') = A

T(n'')-T(n''') = B such that  A+B = T(n)/2 for some n'''', n''', n'', n' < n.

 

Once we've chosen A=T(n1)-T(n2), (where n > n1 > n2 > n3 > n4 >= 0),

we must have B=T(n2)-T(n3) such that  2 (A+B) = T(n), 

which determines  B = T(n)/2 - A  and thus  T(n3) = T(n2)-B

which therefore must be a triangular number. 

(cf. is_A000217(n)= n==(1+n=sqrtint(2*n))*n/2 )

That reduces the number of choices significantly.

In the same vein, we must then have n4 such that T(n3)-T(n4) = A,

so T(n4) = T(n3) - A must also be a triangular number.

T(n)=n*(n+1)/2

check(n,Tn=T(n))={ Tn%2==0 && forstep(n1=n-1,3,-1, T1=T(n1); forstep(n2=n1-1,2,-1,

(B = Tn/2 - A = T1 - T2 = T(n2)) < 3 && break ;  T2-B > 0 || next ; 

(1+n3=sqrtint(2*T3 = T2-B))*n3==2*T3 || next; T3-A < 0 && next ;

(1+n4=sqrtint(2*T4 = T3-A))*n4==2*T4 &&  return([n4, n3, n2, n1, n])))}

for(n=1,99, n%100 || print1([n]); (t=check(n)) && print(t" T's: "apply(T,t)))

[2, 4, 6, 7, 8] T's: [3, 10, 21, 28, 36] : Indeed : 7 + 11 + 7 + 11 = 28

[3, 9, 11, 14, 15] T's: [6, 45, 66, 105, 120] : Here, 39 + 21 + 39 + 21 = 120
[5, 11, 15, 18, 20] T's: [15, 66, 120, 171, 210]
[2, 6, 17, 18, 24] T's: [3, 21, 153, 171, 300]
[6, 16, 20, 25, 27] T's: [21, 136, 210, 325, 378]
[8, 18, 24, 29, 32] T's: [36, 171, 300, 435, 528]
[13, 15, 28, 29, 35] T's: [91, 120, 406, 435, 630]
[23, 26, 36, 38, 39] T's: [276, 351, 666, 741, 780]
[18, 25, 36, 40, 44] T's: [171, 325, 666, 820, 990]
[12, 17, 36, 38, 48] T's: [78, 153, 666, 741, 1176]
[12, 30, 38, 47, 51] T's: [78, 465, 741, 1128, 1326]
[13, 28, 41, 48, 55] T's: [91, 406, 861, 1176, 1540]
[27, 32, 48, 51, 56] T's: [378, 528, 1176, 1326, 1596]
[15, 37, 47, 58, 63] T's: [120, 703, 1128, 1711, 2016]
[17, 39, 51, 62, 68] T's: [153, 780, 1326, 1953, 2346]
[32, 44, 62, 69, 75] T's: [528, 990, 1953, 2415, 2850]
[46, 55, 73, 79, 80] T's: [1081, 1540, 2701, 3160, 3240]
[35, 44, 69, 74, 84] T's: [630, 990, 2415, 2775, 3570]
[41, 51, 74, 80, 87] T's: [861, 1326, 2775, 3240, 3828]
[23, 53, 69, 84, 92] T's: [276, 1431, 2415, 3570, 4278]
[11, 23, 68, 71, 95] T's: [66, 276, 2346, 2556, 4560]

[58, 67, 91, 97, 99] T's: [1711, 2278, 4186, 4753, 4950]

...

-M.

[Daniel Mondot]

I think I am finding the same results as Maximilian:

for n: 8, 15, 20, 24, 27, 32, 35, 39, 44, 48, 51, 55, 56, 63, 68, 75, 80, 84, 87, 92, 95, 99, 104, 111, 115, 116, 119, 120, 123, 124, 128, 132, 135, 140, 143, 144, 147, 152, 155, 159, 160, 164, 168, 171, 175, 176, 183, 184, 188, 195, 200

for the perimeters:

t(n): 36, 120, 210, 300, 378, 528, 630, 780, 990, 1176, 1326, 1540, 1596, 2016, 2346, 2850, 3240, 3570, 3828, 4278, 4560, 4950, 5460, 6216, 6670, 6786, 7140, 7260, 7626, 7750, 8256, 8778, 9180, 9870, 10296, 10440, 10878, 11628, 12090, 12720, 12880, 13530, 14196, 14706, 15400, 15576, 16836, 17020, 17766, 19110, 20100

Also, starting with n=20 (t(n)=210), there are multiple arrangements that produce a rectangle.

For instance, for n=99, I count 15 different rectangles.

Daniel

--

You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAFqvfd8OFm6xsszGV3tPzfrPEva_kEPW7zNFyvtvuJ5xEZGVSA%40mail.gmail.com.

[scottshannon68]

For what it's worth the 8 and 15 cases are pictured in the text file attached to A334720. I didn't consider at the time the ones which formed proper rectangles. 

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAD5iKagQ_BjJXMAo09FD1stVG04TcZXMsr9i9GYuhLDDEC8QaQ%40mail.gmail.com.

[Daniel Mondot]

For increasing values of n, since the number of solutions seem to increase, I was expecting that for n ≡ 3 mod 4 or n ≡ 0 mod 4 (the values of n that can produce complete rectangles), eventually, there would always be at least one solution, but it turns out that it's not the case.

While, for n=539, there are 66 possible rectangles, for n=595, there is only 1, and for n=599, there are none.

Here are the first few records:

# n t(n) (# solutions)

1 8 36 (1 solution)
2 20 210 (3 solutions)
3 35 630 (6 solutions)
4 84 3570 (10 solutions)
5 99 4950 (15 solutions)
6 195 19110 (21 solutions)
7 440 97020 (55 solutions)
8 539 145530 (66 solutions)

Just like some integers are highly composite, it seems that some values of n produce lots of rectangles, and some very few or none.

It also seems that the number of solutions always fall on these numbers; 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66 which are the triangular numbers.

But they don't appear in order. The first n with 45 solutions is 935.

Daniel.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/67d3600c.a70a0220.258fab.64da%40mx.google.com.

[Ali Sada]

" It also seems that the number of solutions always fall on these numbers; 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66 which are the triangular numbers."

WOW! This could be one of the most fascinating things I've ever seen! Can we confirm this for larger numbers?

Also, in the records you gave, it seems that T(n) is a multiple of the number of solutions. Is that correct?

Best,

Ali

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAD5iKahr3HRXcuMdQQugDW-8efcL0tWxbmwsBQXkOvFzM2A1Ag%40mail.gmail.com.

[Daniel Mondot]

T(n) isn't quite a multiple of the number of solutions, but close:

Here is a more recent record of the first time a particular number of solutions appears:

# n t(n) (# sol)

1 0 0 (0 solutions)
2 8 36 (1 solution)
3 20 210 (3 solutions)
4 35 630 (6 solutions)
5 84 3570 (10 solutions)
6 99 4950 (15 solutions)
7 195 19110 (21 solutions)
8 440 97020 (55 solutions)
9 455 103740 (28 solutions)
10 459 105570 (36 solutions)            << the exception: 36 doesn't divide 105570
11 539 145530 (66 solutions)
12 935 437580 (45 solutions)
13 1364 930930 (105 solutions)

Instead of looking at just the first time a number of solutions appear, If we look at all, there are more (yet, relatively rare) exceptions :

# 175 15400 (6 solutions)   // 15400 not a multiple of 3

# 208 21736 (3 solutions)   // 21736 not a multiple of 3

# 231 26796 (10 solutions)   // 26796 not a multiple of 5

# 252 31878 (15 solutions)   // 31878 not a multiple of 5

I hope it's not because of a bug.

And of course, for all the n that do not make rectangles, for instance:

# 592 175528 (0 solutions)           << we know that 175528 isn't a multiple of zero !! so all of these could be considered exceptions.

I'll let my program run overnight, to see if it can find new "number of solutions".

Daniel

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CACOfRNpbXHnkN1EOKwqqKjz2Gvh1ZNVxBgJweN3sKCPu%2BCdHNw%40mail.gmail.com.

[Ali Sada]

Thank you, Daniel! I will be waiting for your results impatiently!

You said " Just like some integers are highly composite, it seems that some values of n produce lots of rectangles, and some very few or none." I think this analogy is brilliant. My question here is: in this context, what are the 'composite' (or 'prime') numbers, are they the n's or the T(n)'s? Example: is 559 a 'prime' or is it T(599)?

Best,

Ali

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAD5iKagQvUy2jZv0YT2d8sb%2BsZF%3D18oPP%2B76to9TQnvrG438EA%40mail.gmail.com.

[Daniel Mondot]

On a different note... Anyone planning to watch the lunar eclipse and blood moon happening right now, this pi day, and Einstein's birthday? It might not be visible in Europe or further east, though.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CACOfRNpCOe-9p4mXog4pjO4zOLnfrn9KAGcY2p5RF_CELRaT7g%40mail.gmail.com.

[Ali Sada]

While Daniel's computer is doing its magic, here are three subsets of the original T(n)'s.

1) There are rectangles where one rod takes up an entire side. For example, when T(n) = 36, 7 takes up a whole side.

2) A subset of the previous one could be when the rod that takes up a whole side is the last one, i.e. n itself. This must be one of Allan's numbers, where we start from the corner.

3) A subset of the previous one could be when n takes the last side and n-1 takes the previous one. In this case, we have n-1 = T(r1), and n = T(r2)+r1*r2. 

Best,

Ali

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAD5iKaiJ70xmE90ejKx90Pwqu8xD5xosR1g0-nr7MjKWnjCLXg%40mail.gmail.com.

[Daniel Mondot]

Here an update, to the number of solutions to the chain problem:

New values for the number of solutions are still falling on triangular numbers:

# n t(n) (# sol)
1 0 0 (0 solutions)
2 8 36 (1 solution)
3 20 210 (3 solutions)
4 35 630 (6 solutions)
5 84 3570 (10 solutions)
6 99 4950 (15 solutions)
7 195 19110 (21 solutions)
8 440 97020 (55 solutions)
9 455 103740 (28 solutions)
10 459 105570 (36 solutions)

11 539 145530 (66 solutions)
12 935 437580 (45 solutions)
13 1364 930930 (105 solutions)

14 1484 1101870 (91 solutions)
15 1539 1185030 (171 solutions)
16 1595 1272810 (78 solutions)
17 1700 1445850 (120 solutions)

Now, we have this conjecture:

    A chain of n sticks, looping on itself, can be shaped into a rectangle in a distinct number of ways that is always a triangular number (0, 1, 3, 6, etc...)

I wouldn't know how to prove this conjecture to be true. 

And, disproving it may require a counter-example, but as n grows bigger, the time it takes to go through all possible foldings of the chain probably grows proportionally to n^2. So my program gets slower and slower.

Perhaps if we look if there are patterns at which way to fold the chain work, and which ways don't...

Any ideas?

Daniel.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CACOfRNo66QOrMFhYCfqPU8ZebrTmK3%2Brf2Z6opEh1vkqCVhiZg%40mail.gmail.com.

[Ali Sada]

Thank you, Daniel! There are two draft sequences now. Please take a look.

Best,

Ali

https://oeis.org/draft/A380867 ; https://oeis.org/draft/A380868

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAD5iKahPMxPK_rN4QU_%3DjBUbffUzBXzT-LNRZjyp%3D4-JLxvfmg%40mail.gmail.com.