OFFSET
1,3
COMMENTS
Smallest positive integer k such that (ceiling(sqrt(2n+1))+k-1)^2 - n is a square.
REFERENCES
Tattersall, J. "Elementary Number Theory in Nine Chapters", Cambridge University Press, 2001, pp. 102-103.
LINKS
Ridlo Wahyudi Wibowo, Table of n, a(n) for n = 1..10000
Ridlo W. Wibowo, Introducing Fermat Sequences, J. Phys.: Conf. Ser. 1245 (2019), 012048.
FORMULA
a(n) = (d+(2n+1)/d)/2 - floor(sqrt(2n)), where d is the smallest divisor of 2n+1 such that d>=sqrt(2n+1). - Max Alekseyev, Apr 13 2009
EXAMPLE
To factor 931 using Fermat's method we need four iterations: 31^2 - 931 = 30, 32^2 - 931 = 93, 33^2 - 931 = 158, 34^2 - 931 = 225 = 15^2. Hence 931 = (34 - 15)(34 + 15)=19 * 49; so a(931)=4.
MATHEMATICA
Array[(#2 + #1/#2)/2 - Floor@ Sqrt[#3] & @@ {#1, SelectFirst[Divisors[#1], Function[d, d^2 >= #1]], #2} & @@ {#, # - 1} &[2 # + 1] &, 88] (* Michael De Vlieger, Jan 11 2020 *)
PROG
(PARI) { a(n) = m=2*n+1; fordiv(m, d, if(d*d>=m, return((d+m\d)\2-sqrtint(m-1)))) } \\ Max Alekseyev, Apr 13 2009
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Jason Earls, Dec 22 2002
STATUS
approved