A074639 a(n)=Sum_h (hh'-1)/n with h and h' in [1,n], (h,n)=1, hh'=1 (mod n).

0, 0, 0, 1, 2, 5, 4, 11, 10, 15, 12, 31, 16, 39, 28, 36, 34, 75, 32, 91, 52, 64, 60, 145, 64, 115, 88, 141, 84, 225, 76, 241, 146, 160, 152, 250, 104, 319, 204, 272, 172, 419, 152, 447, 280, 286, 228, 599, 208, 501, 252, 440, 348, 727

Offset

0,5

Comments

For a given n a(n) is the sum for h ranging over the set of least nonnegative residues coprimes with n of (hh'-1)/n, where h' is the (unique) number in the same set such that hh'=1 (mod n).

The summand is also the least nonnegative residue of (-1/n) mod h. - Robert Israel, May 18 2014

Links

Robert Israel, Table of n, a(n) for n = 0..10000

M. Dondi, Plot of A074639(n)/phi(n) (Euler's totient function) against the line y=x/4 in the range [0,100].

M. Dondi, Plot of A074639(n)/phi(n) (Euler's totient function) against the line y=x/4 in the range [0,1000].

M. Dondi, Plot of A074639(n)/phi(n) (Euler's totient function) against the line y=x/4 in the range [0,10000].

M. Dondi, Plot of A074639(n)/phi(n) (Euler's totient function) against the line y=x/4 in the range [0,10000] showing only one point out of every 5.

Example

(1,n)=1 for all n, 1*1=1, so 1 contributes 0 to the sum. (n-1,n)=1 for all n, (n-1)^2=1 (mod n), so n-1 contributes n-2. Thus a(6)=4, in fact only 1 and 5 are coprime with 6 in {1,...,6}; a(5)=2*1+(5-2), in fact 2*3=6=1 (mod 5) and 6=5+1.

Maple

seq(add((i*(i^(-1) mod m)-1)/m, i = select(t -> igcd(t, m)=1, [$1..m-1])), m=0..100); # Robert Israel, May 18 2014

Crossrefs

Cf. A074640-A074644.

Sequence in context: A326002 A072403 A010078 * A319525 A357983 A338459

Adjacent sequences: A074636 A074637 A074638 * A074640 A074641 A074642

Keyword

nonn

Author

Michele Dondi (bik.mido(AT)tiscalinet.it), Sep 12 2002

Status

approved