A174088 Number of pairs (i,j) such that i*j == 0 (mod k), 0 <= i <= j < k.

1, 2, 3, 5, 5, 8, 7, 11, 12, 14, 11, 21, 13, 20, 23, 26, 17, 33, 19, 37, 33, 32, 23, 51, 35, 38, 42, 53, 29, 68, 31, 58, 53, 50, 59, 87, 37, 56, 63, 91, 41, 98, 43, 85, 96, 68, 47, 122, 70, 100, 83, 101, 53, 123, 95, 131, 93, 86, 59, 181, 61, 92, 138, 132, 113, 158, 67, 133, 113

Offset: 1

Author

Russell Easterly, Mar 06 2010

Keywords

• nonn

Comments

a(p) = p for p prime, since gcd(k,p) = 1 for 1 <= k < p, the product of k is also coprime to p, but multiples n*p for n >= 1 are plainly divisible by p. - Michael De Vlieger, Nov 22 2019

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Michael De Vlieger)

Crossrefs

Cf. A000188, A018804.

Programs

Mathematica

Table[If[PrimeQ@ b, b, Count[Flatten@ Array[# Range@ # &, b], ?(Mod[#, b] == 0 &)]], {b, 69}]  (* _Michael De Vlieger, Nov 22 2019 *)
f1[p_, e_] := (e*(p - 1)/p + 1)*p^e; f2[p_, e_] := p^Floor[e/2]; a[n_] := (Times @@ f1 @@@ (fct = FactorInteger[n]) + Times @@ f2 @@@ fct)/2; Array[a, 100] (* Amiram Eldar, Apr 28 2023 *)

PARI

a(n)={ my(ct=0); for(i=0,n-1,for(j=0,i, ct+=(Mod(i*j,n)==0) ) ); ct; } \\ Joerg Arndt, Aug 03 2013

Formula

a(n) = ( A018804(n) + A000188(n) ) / 2. - Max Alekseyev, Sep 05 2010

Extensions

More terms from Max Alekseyev, Sep 05 2010

Better name from Joerg Arndt, Aug 03 2013