This may be old news disguised by notational ignorance, but heterologous to sum over divisors, ==== \ > f(d), / ==== d | n is sum over totatives, ==== \ S(n) := > f(t) . / ==== t < n (t, n) = 1 When f is a polynomial, we can express S(n) in terms of an umbral operator on Bernoulli polynomials and two multiplicative functions: Euler's totient a a-1 phi(p ) = p (p - 1), OEIS A000010, and the unnamed(?) a k U (p ) := 1 - p , OEIS <see below>. k n - 1 ==== B (n) - B ==== \ k k + 1 k + 1 \ k k s (n) := > j = ------------------ S (n) := > t k / k + 1 k / ==== ==== j = 0 t < n (t, n) = 1 2 2 n n phi(n ) 1 -- - - ------- 2 2 2 3 2 3 n U (n) n n n phi(n ) 1 2 -- - -- + - ------- + ------- 3 2 6 3 6 2 4 3 2 4 n U (n) n n n phi(n ) 1 3 -- - -- + -- ------- + -------- 4 2 4 4 4 3 5 4 3 5 n U (n) n U (n) n n n n phi(n ) 3 1 4 -- - -- + -- - -- ------- - ------- + -------- 5 2 3 30 5 30 3 2 4 6 5 4 2 6 n U (n) 5 n U (n) n n 5 n n phi(n ) 3 1 5 -- - -- + ---- - -- ------- - -------- + ---------- 6 2 12 12 6 12 12 3 5 7 6 5 3 7 n U (n) n U (n) n U (n) n n n n n phi(n ) 5 3 1 6 -- - -- + -- - -- + -- ------- + ------- - -------- + -------- 7 2 2 6 42 7 42 6 2 2 4 6 8 7 6 4 2 8 n U (n) 7 n U (n) 7 n U (n) n n 7 n 7 n n phi(n ) 5 3 1 7 -- - -- + ---- - ---- + -- ------- + -------- - ---------- + ---------- 8 2 12 24 12 8 12 24 12 etc. All this needs proving, of course. S_1(n) is OEIS A023896. S_2(n), S_3(n), and S_4(n) are A053818 through A053820. Unsigned U_1(n) and U_3(n) are A023900 and A063453. --rwg