OFFSET
1,2
COMMENTS
sum{k|n} a(k) = sum{k=1 to n} d(k), where d(k) is the number of positive divisors of k.
LINKS
Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
FORMULA
a(n) is also Sum_{k|n} mu(n/k) (Sum_{j=1..k} d(j)) and Sum_{k=1..n} phi(n,n/k), where mu() is the Mobius (Moebius) function, d(j) is the number of positive divisors of j and phi(n,x) is the number of positive integers which are <= x and are coprime to n.
EXAMPLE
a(6)=7 because the numbers relatively prime to 6 and not exceeding 6 are 1 and 5, yielding floor(6/1) + floor(6/5) = 7.
MAPLE
a:=proc(n) local s, j: s:=0: for j from 1 to n do if gcd(j, n)=1 then s:=s+floor(n/j) else s:=s: fi od: s: end: seq(a(n), n=1..75);
MATHEMATICA
Table[a := Select[Range[n], GCD[n, # ] == 1 &]; Sum[Floor[n/a[[i]]], {i, 1, Length[a]}], {n, 1, 60}]
PROG
(PARI) A116477(n) = sum(k=1, n, (gcd(k, n)==1)*floor(n/k)) \\ Michael B. Porter, Mar 01 2010
(PARI) A006218(n)=sum(k=1, sqrtint(n), n\k)*2-sqrtint(n)^2
a(n, f=factor(n))=my(K=1, N); for(i=1, #f~, if(f[i, 2]>1, K*=f[i, 1]^(f[i, 2]-1); f[i, 2]=1)); sumdiv(N=n/K, k, moebius(N/k)*A006218(k*K)) \\ Charles R Greathouse IV, Nov 30 2021
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Leroy Quet, Mar 18 2006
EXTENSIONS
More terms from Emeric Deutsch and Stefan Steinerberger, Apr 01 2006
STATUS
approved