Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Background (feel free to skip this part)

Suppose we want to $k$-partition all the positive integers up to (and including) some integer $N$. This partition should divide the numbers into $k$ sets, such that each set has the same sum.

For example, for $N=4$, there is one possible $2$-partition: $\{1,4\},\{2,3\}$ (since the sum of the numbers in each is $5$). For another example, with $N=7$ there are multiple possible 2-partitions, one of which is: $\{1,2,4,7\},\{3,5,6\}$ (since the sum of the numbers in each is $14$).

We can see that in order for any $N$ to have a valid $2$-partition, we need $\sum_{i=1}^N i = \frac{N(N+1)}{2}$ to be divisible by $2$, meaning $$N(N+1) \text{ divisible by 4} \Rightarrow N \text{ or } N+1 \text{ divisible by 4}$$

It isn’t too difficult to determine similar requirements on $N$ for the existence of other $k$-partitions: $$k=3: \quad N(N+1) \text{ divisible by 6} \Rightarrow N \text{ or } N+1 \text{ divisible by 3}$$ $$k=4: \quad N(N+1) \text{ divisible by 8} \Rightarrow N \text{ or } N+1 \text{ divisible by 8}$$ $$\vdots$$

It might be interesting to investigate how many $k$-partitions there are for any given $N$, but I’m more interested in the problem of imposing restrictions on the partitions (which makes it more difficult to find the $N$ for which they exist).

The problem

Let’s say we want (what I have dubbed) a consecutive $k$-partition. That is, divide the positive integers up to (and including) $N$ into $k$ sets, such that each set has the same sum and the sets are ordered, with the largest number in each set being 1 less than the smallest number in the next set. (Clearly, if there exists a consecutive $k$-partition for $N$, there is only one such partition.)

In the case $k=2$, a consecutive $2$-partition exists for $N$ if we can find an $a$ such that: $$1+2+\ldots+a = (a+1)+(a+2)+\ldots+N$$

For example, for $N=3$ there is one possible consecutive $2$-partition: $\{1,2\},\{3\}$. The next $N$ for which there exists a consecutive $2$-partition is $N=20$, where $a=14$ and we have: $$1+2+\ldots+14=105=15+16+\ldots+20$$

In general, a consecutive $2$-partition exists for $N$ if we can find an $a$ such that $$\frac{a(a+1)}{2} = \frac{N(N+1)}{2} - \frac{a(a+1)}{2},$$ which by the quadratic formula means we need $$a = \frac{\sqrt{2N^2 + 2N + 1}-1}{2}$$ to be a positive integer. Since the root term will always be odd, the top will always be divisible by $2$, so we just need $$a = 2N^2 + 2N + 1$$ to be a square number.

Interesting note: We want $a = Z^2$ for some positive integer $Z$, and we can write $a = 2N^2 + 2N + 1 = N^2 + (N+1)^2 = Z^2$, and the rightmost equation is precisely the set of Pythagorean triples $(X, X+1, Z)$.

Using this formula, the next $N$ after $3$ then $20$ seems to be $119$, then $696$, then $4059$, then $23660$. Clearly these grow farther apart, and a brute-force iteration over all the positive integers will be very slow in finding these. Is there a formula to find $N$s for which this $a$ exists? Or, as a more theoretical question: What can we know about the set of these $N$s (how are they distributed among the positive integers)?

This gets more tricky with consecutive $3$-partitions. For any $N$, we need to find a $b$ and $c$ such that $$\frac{b(b+1)}{2} = \frac{c(c+1)}{2} - \frac{b(b+1)}{2} = \frac{N(N+1)}{2} - \frac{c(c+1)}{2},$$ which means we need both of the following to be positive integers: $$b = \frac{\sqrt{12b^2 + 12b + 9} – 3}{6}$$ $$c = \frac{\sqrt{24b^2 + 24b + 9} - 3}{6}$$ Multiplying the top and bottom by $\frac{1}{3}$ and noting that the top will then always be divisible by $2$, we just need $$b = \frac{4}{3}N^2 + \frac{4}{3}N + 1$$ $$c = \frac{8}{3}N^2 + \frac{8}{3}N + 1$$ to be square numbers.

I tested the above formulas on the first $25000$ positive integers, and haven’t found any $N$s with a consecutive $3$-partition. Are there any?

Summary of the questions

  1. Is there a formula to find $N$s for which a consecutive $2$-partition exists (without needing to iterate and see if there exists an integer $a$)?
  2. Are there any $N$s for which a consecutive $3$-partition exists? What about for consecutive $4$-partitions, or $5$, etc.?
  3. For any $k$, what do we know (about the distribution among the positive integers) of the set of $N$s for which a consecutive $k$-partition exists?

I’m fascinated by this topic, and any insights you can provide (perhaps using knowledge gleaned from more advanced number theory) would be helpful!

UPDATE on question 2

For consecutive $3$-partitions, it seems like $N$s that satisfy the conditions on $b$ and $c$ can be expressed by recursive formulas: $$\text{condition on } b \Rightarrow N_{i+2} = 4N_{i+1} - N_i + 1 \text{, with } N_0=0 \text{ and } N_1 = 2$$ $$\text{condition on } c \Rightarrow N'_{i+2} = 10N'_{i+1} - N'_i + 4 \text{, with } N'_0=0 \text{ and } N'_1 = 5$$ Side question: Is there a way to prove this?

