A357928 - OEIS

%I #161 Oct 27 2022 07:35:06

%S 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,

%T -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,

%U -1,23,1,24,-1,1,0,1,-1,26,10,5,-1,28,1,29,-1,2,12,1,-1,32

%N 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.

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

%C 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.

%C 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).

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

%C a(n) = 0 if n is square.

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

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Fermat%27s_factorization_method">Fermat's factorization method</a>

%e n   prime  square  n == 2 (mod 4)   c   s  v=(s+c)^2-n   u   w   x   y  x*y

%e --  -----  ------  --------------  --  --  -----------  --  --  --  --  ---

%e 76      F       F               F  12   8          324  20  68   2  38   76

%e 13      T       F               F   4   3           36   7   6   1  13   13

%e 25      F       T               F   0   0            0   5   0   5   5   25

%e 7       T       F               T  -1   -            -   -   -   -   -    -

%o (Python)

%o from gmpy2 import *

%o def fermat(n):

%o     a, rem = isqrt_rem(n)

%o     b2 = -rem

%o     c0 = (a << 1) + 1

%o     c = c0

%o     while not is_square(b2):

%o         b2 += c

%o         c += 2

%o     return (c-c0) >> 1

%o def A357928(n):

%o   if is_square(n):

%o       return 0

%o   elif ((n-2) % 4) != 0:

%o       return fermat(n)

%o   else:

%o       return -1

%o (Python)

%o from math import isqrt

%o from itertools import takewhile

%o from sympy import divisors

%o 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

%o (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

%Y Cf. A177713, A037074.

%K sign

%O 0,8

%A _Darío Clavijo_, Oct 20 2022