cp's OEIS Frontend

A067439 a(n) = sum of all the remainders when n is divided by positive integers less than and coprime to n.

%I A067439 #23 May 19 2025 16:21:48
%S A067439 0,0,1,1,4,1,8,6,9,5,22,8,28,15,19,20,51,20,64,30,39,33,98,33,83,56,
%T A067439 89,55,151,46,167,95,107,95,150,71,233,120,172,106,297,92,325,163,186,
%U A067439 162,403,144,358,189,279,217,505,173,375,230,342,276,635,165,645,338
%N A067439 a(n) = sum of all the remainders when n is divided by positive integers less than and coprime to n.
%H A067439 Charles R Greathouse IV, <a href="/A067439/b067439.txt">Table of n, a(n) for n = 1..10000</a>
%F A067439 From _Ridouane Oudra_, May 14 2025: (Start)
%F A067439 a(n) = A004125(n) - A072514(n).
%F A067439 a(n) = Sum_{d|n} d*mu(d)*A004125(n/d).
%F A067439 a(n) = Sum_{d|n} mu(d)*f(n,d), where f(n,d) = Sum_{i=1..n/d} (n mod d*i).
%F A067439 a(p) = A004125(p), for p prime.
%F A067439 a(p^k) = A004125(p^k) - p*A004125(p^(k-1)), for p prime and k >= 0.
%F A067439 a(p^k) = A072514(p^(k+1))/p - A072514(p^k), for p prime and k >= 0. (End)
%e A067439 a(8) = 6. The remainders when 8 is divided by the coprime numbers 1, 3, 5 and 7 are 0, 2, 3 and 1, whose sum = 6.
%p A067439 a := n -> add(ifelse(igcd(n, i) = 1, irem(n, i), 0), i = 1..n-1):
%p A067439 seq(a(n), n = 1..62);  # _Peter Luschny_, May 14 2025
%t A067439 a[n_] := Sum[If[GCD[i, n]>1, 0, Mod[n, i]], {i, 1, n-1}]
%t A067439 Table[Total[Mod[n,#]&/@Select[Range[n-1],CoprimeQ[#,n]&]],{n,70}] (* _Harvey P. Dale_, May 22 2012 *)
%o A067439 (PARI) a(n)=sum(i=1,n-1,if(gcd(n,i)==1,n%i)) \\ _Charles R Greathouse IV_, Jul 17 2012
%Y A067439 Cf. A004125, A067435, A067436, A024934, A033955, A111490.
%Y A067439 Cf. A072514, A008683.
%K A067439 nonn
%O A067439 1,5
%A A067439 _Amarnath Murthy_, Jan 29 2002
%E A067439 Edited by _Dean Hickerson_, Feb 15 2002