a(n) = Sum_{k=1..n} gcd(k,n)^(n/gcd(k,n) - 1).

Terms

a(0) =1a(1) =2a(2) =3a(3) =5a(4) =5a(5) =14a(6) =7a(7) =25a(8) =25a(9) =74a(10) =11a(11) =161a(12) =13a(13) =398a(14) =383a(15) =657a(16) =17a(17) =2110a(18) =19a(19) =3341a(20) =4485a(21) =10262a(22) =23a(23) =19569a(24) =2521a(25) =49178a(26) =39547a(27) =74441a(28) =29a(29) =221462