|
%I #17 Nov 30 2021 09:54:54
%S 1,2,4,5,9,7,15,12,18,15,28,16,36,23,31,30,51,26,59,34,50,43,75,37,77,
%T 52,72,55,102,42,112,69,90,73,106,61,141,84,109,80,159,66,169,97,119,
%U 108,187,84,185,103,155,121,218,97,193,126,179,142,248,95,262,152,185
%N a(n) = Sum_{1<=k<=n, gcd(k,n)=1} floor(n/k).
%C sum{k|n} a(k) = sum{k=1 to n} d(k), where d(k) is the number of positive divisors of k.
%C Equals A054525 * A006218 (Mobius transform of A006218). - _Gary W. Adamson_, Aug 07 2008
%H Charles R Greathouse IV, <a href="/A116477/b116477.txt">Table of n, a(n) for n = 1..10000</a>
%F 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.
%e 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.
%p 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);
%t Table[a := Select[Range[n], GCD[n, # ] == 1 &]; Sum[Floor[n/a[[i]]], {i, 1, Length[a]}], {n, 1, 60}]
%o (PARI) A116477(n) = sum(k=1,n,(gcd(k,n)==1)*floor(n/k)) \\ _Michael B. Porter_, Mar 01 2010
%o (PARI) A006218(n)=sum(k=1, sqrtint(n), n\k)*2-sqrtint(n)^2
%o 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
%Y Cf. A006218. Row sums of A122191.
%Y Cf. A054525. - _Gary W. Adamson_, Aug 07 2008
%K easy,nonn
%O 1,2
%A _Leroy Quet_, Mar 18 2006
%E More terms from _Emeric Deutsch_ and _Stefan Steinerberger_, Apr 01 2006
|
