A056144 a(1) = 1, a(m+1) = Sum_{k=1..m} gcd(m, a(k)).

1, 1, 2, 3, 5, 9, 11, 7, 9, 27, 15, 21, 25, 13, 27, 49, 17, 33, 59, 19, 33, 69, 53, 45, 47, 61, 39, 117, 47, 29, 89, 31, 33, 161, 51, 75, 105, 37, 57, 159, 65, 41, 135, 43, 85, 251, 91, 139, 89, 127, 127, 171, 113, 157, 199, 131, 93, 227, 87, 117, 185, 121, 123, 227, 65

Offset: 1

Author

Leroy Quet, Aug 04 2000

Keywords

• easy
• nonn

Comments

From Ivan Neretin, Apr 06 2016: (Start)

a(n) >= n-1.

All terms except a(3) = 2 are odd.

For all n of the form 2^k+1 except 3, a(n) = n.

(End)

Examples

			a(7) = gcd(6,1) + gcd(6,1) + gcd(6,2) + gcd(6,3) + gcd(6,5) + gcd(6,9) = 1 + 1 + 2 + 3 + 1 + 3 = 11.
		

Links

• Ivan Neretin, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A093820.

Programs

Maple

a:= proc(n) option remember;
      1+add(igcd(n-1, a(j)), j=2..n-1)
    end:
seq(a(n), n=1..65);  # Alois P. Heinz, Mar 06 2025

Mathematica

Fold[Append[#1, Total@GCD[#1, #2]] &, {1}, Range@64] (* Ivan Neretin, Apr 06 2016 *)