|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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.
|
|
REFERENCES
|
H. Davenport, The Higher Arithmetics, 7th ed. 1999, Cambridge University Press, pp. 32-35.
|
|
LINKS
|
|
|
FORMULA
|
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|