Consecutive partitions of positive integers

Question

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?$$

Answer 1

[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$.

Answer 2

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$.