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

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?