A188169 The number of divisors d of n of the form d == 1 (mod 8).

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 2, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 2, 2, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 1, 2, 2, 1, 2, 1, 1, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 2

Offset: 1

Author

R. J. Mathar, Mar 23 2011

Keywords

• nonn
• easy

Comments

a(n) >= 1 as the divisor d=1 is always counted.

The largest terms up to n = 10^6 are each equal to 24. Those 8 terms are for n = 675675, 765765, 799425, 855855, 863379, 883575, 945945, or 987525. - Harvey P. Dale, May 31 2017

From David A. Corneth, Apr 06 2021: (Start)

a(n) can be computed from the prime factorization of n. Let v(n) = (n1, n3, n5, n7) where n_r is the number of divisors of n in class r (mod 8) (we do not care about even remainders). Then if gcd(k, m) = 1 we have v(k) = (k1, k3, k5, k7) so a(k) = k1, v(m) = (m1, m3, m5, m7) so a(m) = k1.

We have a(k*m) = (km)_1 = k1*m1 + k2*m2 + k3*m3 + k4*m4. The other (km)_3..(km)_7 have a similar expression.

If p == 1 (mod 8) then a(p^e) = e + 1 otherwise floor(e/2) + 1. (End)

Links

• David A. Corneth, Table of n, a(n) for n = 1..10000
• David A. Corneth, PARI program.
• R. A. Smith and M. V. Subbarao, The average number of divisors in an arithmetic progression, Canadian Mathematical Bulletin, Vol. 24, No. 1 (1981), pp. 37-41.

Crossrefs

Cf. A001826, A188170, A188171, A188172.

Cf. A001620, A256781.

Programs

Maple

sigmamr := proc(n,m,r) local a,d ; a := 0 ; for d in numtheory[divisors](n) do if modp(d,m) = r then a := a+1 ; end if; end do: a; end proc:
A188169 := proc(n) sigmamr(n,8,1) ; end proc:

Mathematica

Table[Count[Divisors[n],?(Mod[#,8]==1&)],{n,100}] (* _Harvey P. Dale, May 31 2017 *)

PARI

a(n) = {my(d = divisors(n)); #select(x -> x%8 == 1, d)} \\ David A. Corneth, Apr 06 2021

PARI

\\ See PARI link. David A. Corneth, Apr 06 2021

Formula

a(n) + A188171(n) = A001826(n).

G.f.: Sum_{k>=1} x^k/(1 - x^(8*k)). - Ilya Gutkovskiy, Sep 11 2019

a(k) = a(2*k). - David A. Corneth, Apr 06 2021

Sum_{k=1..n} a(k) = n*log(n)/8 + c*n + O(n^(1/3)*log(n)), where c = gamma(1,8) - (1 - gamma)/8 = A256781 - (1 - A001620)/8 = 0.735783... (Smith and Subbarao, 1981). - Amiram Eldar, Nov 25 2023