A078753 Number of steps to factor 2n+1 using Fermat's factorization method.

1, 1, 2, 1, 3, 4, 1, 5, 6, 1, 8, 1, 1, 10, 11, 2, 1, 13, 2, 15, 16, 1, 18, 1, 3, 20, 1, 4, 23, 24, 1, 1, 26, 5, 28, 29, 2, 1, 32, 1, 33, 2, 7, 36, 1, 8, 3, 40, 1, 41, 42, 1, 44, 45, 10, 47, 4, 1, 2, 1, 11, 4, 53, 12, 55, 2, 1, 58, 59, 14, 1, 5, 2, 63, 64, 1, 6, 67, 16, 3, 70, 1, 72, 1, 1, 74, 3, 18

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

Sequence in context: A063804 A213800 A224823 * A119443 A209413 A126198

Adjacent sequences: A078750 A078751 A078752 * A078754 A078755 A078756

Keyword

easy,nonn

Author

Jason Earls, Dec 22 2002

Status

approved