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
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 (list; graph; refs; listen; history; text; internal format)
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

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.

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

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 April 18 08:37 EDT 2019. Contains 322209 sequences. (Running on oeis4.)