By iterating $i$, we can generate $N$s which satisfy the first condition, and $N'$s which satisfy the second condition. I have done this to generate $N$ and $N'$ all the way up to $10^{300}$, and there are none which satisfy both conditions! Does this make it very likely that no consecutive $3$-partitions exist?

These recursive formulas can also be expressed in closed form: $$N_i = \frac{1}{4} \left((1+\sqrt{3})(2+\sqrt{3})^i + (1-\sqrt{3})(2-\sqrt{3})^i - 2 \right)$$ $$N'_i = \frac{1}{4} \left((1+\frac{\sqrt{6}}{2})(5+2\sqrt{6})^i + (1-\frac{\sqrt{6}}{2})(5-2\sqrt{6})^i - 2 \right)$$ So the question becomes: $$\{N_i \mid i \in \mathbb{Z^+}\} \cap \{N'_i \mid i \in \mathbb{Z^+}\} = \emptyset?$$

share|improve this question
2  
This OEIS sequence is relevant: oeis.org/A001652 –  Matthew Conroy Dec 18 '13 at 1:17
    
@MatthewConroy That's the one! It defines my $N$ for consecutive $2$-partitions by saying $\frac{N(N+1)}{2}$ must be a product of two consecutive integers, which is true. –  jamaicanworm Dec 18 '13 at 2:15

2 Answers 2

up vote 4 down vote accepted
+200

[Edited to include the connection with Euler's theorem that there's no nonconstant $4$-term arithmetic progression of squares; briefly, since $1$ and $4(N^2+N)+1 = (2N+1)^2$ are always squares, $(1,b,c,(2N+1)^2)$ is such a $4$-term progression, so $b=c=1$ and $N^2+N=0$ for any rational solution. It seems that the same deals with all $k \geq 3$.]

The Diophantine equations $$ B^2 = b = \frac43(N^2+N) + 1 $$ $$ C^2 = c = \frac83(N^2+N) + 1 $$ have no simultaneous solution in integers other than the eight trivial solutions with $N=0,-1$, $B = \pm 1$, $C = \pm 1$. Such a result can be tricky to prove in general, but here we are somewhat lucky in that these are the only rational solutions, and moreover $N=0$ and $N=-1$ are the only rational numbers for which the product $bc$ is a square. This can be proved using Fermat's "descent" method; the calculations, though elementary, may be somewhat laborious to carry out by hand, but happily this is no longer necessary thanks to existing tables and software.

In general, if $P,Q$ are quadratic polynomials such that $PQ$ has four distinct factors then the simultaneous Diophantine equations $B^2 = P(N)$, $C^2 = Q(N)$ define an elliptic curve. A fundamental 1929 theorem of Siegel assures that such a curve has only finitely many integral points. The proof is "ineffective" and does not in general give an algorithm guaranteed to determine all solutions. Later theoretical and computational advances do provide such an algorithm, which is feasible at least for $P,Q$ with small coefficients; but the resulting proof is very far from elementary, and it can be hard to predict in any given case how hard it is to give an elementary proof.

In the present case, though, the elliptic curve already has finitely many rational points, as does the "isogenous" curve $A^2 = P(N) Q(N)$. We bring this curve $$ A^2 = \left( \frac43(N^2+N) + 1 \right) \left( \frac83(N^2+N) + 1 \right) $$ into standard Weierstrass form in the usual way starting from the rational point $(N,A) = (0,1)$: the Taylor expansion of $A$ about $N=0$ starts $1 + 2N + O(N^2)$, so for $N\neq 0$ we can write $$ A = 1 + 2N + rN^2 $$ for some rational $r$, and divide the resulting equation by $N^2$ to get $$ (9r^2-32)N^2 + (36r-64)N + (18r-32) = 0. $$ This equation is quadratic in $N$, and thus has rational roots iff its discriminant w.r.t. $N$ is a square. That discriminant factors as $-72(r-2)r(9r-16)$; taking $r=-2x/9$ and removing a factor $(8/3)^2$ we find that $$ y^2 = x (x+8) (x+9) = x^3 + 17 x^2 + 72 x $$ for some rational $x,y$. This elliptic curve turns out to have conductor $24$, so it already appears in Tingley's "Antwerp Tables" of modular elliptic curves of conductor at most $200$; it turns out to have label 24C here. We find that it has rank zero, and only four rational points, which must be the point at infinity and the three "$2$-torsion points" with $y=0$. Alternatively, we can input [0,17,0,72,0] to Cremona's program mwrank to find that the curve has rank zero, and then find its torsion points with gp. Either way, we finish by retracing our steps to find that each of $r=0,2,16/9$ corresponds to one of the known solutions with $N=0$ or $N=-1$ (in each case a double root of the quadratic in $N$), so we are done.

[Thanks to Will Jagy for calling my attention to this question.]

