- #1
TimNguyen
- 80
- 0
Compositions into Relatively Prime Parts
Hello.
I was reading a journal and an interesting problem came up. I believe the journal was in the American Mathematics Society publications. Well, here's the statement.
"For all integers, n greater than or equal to 3, the number of compositions of n into relatively prime parts is a multiple of 3."
Example : For 4: the compositions of relatively prime parts are:
(1,3), (3,1), (2,1,1), (1,2,1), (1,1,2), (1,1,1,1).
This is what I have so far for a "proof":
Let n be an integer greater than or equal to 3.
Then the first composition will be given by (n-1, 1), (1, n-1); since for all k, an integer, (k, 1) and (1, k) are always relatively prime.
Also, (1, 1, ..., 1) where the composition adds to n is also an obtainable composition.
(So basically, I've gotten the end points of the compositions to be a multiple of 3, then I need to prove that the "in-between" compositions will also be a multiple of 3.)
Well, obviously I'm stuck there. I've tried to split it into two cases afterwards where the cases involve n - odd and n - even but it has come to no avail. Also I've tried to find a formula where the compositions of relatively prime parts is a multiple of 3 but it fails at "6". Here was the formula I came up with that failed, if it could be potentially be improved upon.
Formula: Starting at n=1, where i=3, i being the starting point.
(i)!/2^n
Like:
For 3, 3! = 6 divided by 2^1 = 2 will equal 3 compositions- a multiple of 3
For 4, 4! = 24 divided by 2^2 = 4 will equal 6 compositions - a multiple of 3
For 5, 5! = 120 divided by 2^3 = 8 will equal 15 compositions - multiple of 3
Well, hopefully people will post their ideas...
Hello.
I was reading a journal and an interesting problem came up. I believe the journal was in the American Mathematics Society publications. Well, here's the statement.
"For all integers, n greater than or equal to 3, the number of compositions of n into relatively prime parts is a multiple of 3."
Example : For 4: the compositions of relatively prime parts are:
(1,3), (3,1), (2,1,1), (1,2,1), (1,1,2), (1,1,1,1).
This is what I have so far for a "proof":
Let n be an integer greater than or equal to 3.
Then the first composition will be given by (n-1, 1), (1, n-1); since for all k, an integer, (k, 1) and (1, k) are always relatively prime.
Also, (1, 1, ..., 1) where the composition adds to n is also an obtainable composition.
(So basically, I've gotten the end points of the compositions to be a multiple of 3, then I need to prove that the "in-between" compositions will also be a multiple of 3.)
Well, obviously I'm stuck there. I've tried to split it into two cases afterwards where the cases involve n - odd and n - even but it has come to no avail. Also I've tried to find a formula where the compositions of relatively prime parts is a multiple of 3 but it fails at "6". Here was the formula I came up with that failed, if it could be potentially be improved upon.
Formula: Starting at n=1, where i=3, i being the starting point.
(i)!/2^n
Like:
For 3, 3! = 6 divided by 2^1 = 2 will equal 3 compositions- a multiple of 3
For 4, 4! = 24 divided by 2^2 = 4 will equal 6 compositions - a multiple of 3
For 5, 5! = 120 divided by 2^3 = 8 will equal 15 compositions - multiple of 3
Well, hopefully people will post their ideas...
Last edited:
