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 2kp1q1p2q2...pmqm2^{ k }p_{ 1 }^{ q_{ 1 } }p_{ 2 }^{ q_{ 2 } }...p_{ m }^{ q_{ m } } for some non-2 primes {pi}i=1m\{ p_{ i }\} _{ i=1 }^{ m }, some non-negative integer kk and some positive integers {qi}i=1m\{ q_{ i }\} _{ i=1 }^{ m }. Let's say that the sequence of consecutive integers starts at some integer xx and ends at some integer x+nx+n where nn is some positive integer (thus there are n+1n+1 terms in the sequence). Note that this excludes sets with just one member. The sum of the consecutive integers is then given by k=0n(x+k)\sum _{ k=0 }^{ n }{ (x+k) } , and thus we need k=0n(x+k)=2kp1q1p2q2...pmqm\sum _{ k=0 }^{ n }{ (x+k) } =2^{ k }p_{ 1 }^{ q_{ 1 } }p_{ 2 }^{ q_{ 2 } }...p_{ m }^{ q_{ m } } for the particular xx and nn to constitute a valid sequence of n+1n+1 members. This gives that (n+1)x+n(n+1)2=2kp1q1p2q2...pmqmx+n2=2kp1q1p2q2...pmqmn+1(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=2kp1q1p2q2...pmqmn+1n2x=\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 nn can we choose such that the right-hand side of that equation is an integer and thus, so too, is xx.

Well, there are two potential cases, that nn is even and that nn is odd. If nn is even, we have that n2\frac { n }{ 2 } is an integer and thus, so too, must 2kp1q1p2q2...pmqmn+1\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)2kp1q1p2q2...pmqm (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, xx must then be an integer and xx and nn constitute a valid pair. Thus, n+1n+1 must be any divisor of 2kp1q1p2q2...pmqm2^{ k }p_{ 1 }^{ q_{ 1 } }p_{ 2 }^{ q_{ 2 } }...p_{ m }^{ q_{ m } } such that nn is even, or, equivalently that n+1n+1 is odd. Thus, we can let n+1n+1 be any odd, positive divisor (except 1) of 2kp1q1p2q2...pmqm2^{ k }p_{ 1 }^{ q_{ 1 } }p_{ 2 }^{ q_{ 2 } }...p_{ m }^{ q_{ m } } giving (q1+1)(q2+1)(q3+1)...(qm+1)1(q_{ 1 }+1)(q_{ 2 }+1)(q_{ 3 }+1)...(q_{ m }+1)-1 valid pairs (x,n)(x,n) which have even nn (we wish to exclude the case where n+1=1n+1=1, as nn must be a positive integer). Next, we have the case that nn is odd. Going back to x+n2=2kp1q1p2q2...pmqmn+1x+\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=2k+1p1q1p2q2...pmqmn+12x+n=\frac { 2^{ k+1 }p_{ 1 }^{ q_{ 1 } }p_{ 2 }^{ q_{ 2 } }...p_{ m }^{ q_{ m } } }{ n+1 } . Noting that because nn is odd and 2x2x is even, the left-hand side is an odd integer, and thus, so too, must the right-hand side be. Thus, n+1n+1 must be a divisor of 2k+1p1q1p2q2...pmqmn+1\frac { 2^{ k+1 }p_{ 1 }^{ q_{ 1 } }p_{ 2 }^{ q_{ 2 } }...p_{ m }^{ q_{ m } } }{ n+1 } such that 2k+1(n+1)2^{ k+1 }|(n+1) . Therefore, we have that n+1=2k+1dn+1=2^{ k+1 }d where dd can be any positive divisor of p1q1p2q2...pmqmp_{ 1 }^{ q_{ 1 } }p_{ 2 }^{ q_{ 2 } }...p_{ m }^{ q_{ m } }, as if dd is a positive integer and kk is a non-negative integer 2k+1d12^{ k+1 }d-1 will always be a positive integer. Thus, because each dd corresponds to 11 valid odd nn we have (q1+1)(q2+1)(q3+1)...(qm+1)(q_{ 1 }+1)(q_{ 2 }+1)(q_{ 3 }+1)...(q_{ m }+1) valid odd nn and, thus, 2(q1+1)(q2+1)(q3+1)...(qm+1)12(q_{ 1 }+1)(q_{ 2 }+1)(q_{ 3 }+1)...(q_{ m }+1)-1 total valid nn, 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
2 years, 8 months ago

No vote yet
1 vote

</code>...<code></code> ... <code>.">   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 </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 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 - 2 years, 6 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...