login
A195508
Number of iterations in a Draim factorization of 2n+1.
3
1, 2, 3, 1, 5, 6, 1, 8, 9, 1, 11, 2, 1, 14, 15, 1, 2, 18, 1, 20, 21, 1, 23, 3, 1, 26, 2, 1, 29, 30, 1, 2, 33, 1, 35, 36, 1, 3, 39, 1, 41, 2, 1, 44, 3, 1, 2, 48, 1, 50, 51, 1, 53, 54, 1, 56, 2, 1, 3, 5, 1, 2, 63, 1, 65, 3, 1, 68, 69, 1, 5, 2, 1, 74, 75, 1, 2, 78, 1, 3, 81, 1, 83, 6, 1, 86, 2, 1, 89, 90, 1, 2, 5, 1, 95, 96, 1, 98, 99
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
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
Cf. A090368.
Sequence in context: A355618 A238122 A214059 * A049274 A339470 A130508
KEYWORD
nonn,easy
AUTHOR
Frank Ellermann, Sep 19 2011
STATUS
approved