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
4 years, 10 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. 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 1paragraph 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}$

Sort by:

This is an unusually interesting setup. I think having a problem that applies these stuffs might be worthwhile. Would you like to post one?

- 4 years, 7 months ago