login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A023896 Sum of positive integers in reduced residue system modulo n. a(1) = 1 by convention. 46
1, 1, 3, 4, 10, 6, 21, 16, 27, 20, 55, 24, 78, 42, 60, 64, 136, 54, 171, 80, 126, 110, 253, 96, 250, 156, 243, 168, 406, 120, 465, 256, 330, 272, 420, 216, 666, 342, 468, 320, 820, 252, 903, 440, 540, 506, 1081, 384, 1029, 500, 816, 624, 1378, 486, 1100, 672 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

a(n) = Sum_{1<=k<=n, GCD(k,n)=1} k.

Sum of totatives of n, i.e. sum of integers up to n and coprime to n.

a(1) = 1, since 1 is coprime to any positive integer.

a(n) = n*A023022(n) for n>2.

Equals row sums of triangle A127368. [Gary W. Adamson, Aug 27 2008]

Equals row sums of triangle A144734. [Gary W. Adamson, Sep 20 2008]

Equals row sums of triangle A144824. [Gary W. Adamson, Sep 21 2008]

a(n) = A053818(n) * A175506(n) / A175505(n). For number n >= 1 holds B(n) = a(n) / A023896(n) = A175505(n) / A175506(n), where B(n) = antiharmonic mean of numbers k such that GCD(k, n) = 1 for k < n. Cf. A179871, A179872, A179873, A179874, A179875, A179876, A179877, A179878, A179879, A179880, A179882, A179883, A179884, A179885, A179886, A179887, A179890, A179891, A007645, A003627, A034934. [Jaroslav Krizek, Aug 01 2010]

REFERENCES

T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 48, problem 16, the function phi_1(n).

D. M. Burton, Elementary Number Theory, p. 171.

Tattersall, J. "Elementary Number Theory in Nine Chapters", Cambridge University Press, 2001, p. 163.

LINKS

Michael De Vlieger (First 1000 terms from T. D. Noe), Table of n, a(n) for n = 1..10000

FORMULA

a(n) = n*phi(n)/2 = A002618(n)/2 if n>1, a(1)=1.

a(n) = Sum{1 <= k < n, k for GCD(k, n) =1}.

If n = p is a prime, a(p)=T(p-1) where T(k) is the k-th triangular number (A000217). - Robert G. Wilson v, Jul 31 2004

Equals A054521 * [1,2,3,...]. - Gary W. Adamson, May 20 2007

EXAMPLE

a(12) = 1 + 5 + 7 + 11 = 24.

Reduced residue system for 40 = {1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39}.  The sum is 320.  Average is 20.

MAPLE

A023896 := proc(n)

    if n = 1 then

        1;

    else

        n*numtheory[phi](n)/2 ;

    end if;

end proc: # R. J. Mathar, Sep 26 2013

MATHEMATICA

a[ n_ ] = n/2*EulerPhi[ n ]; a[ 1 ] = 1; Table[a[n], {n, 56}]

a[ n_] := If[ n < 2, Boole[n == 1], Sum[ k Boole[1 == GCD[n, k]], { k, n}]]; (* Michael Somos, Jul 08 2014 *)

PROG

(PARI) {a(n) = if(n<2, n>0, n*eulerphi(n)/2)};

(Haskell)

a023896 = sum . a038566_row  -- Reinhard Zumkeller, Mar 04 2012

CROSSREFS

Cf. A000010, A000203, A002180, A045545, A001783, A024816, A066760, A054521, A067392, A038566.

Sequence in context: A143443 A139556 A191150 * A222136 A128488 A226303

Adjacent sequences:  A023893 A023894 A023895 * A023897 A023898 A023899

KEYWORD

nonn,easy,nice

AUTHOR

Olivier Gérard

EXTENSIONS

Typos in programs corrected by Zak Seidov, Aug 03 2010

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified October 21 11:15 EDT 2014. Contains 248377 sequences.