cp's OEIS Frontend

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.

%I A357928 #161 Oct 27 2022 07:35:06
%S A357928 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 A357928 -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 A357928 -1,23,1,24,-1,1,0,1,-1,26,10,5,-1,28,1,29,-1,2,12,1,-1,32
%N 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.
%C A357928 c exists iff n != 2 (mod 4), and it allows n to be written as the difference of two perfect squares.
%C A357928 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 A357928 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 A357928 a(n) >= 1 if n is not square and is writable as a difference of squares.
%C A357928 a(n) = 0 if n is square.
%C A357928 a(n) = -1 if n is not writable as a difference of squares.
%H A357928 Wikipedia, <a href="https://en.wikipedia.org/wiki/Fermat%27s_factorization_method">Fermat's factorization method</a>
%e A357928 n   prime  square  n == 2 (mod 4)   c   s  v=(s+c)^2-n   u   w   x   y  x*y
%e A357928 --  -----  ------  --------------  --  --  -----------  --  --  --  --  ---
%e A357928 76      F       F               F  12   8          324  20  68   2  38   76
%e A357928 13      T       F               F   4   3           36   7   6   1  13   13
%e A357928 25      F       T               F   0   0            0   5   0   5   5   25
%e A357928 7       T       F               T  -1   -            -   -   -   -   -    -
%o A357928 (Python)
%o A357928 from gmpy2 import *
%o A357928 def fermat(n):
%o A357928     a, rem = isqrt_rem(n)
%o A357928     b2 = -rem
%o A357928     c0 = (a << 1) + 1
%o A357928     c = c0
%o A357928     while not is_square(b2):
%o A357928         b2 += c
%o A357928         c += 2
%o A357928     return (c-c0) >> 1
%o A357928 def A357928(n):
%o A357928   if is_square(n):
%o A357928       return 0
%o A357928   elif ((n-2) % 4) != 0:
%o A357928       return fermat(n)
%o A357928   else:
%o A357928       return -1
%o A357928 (Python)
%o A357928 from math import isqrt
%o A357928 from itertools import takewhile
%o A357928 from sympy import divisors
%o A357928 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 A357928 (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 A357928 Cf. A177713, A037074.
%K A357928 sign
%O A357928 0,8
%A A357928 _Darío Clavijo_, Oct 20 2022