login
a(n) = Sum_{k=1..n-1} gcd(k,n)*a(k), a(1) = 1.
2

%I #12 Jun 17 2022 14:42:44

%S 1,1,2,5,9,28,46,136,288,722,1238,4342,6818,19146,45026,111698,189506,

%T 624930,1003942,3187170,6659438,15815050,27669542,98100426,166371218,

%U 437756198,972187194,2528368182,4258122302,14644463794,23160708398

%N a(n) = Sum_{k=1..n-1} gcd(k,n)*a(k), a(1) = 1.

%H Reinhard Zumkeller, <a href="/A072979/b072979.txt">Table of n, a(n) for n = 1..1000</a>

%e a(4) = gcd(1,4)*a(1) + gcd(2,4)*a(2) + gcd(3,4)*a(3) = 1*1 + 2*1 + 1*2 = 5.

%t f[n_] := f[n] = Sum[ GCD[k, n]*f[k], {k, 1, n - 1}]; f[1] = 1; Table[ f[n], {n, 1, 31} ]

%o (Haskell)

%o a072979 n = a072979_list !! (n-1)

%o a072979_list = 1 : f 2 [1] where

%o f z xs = y : f (z + 1) (y : xs) where

%o y = sum $ zipWith (*) xs (map (gcd z) [z-1, z-2 ..])

%o -- _Reinhard Zumkeller_, Feb 13 2012

%K easy,nice,nonn

%O 1,3

%A _Paul D. Hanna_, Aug 20 2002