A195508 Number of iterations in a Draim factorization of 2n+1.

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

Author

Frank Ellermann, Sep 19 2011

Keywords

• nonn
• easy

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]

Examples

			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.
		

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

Crossrefs

Cf. A090368.

Programs

Mathematica

a[n_] := Module[{m = 1}, While[GCD[n + m + 1, n - m] == 1, m++]; m]; Array[a, 100] (* Amiram Eldar, Nov 06 2019 *)

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

Formula

a(n) = (A090368(n+1)-1)/2.