12
$\begingroup$

Is it possible to figure out if a number $z$ is the addition of two triangular number without recursion or finding the values to $x$ and $y$?

$$\frac{x(x+1)}{2} + \frac{y(y+1)}{2} = z$$

An example of this would be following:

$$\frac{345(345+1)}{2} + \frac{234(234+1)}{2} = 87180$$

Is it possible to determine if $87180$ originated from the addition of two triangular numbers without recursively going back and plugging every possibility for $x$ and $y$?

$\endgroup$
22
$\begingroup$

The equation: $$ x(x+1)+y(y+1)=2z \tag{1}$$ is equivalent to: $$ (2x+1)^2 + (2y+1)^2 = 8z+2 \tag{2} $$ hence $z$ is the sum of two triangular numbers iff $8z+2$ is the sum of two squares, i.e. iff for every prime $p$ of the form $4k+3$ that divides $8z+2$, $\nu_p(8z+2)$ is even.

In the given example, $z=87180$, we have:

$$ 8z+2 = 2\cdot 17 \cdot 73\cdot 281 \tag{3}$$ and every odd prime occurring in the RHS of $(3)$ is of the form $4k+1$, hence $8z+2$ can be written as the sum of two odd squares: $$ 8z+2 = 101^2 + 829^2 \tag{4}$$ and $z$ is the sum of two triangular numbers: $$ 87180 = \binom{51}{2}+\binom{415}{2}.\tag{5} $$

$\endgroup$
  • $\begingroup$ @FelipeFaria: I have just expanded my answer dealing with your example. Hope it is more clear now. $\endgroup$ – Jack D'Aurizio Feb 25 '15 at 13:53
  • 1
    $\begingroup$ Perhaps the more interesting question is whether this can be done without factoring $8z+2$. $\endgroup$ – lhf Feb 25 '15 at 13:55
  • 1
    $\begingroup$ Indeed it is! Thank you. $\endgroup$ – Felipe Faria Feb 25 '15 at 13:56
  • 1
    $\begingroup$ what is $\nu_p$? $\endgroup$ – MichaelChirico Feb 25 '15 at 16:10
  • 2
    $\begingroup$ @MichaelChirico: the $p$-adic height, i.e. $$\nu_p(n)=\max\left\{m\in\mathbb{N}: p^m\mid n\right\}.$$ $\endgroup$ – Jack D'Aurizio Feb 25 '15 at 17:35
1
$\begingroup$

If we had $a(k)$ from A008441 the test for $z$ would be $$ a(z) > 0 . $$

The information section on this series provides many interesting relations.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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