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,2

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)

Formula

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

From Ali Sada, May 06 2026: (Start)

a(p^2) = p^2 + A000217(p-1), p prime.

a(p1*p2) = 2*p1*p2 - p1 - p2 + 1 where p1 and p2 are two distinct primes. (End)

Mathematica

Table[If[PrimeQ@ b, b, Count[Flatten@ Array[# Range@ # &, b], _?(Mod[#, b] == 0 &)]], {b, 69}] (* Michael De Vlieger, Nov 22 2019 *)
(* Alternative: *)
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 *)

Prog

(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
(Python)
from math import prod
from sympy import factorint
def A174088(n):
    f = factorint(n).items()
    return prod(p**(e-1)*((p-1)*e+p) for p, e in f)+prod(p**(e>>1) for p, e in f)>>1 # Chai Wah Wu, May 06 2026

Crossrefs

Cf. A000188, A018804.

Sequence in context: A209187 A357259 A166250 * A304493 A208323 A067284

Adjacent sequences: A174085 A174086 A174087 * A174089 A174090 A174091

Keyword

nonn,easy,changed

Author

Russell Easterly, Mar 06 2010

Extensions

More terms from Max Alekseyev, Sep 05 2010

Better name from Joerg Arndt, Aug 03 2013

Status

approved