Added later: It turns out that this $2$-descent calculation long predates the Antwerp tables: it is essentially equivalent to Euler's proof of his theorem that there is no nonconstant $4$-term arithmetic progression of squares. (See for instance Keith Conrad's exposition, which states that Euler proved the result in 1780, answering a question "first raised by Fermat in 1640".) Indeed if $b$ and $c$ are squares then $$ 1, \ \frac43(N^2+N)+1, \ \frac83(N^2+N)+1, \ 4(N^2+N)+1 $$ is such a progression (the last term being $(2N+1)^2$, so it is constant by Euler, whence $b=c=1$ and we are done.

jamaicanworm writes in a comment that for general $k \geq 3$ the problem is whether there exists a positive integer $N$ such that $c_i := \frac{4(k-i)}{k}(N^2+N) + 1$ is a square for each $i=1,2,\ldots,k-1$. These $c_i$ form an arithmetic progression, and extending it by one term in each direction again yields the squares $c_k = 1$ and $c_0 = (2N+1)^2$. Hence we have an arithmetic progression of $k+1$ squares, and again Euler's theorem shows that even if we allow $N$ to be rational the only examples are the trivial ones with $N^2+N=0$.

share|improve this answer
    
Great! I can't say I understand most of this, but I will learn :) Can one use the same procedure to show that consecutive $k$-partitions do or do not exist for other $k>3$? –  jamaicanworm Dec 24 '13 at 17:04
1  
Some of what you don't understand is context that's not actually needed for the proof. The path from $A^2 = P(N) Q(N)$ to $y^2=x(x+8)(x+9)$ is elementary algebra. (I should have called $c$ something else to avoid confusion with $\frac83(N^2+N)+1$; sorry $-$ I might edit that at some point.) For the technique to deal with that, you can look up descent by $2$-isogeny in Silverman's The Arithmetic of Elliptic Curves $-$ you don't need all the Galois cohomology etc. though it helps to learn a bit about the group law on an elliptic curve. $$ $$ Other $k>3$, I don't know; what's the equation? –  Noam D. Elkies Dec 24 '13 at 19:29
    
I'm pretty sure the pattern is as follows: In order for a consecutive $k$-partition to exist for any $N$, we must have positive integer solutions to the system of $k-1$ equations, where each equation is $\frac{4(k-i)}{k}(N^2+N)+1=c_i^2$ ($i=1,2,\ldots,k-1$). –  jamaicanworm Dec 25 '13 at 0:08
1  
Ah, good: that makes the $c_i^2$ squares in arithmetic progression, so as soon as $k \geq 5$ it's impossible by a classical theorem of Euler (that there are no nonconstant 4-term arith.progs. of squares). Come to think of it, though, it's automatically a square for $i=0$ and $i=k$, which means that the same theorem is exactly the calculation I was farming out to the tables or mwrank, and deals with all $k \geq 3$ ! OK, let me edit my answer... –  Noam D. Elkies Dec 25 '13 at 3:13
1  
The equations $a^2+c^2=2b^2$ and $b^2+d^2=2c^2$ are equivalent to $b^2-a^2 = c^2-b^2$ and $c^2-b^2 = d^2-c^2$ respectively. Together these give $b^2-a^2 = c^2-b^2 = d^2-c^2$, which says that $a^2,b^2,c^2,d^2$ are in arithmetic progression. –  Noam D. Elkies Dec 25 '13 at 20:01

I can help you anwer the first question: This has something to do with solutions to Pell's equation. I let mathematica solve it, and it gave the following solution: $$ \frac{1}{4} \left(\sqrt{2} \left(3+2 \sqrt{2}\right)^{c_1}-\left(3+2 \sqrt{2}\right)^{c_1}-\sqrt{2} \left(3-2 \sqrt{2}\right)^{c_1}-\left(3-2 \sqrt{2}\right)^{c_1}-2\right) $$ where $c_1$ is an integer. The system of equations for question two can't be solved by mathematica, but i do not se a simple proof for that right now. Whether or not a $k$-partition exists for an integer $k$ is not an easy question, but maybe you can express a system of equations for arbitrary $k$ and show that it can't have solutions.

EDIT The command i used wasSolve[2n^2+2n+1==k^2&&n>0&&k>0,{n,k},Integers]. This way, it can solve this kind of formula's. An online solver is available here. This returns a recurrence relation to generate the consecutive values of $n$ given by the formula above. How to solve a general linear recurrence relation can be found here.

EDIT 2 I just realized the following: $3$-consecutive equal sums can only occur when the first two are equal, and thus, the largerst element of the middle sum has to be a value of $N$ which comes from the formula above and sattisfies the $2$-consecutive sum criterium. I will try to proof that $k$-consecutive sums do not exist for $k\geq 3$.

share|improve this answer
    
Thanks for the edit! What would you plug into the online solver to get this formula? –  jamaicanworm Dec 18 '13 at 14:51
1  
you can replace $n$ by $x$ and $k$ by $y$, so you get $2x^2-y^2+2x+1=0$. –  Ragnar Dec 18 '13 at 18:56
    
Ragnar has successfully answered question 1. I have posted an updated to question 2. –  jamaicanworm Dec 19 '13 at 14:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.