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
1 year, 2 months ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 \( 2 \times 3 \)
2^{34} \( 2^{34} \)
a_{i-1} \( a_{i-1} \)
\frac{2}{3} \( \frac{2}{3} \)
\sqrt{2} \( \sqrt{2} \)
\sum_{i=1}^3 \( \sum_{i=1}^3 \)
\sin \theta \( \sin \theta \)
\boxed{123} \( \boxed{123} \)

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 year ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...