A248517 Number of odd divisors > 1 in the numbers 1 through n, counted with multiplicity.

0, 0, 0, 1, 1, 2, 3, 4, 4, 6, 7, 8, 9, 10, 11, 14, 14, 15, 17, 18, 19, 22, 23, 24, 25, 27, 28, 31, 32, 33, 36, 37, 37, 40, 41, 44, 46, 47, 48, 51, 52, 53, 56, 57, 58, 63, 64, 65, 66, 68, 70, 73, 74, 75, 78, 81, 82, 85, 86, 87, 90, 91, 92, 97, 97, 100, 103, 104, 105, 108, 111

Offset: 0

Author

R. J. Mathar, Jun 18 2015

Keywords

• nonn
• easy

Comments

Number of partitions of n into 3 parts such that the smallest part divides the "middle" part. - Wesley Ivan Hurt, Oct 21 2021

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 0..10000

Crossrefs

Cf. A002541, A006218, A069283.

Programs

Maple

A248517 := proc(n)
    add(A069283(j),j=1..n) ;
end proc:

Mathematica

Table[Sum[Floor[Floor[i/2]/(n - i)], {i, n - 1}], {n, 0, 100}] (* Wesley Ivan Hurt, Jan 30 2016 *)
Join[{0},Accumulate[Table[Count[Divisors[n],?OddQ]-1,{n,80}]]] (* _Harvey P. Dale, Jan 06 2019 *)
Join[{0}, Accumulate[Table[DivisorSigma[0, n/2^IntegerExponent[n, 2]] - 1, {n, 1, 100}]]] (* Amiram Eldar, Jul 10 2022 *)

PARI

a(n)=my(n2=n\2); sum(k=1, sqrtint(n), n\k)*2-sqrtint(n)^2-sum(k=1, sqrtint(n2), n2\k)*2+sqrtint(n2)^2-n \\ Charles R Greathouse IV, Jun 18 2015

Python

from math import isqrt
def A248517(n): return ((t:=isqrt(m:=n>>1))+(s:=isqrt(n)))*(t-s)+(sum(n//k for k in range(1,s+1))-sum(m//k for k in range(1,t+1))<<1)-n # Chai Wah Wu, Oct 23 2023

Formula

a(n) = Sum_{j=1..n} A069283(j).

a(n) = A060831(n) - n.

a(n) = A006218(n) - A006218(floor(n/2)) - n. - Charles R Greathouse IV, Jun 18 2015

a(n) = Sum_{i=1..n-1} floor(floor(i/2)/(n-i)). - Wesley Ivan Hurt, Jan 30 2016