2
$\begingroup$

Since $n = \frac{n(n+1)}{2}-\frac{n(n-1)}{2}$, every natural number can be represented as the difference of two triangular numbers: $ n = \frac{a(a+1)}{2}-\frac{b(b-1)}{2}$. Finding such a representation gives a factorization of $n = \frac{(a+b)\cdot(a-b+1)}{2}$. A naive way of finding such representations would be to set

$x = floor(0.5+\sqrt{0.25+2n})$

while True:
  x = x+1
  set y = x(x+1)/2 -n
  if issquare(8*y+1):
      b = (1+sqrt(8*y+1))/2
      if x-b+1 = 0 (mod 2):
         return (x-b+1)/2,x+b
      else:
         return x-b+1,(x+b)/2

Although to me unclear why this algorithm should terminate, I have implemented it in python and the running time for $n=p\cdot q$ with two unequal primes $p$ and $q$ seems to be $n^{0.38} < n^{0.5} = \sqrt{n}$, which seems to be better than trial division. It is known, that one can find very fast a representation of $n$ as a sum of three triangular numbers by first finding a representation of $8n+3$ as a sum of three squares using the algorithm of Shallit and Rabin. So in essence I have two questions:

1) Does anybody know a reason why the above naive algorithm should terminate.

2) Does anybody know of a faster way to find such (nontrivial) representation of $n$ without factoring $n$ first?

$\endgroup$
8
  • 1
    $\begingroup$ This is just a minor variant of Fermat's method, but using triangular numbers instead of squares: en.wikipedia.org/wiki/Fermat%27s_factorization_method $\endgroup$
    – S. Carnahan
    Commented Oct 26, 2015 at 14:05
  • $\begingroup$ I know of Fermat's factorization method. This method is different. $\endgroup$
    – user6671
    Commented Oct 26, 2015 at 14:13
  • 3
    $\begingroup$ But what you are doing is equivalent to writing $8n = (2a+1)^{2}- (2b-1)^{2}$. $\endgroup$ Commented Oct 26, 2015 at 14:22
  • 1
    $\begingroup$ What range of $n$ did you examine to estimate your 0.38 exponent? $\endgroup$ Commented Oct 26, 2015 at 14:33
  • 1
    $\begingroup$ Every method to factor an uneven number is equivalent to Fermat's method: $2n+1=d\cdot e = ((d+e)/2)^2-((d-e)/2)^2$ $\endgroup$
    – user6671
    Commented Nov 6, 2015 at 20:11

3 Answers 3

3
$\begingroup$

The representations of this type correspond one-for-one to odd divisors of $n$. So your request for a method for constructing such a representation without factoring seems to be hopeless: if you have a method for constructing such a representation it is automatically a method for factoring. See Wikipedia: Polite number.

$\endgroup$
1
$\begingroup$

There is a quick way to find solutions even without (completely) factoring. In particular, write $2n = 2^{\alpha} m$, where $m$ is odd and use the factorization $2n = m \cdot 2^{\alpha}$ to find $a$ and $b$. This gives $$ a = \frac{2^{\alpha} + m - 1}{2}, \quad b = \frac{|2^{\alpha} - m| + 1}{2}, $$ which always results in a non-trivial solution unless $n$ is a power of $2$ (in which case it is well-known that there is no representation of $n$ as the sum of a set of consecutive integers of size $> 1$).

$\endgroup$
0
$\begingroup$

For 2) it is possible to get subexponential time.

If $n$ is prime there are few representations.

So you want $2n=(a+b)(a-b+1)$ in nontrivial way.

Factor $2n$ in subexponential time and for all divisors $d$ of $2n$, write $2n=dd'$.

Solve $a+b=2d,a+b-1=d'$ to get $$a=d-1/2+d'/2,b=d+1/2-d'/2$$.

In case $a,b$ are integers, you have found representation.

I wouldn't expect your approach to give efficient factoring algorithm.

$\endgroup$
3
  • 1
    $\begingroup$ I should say that finding the representation without factoring n or 2n first. $\endgroup$
    – user6671
    Commented Oct 26, 2015 at 14:08
  • $\begingroup$ @stackExchangeUser Did you wrote that? I didn't notice it, maybe my mistake. $\endgroup$
    – joro
    Commented Oct 26, 2015 at 14:31
  • $\begingroup$ No I didn't write that, I thought it was clear from the context, my mistake. $\endgroup$
    – user6671
    Commented Oct 26, 2015 at 15:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.