OFFSET
1,2
COMMENTS
A Draim factorization determines the smallest divisor d of 2n+1 with simple operations (integer division, remainder, +, -, *) and needs a(n)=(d-1)/2 steps.
Least m>0 for which gcd(n+1+m, n-m) > 1. [Clark Kimberling, Jul 18 2012]
REFERENCES
H. Davenport, The Higher Arithmetics, 7th ed. 1999, Cambridge University Press, pp. 32-35.
LINKS
Amiram Eldar, Table of n, a(n) for n = 1..10000
FORMULA
a(n) = (A090368(n+1)-1)/2.
EXAMPLE
a(12)=2 because the Draim algorithm needs 2 steps to find the smallest divisor of 25=2*12+1; any a(n)=2 indicates a smallest divisor 5 of 2n+1.
MATHEMATICA
a[n_] := Module[{m = 1}, While[GCD[n + m + 1, n - m] == 1, m++]; m]; Array[a, 100] (* Amiram Eldar, Nov 06 2019 *)
PROG
(Rexx)
SEQ = '' ; do N = 1 to 50 ; X = 2 * N + 1 ; M = X
do Y = 3 by 2 until R = 0
Q = X % Y ; R = X // Y ; M = M - 2 * Q ; X = M + R
end Y ; SEQ = SEQ (( Y - 1 ) / 2 ) ; end N ; say SEQ
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Frank Ellermann, Sep 19 2011
STATUS
approved