4
$\begingroup$

An unrelated problem I came across in the domain of computer science reduced to the following mathematical problem:

For a given number $ n\in \mathbb{N} $, I need to find if any multiple of that number can be expressed as a series of the first $x$ natural numbers. Further, if such multiples exist, I need to find the least such multiple.

That is, for a given $n$, I need the lowest values for $k, x$ that satisfy the equation:

$$ n \times k = \frac{x\times \left(x+1 \right)}{2}, n\in \mathbb{N}, k\in \mathbb{N}, x\in \mathbb{N} $$

I understand that this is a diophantine equation, and while I could find ways to solve linear and quadratic diophantine equations, I could not find a general form that could be applied to the problem above, especially since there are two unknowns in the equation.

I also considered that one way to solve the problem would be to try and factorize $2 \times n$ into two consecutive numbers as indicated by the rearranged equation:

$$ k = \frac{x\times \left(x+1 \right)}{2 \times n}, n\in \mathbb{N}, k\in \mathbb{N}, x\in \mathbb{N} $$

Finally, since the problem originated in the context of computer programs, I figured that if I couldn't find a mathematical approach to solve this equation, I could simply try for all values of x till I found an appropriate value. The problem with that approach (apart from the less than ideal computational time needed) is that I do not know if the $n$ I'm solving this for has such a multiple or not, hence I have no way of knowing if the brute-force algorithm would terminate.

So I also tried (unsuccessfully) to find a method to determine if such a value for $k, x$ exists for a given $n$. Does such a method exist?

I would appreciate any help in trying to solve this problem.

$\endgroup$
4
  • 2
    $\begingroup$ If $n$ is an integer, then $T_{2n}=1+2+\cdots +2n=n\times (2n+1)$ so $(2n+1)$ is a trivial bound on your solution for $k$. $\endgroup$
    – lulu
    Apr 18, 2020 at 12:13
  • $\begingroup$ If $n$ is odd, a solution is given by $k=(n-1)/2$ and $x=n-1$. $\endgroup$
    – user289143
    Apr 18, 2020 at 12:20
  • $\begingroup$ Is there any use to the fact that $8nk+1=(2x+1)^2$? $\endgroup$
    – Empy2
    Apr 18, 2020 at 13:33
  • $\begingroup$ See also oeis.org/A011772 $\endgroup$
    – lhf
    Apr 18, 2020 at 13:38

1 Answer 1

3
$\begingroup$

The question whether such $x$ always exists has already been answered in the comments: $x=2n$ is a solution.

To find possible smaller solutions, you can proceed as follows. Let $2n=\prod_{k=1}^mp_k^{\alpha_k}$ be the prime factorization of $2n$, with $m$ distinct prime factors. Each prime power $p_k^{\alpha_k}$ must divide either $x$ or $x+1$ (since they cannot both be divisible by $p_k$). Thus there are $2^m$ different possibilities for splitting up the prime powers among $x$ and $x+1$. Let $r$ and $s$ be the products of the prime powers that divide $x$ and $x+1$, respectively. Then $x\equiv0\bmod r$ and $x\equiv-1\bmod s$. By the Chinese remainder theorem there is exactly one value $x$ with $1\le x\le rs=2n$ that satisfies these two congruences. It can be efficiently computed. So you just need to compute $2^m$ such values and take the lowest one.

Some examples:

For $n=5$, we have $2n=10=2^1\cdot5^1$, so there are $2^2=4$ ways to split up the two prime powers. Putting them all in $x$ yields $x=10$, putting them all in $x+1$ yields $x=9$, putting the $2$ in $x$ and the $5$ in $x+1$ yields $x=4$ and putting the $5$ in $x$ and the $2$ in $x+1$ yields $x=5$. These are indeed the four triangular numbers up to $x=10$ that are divisible by $5$, with the smallest at $x=4$.

For $n=18$, we have $2n=36=2^2\cdot3^2$, so again $2^2=4$ cases to try. Putting all factors in $x$ yields $x=36$, putting all factors in $x+1$ yields $x=35$, putting the $2$s in $x$ and the $3$s in $x+1$ yields $x\equiv0\bmod4$ and $x\equiv-1\bmod9$, with solution $x=8$, and putting the $3$s in $x$ and the $2$s in $x+1$ yields $x\equiv0\bmod9$ and $x\equiv-1\bmod4$, with solution $x=27$. These are indeed the four triangular numbers up to $x=36$ that are divisible by $18$, with the smallest at $x=8$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .