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$
  • 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 Oct 26 '15 at 14:05
  • $\begingroup$ I know of Fermat's factorization method. This method is different. $\endgroup$ – orgesleka Oct 26 '15 at 14:13
  • 3
    $\begingroup$ But what you are doing is equivalent to writing $8n = (2a+1)^{2}- (2b-1)^{2}$. $\endgroup$ – Geoff Robinson Oct 26 '15 at 14:22
  • 1
    $\begingroup$ What range of $n$ did you examine to estimate your 0.38 exponent? $\endgroup$ – Bill Bradley Oct 26 '15 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$ – orgesleka Nov 6 '15 at 20:11
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$
  • 1
    $\begingroup$ I should say that finding the representation without factoring n or 2n first. $\endgroup$ – orgesleka Oct 26 '15 at 14:08
  • $\begingroup$ @stackExchangeUser Did you wrote that? I didn't notice it, maybe my mistake. $\endgroup$ – joro Oct 26 '15 at 14:31
  • $\begingroup$ No I didn't write that, I thought it was clear from the context, my mistake. $\endgroup$ – orgesleka Oct 26 '15 at 15:45

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.