Waste less time on Facebook — follow Brilliant.
×

How many sequences of consecutive integers sum to a particular positive integer greater than 1?

By the fundamental theorem of arithmetic, every positive integer greater than 1 can be written as a product of primes. Thus, we can write every positive integer as \(2^{ k }p_{ 1 }^{ q_{ 1 } }p_{ 2 }^{ q_{ 2 } }...p_{ m }^{ q_{ m } }\) for some non-2 primes \(\{ p_{ i }\} _{ i=1 }^{ m }\), some non-negative integer \(k\) and some positive integers \(\{ q_{ i }\} _{ i=1 }^{ m }\). Let's say that the sequence of consecutive integers starts at some integer \(x\) and ends at some integer \(x+n\) where \(n \) is some positive integer (thus there are \(n+1\) terms in the sequence). Note that this excludes sets with just one member. The sum of the consecutive integers is then given by \(\sum _{ k=0 }^{ n }{ (x+k) } \), and thus we need \(\sum _{ k=0 }^{ n }{ (x+k) } =2^{ k }p_{ 1 }^{ q_{ 1 } }p_{ 2 }^{ q_{ 2 } }...p_{ m }^{ q_{ m } }\) for the particular \(x\) and \(n\) to constitute a valid sequence of \(n+1\) members. This gives that \((n+1)x+\frac { n(n+1) }{ 2 } =2^{ k }p_{ 1 }^{ q_{ 1 } }p_{ 2 }^{ q_{ 2 } }...p_{ m }^{ q_{ m } }\quad \Leftrightarrow \quad x+\frac { n }{ 2 } =\frac { 2^{ k }p_{ 1 }^{ q_{ 1 } }p_{ 2 }^{ q_{ 2 } }...p_{ m }^{ q_{ m } }\quad }{ n+1 } \), and thus \(x=\frac { 2^{ k }p_{ 1 }^{ q_{ 1 } }p_{ 2 }^{ q_{ 2 } }...p_{ m }^{ q_{ m } }\quad }{ n+1 } -\frac { n }{ 2 } \).

So, the question becomes, how many positive integers \(n\) can we choose such that the right-hand side of that equation is an integer and thus, so too, is \(x\).

Well, there are two potential cases, that \(n\) is even and that \(n\) is odd. If \(n\) is even, we have that \(\frac { n }{ 2 }\) is an integer and thus, so too, must \(\frac { 2^{ k }p_{ 1 }^{ q_{ 1 } }p_{ 2 }^{ q_{ 2 } }...p_{ m }^{ q_{ m } }\quad }{ n+1 }\) be. Therefore, we have that \( (n+1)|2^{ k }p_{ 1 }^{ q_{ 1 } }p_{ 2 }^{ q_{ 2 } }...p_{ m }^{ q_{ m } }\). If that is the case, along with n being even, \(x\) must then be an integer and \(x\) and \(n\) constitute a valid pair. Thus, \(n+1\) must be any divisor of \(2^{ k }p_{ 1 }^{ q_{ 1 } }p_{ 2 }^{ q_{ 2 } }...p_{ m }^{ q_{ m } }\) such that \(n\) is even, or, equivalently that \(n+1\) is odd. Thus, we can let \(n+1\) be any odd, positive divisor (except 1) of \(2^{ k }p_{ 1 }^{ q_{ 1 } }p_{ 2 }^{ q_{ 2 } }...p_{ m }^{ q_{ m } }\) giving \((q_{ 1 }+1)(q_{ 2 }+1)(q_{ 3 }+1)...(q_{ m }+1)-1\) valid pairs \((x,n)\) which have even \(n\) (we wish to exclude the case where \(n+1=1\), as \(n\) must be a positive integer). Next, we have the case that \(n\) is odd. Going back to \(x+\frac { n }{ 2 } =\frac { 2^{ k }p_{ 1 }^{ q_{ 1 } }p_{ 2 }^{ q_{ 2 } }...p_{ m }^{ q_{ m } }\quad }{ n+1 }\), we have, multiplying both sides by 2, that \(2x+n=\frac { 2^{ k+1 }p_{ 1 }^{ q_{ 1 } }p_{ 2 }^{ q_{ 2 } }...p_{ m }^{ q_{ m } } }{ n+1 } \). Noting that because \(n\) is odd and \(2x\) is even, the left-hand side is an odd integer, and thus, so too, must the right-hand side be. Thus, \(n+1\) must be a divisor of \(\frac { 2^{ k+1 }p_{ 1 }^{ q_{ 1 } }p_{ 2 }^{ q_{ 2 } }...p_{ m }^{ q_{ m } } }{ n+1 }\) such that \(2^{ k+1 }|(n+1) \). Therefore, we have that \(n+1=2^{ k+1 }d\) where \(d\) can be any positive divisor of \(p_{ 1 }^{ q_{ 1 } }p_{ 2 }^{ q_{ 2 } }...p_{ m }^{ q_{ m } }\), as if \(d\) is a positive integer and \(k\) is a non-negative integer \(2^{ k+1 }d-1\) will always be a positive integer. Thus, because each \(d\) corresponds to \(1\) valid odd \(n\) we have \((q_{ 1 }+1)(q_{ 2 }+1)(q_{ 3 }+1)...(q_{ m }+1)\) valid odd \(n\) and, thus, \(2(q_{ 1 }+1)(q_{ 2 }+1)(q_{ 3 }+1)...(q_{ m }+1)-1\) total valid \(n\), corresponding to exactly that many sequences of consecutive integers which sum to our original positive integer (excluding the sequence of just that positive integer)!

Note by Chris Callahan
3 months, 2 weeks ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

This is an unusually interesting setup. I think having a problem that applies these stuffs might be worthwhile. Would you like to post one? Pi Han Goh · 1 month, 1 week ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...