login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A078753 Number of steps to factor 2n+1 using Fermat's factorization method. 3

%I

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

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

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 22 18:53 EDT 2019. Contains 323481 sequences. (Running on oeis4.)