A125728 a(n) = Sum_{k=1..n} (number of positive integers <= k which are coprime to both k and n).

1, 2, 4, 5, 10, 7, 18, 16, 23, 19, 42, 24, 58, 38, 46, 56, 96, 52, 120, 72, 93, 93, 172, 91, 171, 132, 176, 143, 270, 116, 308, 218, 237, 228, 280, 201, 432, 286, 330, 275, 530, 237, 584, 368, 394, 417, 696, 357, 666, 431, 570, 515, 882, 452, 716, 565, 712, 665

Offset

1,2

Comments

Equals row sums of triangle A144379. - Gary W. Adamson, Sep 19 2008

Links

Giovanni Resta, Table of n, a(n) for n = 1..10000

Formula

a(n) = Sum_{j=1..n} Sum_{k|(n*j)} mu(k) * floor(j/k), where mu(k) is the Mobius (Moebius) function and the inner sum is over the positive divisors, k, of (n*j).

Example

The positive integers coprime to k and <= k are, as k runs from 1 to 8, 1; 1; 1, 2; 1,3; 1,2,3,4; 1,5; 1,2,3,4,5,6; 1,3,5,7. So we want, so as to get a(8), the number of 1's, 3's, 5's and 7's in this concatenated list, since the positive integers <=8 and coprime to 8 are 1,3,5,7. In the concatenated list there are eight 1's, four 3's, three 5's and one 7. So a(8) = 8 + 4 + 3 + 1 = 16.

Mathematica

f[n_] := Sum[Sum[ Boole[GCD[j, k] == 1 && GCD[j, n] == 1], {j, k}], {k, n}]; Table[f[n], {n, 60}] (* Ray Chandler, Feb 03 2007 *)

Crossrefs

Cf. A144379. - Gary W. Adamson, Sep 19 2008

Sequence in context: A245512 A366351 A232616 * A351871 A276608 A173660

Adjacent sequences: A125725 A125726 A125727 * A125729 A125730 A125731

Keyword

nonn

Author

Leroy Quet, Feb 02 2007

Extensions

Extended by Ray Chandler, Feb 03 2007

Status

approved