A099427 a(1) = 1; for n > 1, a(n) = 1 + greatest common divisor of n and a(n-1).

1, 2, 2, 3, 2, 3, 2, 3, 4, 3, 2, 3, 2, 3, 4, 5, 2, 3, 2, 3, 4, 3, 2, 3, 2, 3, 4, 5, 2, 3, 2, 3, 4, 3, 2, 3, 2, 3, 4, 5, 2, 3, 2, 3, 4, 3, 2, 3, 2, 3, 4, 5, 2, 3, 2, 3, 4, 3, 2, 3, 2, 3, 4, 5, 6, 7, 2, 3, 4, 3, 2, 3, 2, 3, 4, 5, 2, 3, 2, 3, 4, 3, 2, 3, 2, 3, 4, 5, 2, 3, 2, 3, 4, 3, 2, 3, 2, 3, 4, 5, 2, 3, 2, 3, 4

Offset: 1

Author

Gaetan Polard (gaetan27(AT)hotmail.com), Nov 18 2004

Keywords

• easy
• nonn
• nice

Comments

a(A060401(n)) = n + 1; a(A192489(n)) = 2. - Reinhard Zumkeller, Jul 02 2011

For n >= 3, a(n) == n+1 (mod 2). - Robert Israel, Jan 10 2017

Examples

			a(9)=4 because 1+gcd(a(8),9)=1+gcd(3,9)=1+3.
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Crossrefs

For position of first occurrence of n see A060401.

Programs

Haskell

a099427 n = a099427_list !! (n-1)
a099427_list = 1 : map (+ 1) (zipWith gcd [2..] a099427_list)
-- Reinhard Zumkeller, Jun 23 2015, Jul 02 2011

Maple

f:= proc(n) option remember; 1 + igcd(n,procname(n-1)) end proc:
f(1):= 1:
map(f, [$1..1000]); # Robert Israel, Jan 10 2017

Mathematica

a[1] = 1; a[n_] := a[n] = GCD[n, a[n - 1]] + 1; Table[ a[n], {n, 105}] (* Robert G. Wilson v, Nov 18 2004 *)
nxt[{n_,a_}]:={n+1,GCD[n+1,a]+1}; Transpose[NestList[nxt,{1,1},110]] [[2]] (* Harvey P. Dale, Nov 22 2014 *)

Extensions

Edited and extended by Robert G. Wilson v, Nov 18 2004