A357928 a(n) is the smallest c for which (s+c)^2-n is a square, where s = floor(sqrt(n)), or -1 if no such c exists.

0, 0, -1, 1, 0, 1, -1, 2, 1, 0, -1, 3, 1, 4, -1, 1, 0, 5, -1, 6, 2, 1, -1, 8, 1, 0, -1, 1, 3, 10, -1, 11, 1, 2, -1, 1, 0, 13, -1, 2, 1, 15, -1, 16, 6, 1, -1, 18, 1, 0, -1, 3, 7, 20, -1, 1, 2, 4, -1, 23, 1, 24, -1, 1, 0, 1, -1, 26, 10, 5, -1, 28, 1, 29, -1, 2, 12, 1, -1, 32

Offset

0,8

Comments

c exists iff n != 2 (mod 4), and it allows n to be written as the difference of two perfect squares.

This gives a factorization n = x*y where x and y may or may not be primes: let s = floor(sqrt(n)), u = a(n) + s and v = u^2 - n; then w = sqrt(v), x = u - w, y = u + w and x*y == n.

The Fermat factorization algorithm seeks such a form, starting from s, so that a(n) is the number of steps it must take for n != 2 (mod 4).

a(n) >= 1 if n is not square and is writable as a difference of squares.

a(n) = 0 if n is square.

a(n) = -1 if n is not writable as a difference of squares.

Links

Table of n, a(n) for n=0..79.

Wikipedia, Fermat's factorization method

Example

n   prime  square  n == 2 (mod 4)   c   s  v=(s+c)^2-n   u   w   x   y  x*y
--  -----  ------  --------------  --  --  -----------  --  --  --  --  ---
76      F       F               F  12   8          324  20  68   2  38   76
13      T       F               F   4   3           36   7   6   1  13   13
25      F       T               F   0   0            0   5   0   5   5   25
7       T       F               T  -1   -            -   -   -   -   -    -

Prog

(Python)
from gmpy2 import *
def fermat(n):
    a, rem = isqrt_rem(n)
    b2 = -rem
    c0 = (a << 1) + 1
    c = c0
    while not is_square(b2):
        b2 += c
        c += 2
    return (c-c0) >> 1
def A357928(n):
  if is_square(n):
      return 0
  elif ((n-2) % 4) != 0:
      return fermat(n)
  else:
      return -1
(Python)
from math import isqrt
from itertools import takewhile
from sympy import divisors
def A357928(n): return -1 if n&3==2 else min((m>>1 for d in takewhile(lambda d:d**2<=n, divisors(n)) if not((m:=n//d+d) & 1)), default=0) - isqrt(n) # Chai Wah Wu, Oct 26 2022
(PARI) a(n) = if ((n%4)==2, -1, my(s=sqrtint(n), c=0); while (!issquare((s+c)^2-n), c++); c); \\ Michel Marcus, Oct 24 2022

Crossrefs

Cf. A177713, A037074.

Sequence in context: A257261 A355141 A171963 * A292131 A255740 A100995

Adjacent sequences: A357925 A357926 A357927 * A357929 A357930 A357931

Keyword

sign

Author

Darío Clavijo, Oct 20 2022

Status

approved