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
Keywords
Examples
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.
Links
- Giovanni Resta, Table of n, a(n) for n = 1..10000
Crossrefs
Cf. A144379. - Gary W. Adamson, Sep 19 2008
Programs
-
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 *)
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).
Extensions
Extended by Ray Chandler, Feb 03 2007
Comments