A135324 a(n) = Sum_{k=1..phi(n)} k*t(k), where t(k) is the k-th positive integer which is coprime to n and phi(n) is the number of positive integers which are <= n and are coprime to n.

1, 1, 5, 7, 30, 11, 91, 50, 120, 64, 385, 76, 650, 191, 354, 372, 1496, 243, 2109, 468, 1081, 795, 3795, 560, 3450, 1336, 3033, 1432, 7714, 692, 9455, 2856, 4595, 3056, 6974, 1836, 16206, 4299, 7766, 3576, 22140, 2126, 25585, 6100, 8922, 7711, 33511

Offset

1,3

Links

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Jamie Morken, Lean proof of the formula, ZIP archive on Google Drive, Apr 12 2026

Formula

a(n) = Sum_{k=1..A000010(n)} k*A126572(n,k). - R. J. Mathar, Jan 30 2008

a(n) = (A000010(n) / 12) * ( n * (4 * A000010(n) + 3) + A097945(A007947(n)) - A000005(A007947(n)) / 2 ) for n > 1. - Jamie Morken, Apr 08 2026

Example

The positive integers that are coprime to 12 and are <= 12 are 1,5,7,11. So a(12) = 1*1 + 2*5 + 3*7 + 4*11 = 1+10+21+44 = 76.

Maple

A126572 := proc(n, k) local a, i ; a := 1 ; for i from 1 to k do if i = k then RETURN(a) ; fi ; a := a+1 ; while gcd(a, n) <> 1 do a := a+1 ; od; od: end: A135324 := proc(n) add( k*A126572(n, k), k=1..numtheory[phi](n)) ; end: for n from 1 to 80 do printf("%d, ", A135324(n) ) ; od: # R. J. Mathar, Jan 30 2008

Mathematica

Table[Total@ MapIndexed[First[#2]*#1 &, Select[Range[n], CoprimeQ[#, n] &]], {n, 47}] (* Michael De Vlieger, Apr 08 2026 *)
(* Alternative: using Morken's Lean formula *)
{1}~Join~Table[(#1/12)*(n*(4*#1 + 3) + (EulerPhi[#2]*MoebiusMu[#2]) - DivisorSigma[0, #2]/2) & @@ {EulerPhi[n], Times @@ FactorInteger[n][[All, 1]]}, {n, 2, 47}] (* Michael De Vlieger, Apr 11 2026 *)

Prog

(PARI) apply( {A135324(n)=(A097945(A007947(n))-numdiv(A007947(n))/2+n*(3+4*n=eulerphi(n)))*n\/12}, [1..99]) \\ Using Morken's formula proved by Lean. - M. F. Hasler, Apr 11 2026
(Python)
from math import prod
from sympy import factorint
def A135324(n): # based on Morken's Lean formula
    if n == 1: return 1
    f = factorint(n).items()
    l = len(f)
    a = prod(p-1 for p, e in f)
    b = prod(p**(e-1) for p, e in f)
    return a*b*(a*((b*n<<2)+(-1 if l&1 else 1))+3*n-(1<<l-1))//12 # Chai Wah Wu, May 27 2026

Crossrefs

Cf. A126572, A000010 (phi), A007947 (radical), A001221 (omega), A097945 (mu*phi).

Sequence in context: A153411 A081630 A307532 * A107639 A069688 A158323

Adjacent sequences: A135321 A135322 A135323 * A135325 A135326 A135327

Keyword

nonn

Author

Leroy Quet, Dec 06 2007

Extensions

More terms from R. J. Mathar, Jan 30 2008

Status

approved