|
%I #20 Jan 11 2020 20:47:24
%S 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,
%T 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,
%U 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
%N Number of steps to factor 2n+1 using Fermat's factorization method.
%C Smallest positive integer k such that (ceiling(sqrt(2n+1))+k-1)^2 - n is a square.
%D Tattersall, J. "Elementary Number Theory in Nine Chapters", Cambridge University Press, 2001, pp. 102-103.
%H Ridlo Wahyudi Wibowo, <a href="/A078753/b078753.txt">Table of n, a(n) for n = 1..10000</a>
%H Ridlo W. Wibowo, <a href="https://doi.org/10.1088/1742-6596/1245/1/012048">Introducing Fermat Sequences</a>, J. Phys.: Conf. Ser. 1245 (2019), 012048.
%F 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
%e 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.
%t 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 *)
%o (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
%K easy,nonn
%O 1,3
%A _Jason Earls_, Dec 22 2002
|
