A153876 a(n) = Sum_{i=2^(n-1)..2^n-1} sigma_0(i), sigma_0(i) number of divisors of n, n positive integer.

1, 4, 11, 29, 68, 160, 364, 820, 1813, 3981, 8674, 18782, 40387, 86443, 184232, 391188, 827787, 1746443, 3674573, 7712561, 16151933, 33757505, 70422235, 146659055, 304947023, 633152157, 1312820598, 2718674046, 5623413203, 11618957217, 23982175093, 49452872529

Offset

1,2

Comments

This sequence tells how many binary numbers with n digits are there in the multiplication matrix [1,...,2^n -1]x[1,...,2^n -1]. In general, counting how many base-B numbers of length n are there in the multiplication matrix [1,...,B^n -1]x[1,...,B^n -1] gives a(n)= sum_{i=B^(n-1),(B^n)-1} sigma_0(i). Besides this motivation it is interesting to see the behavior of partial sums of sigma_0(i) on growing intervals : a(n)= sum_{i=f(n-1),f(n)} sigma_0(i).

Links

Chai Wah Wu, Table of n, a(n) for n = 1..76

Formula

a(n) = A085831(n) - A085831(n-1)-1. - R. J. Mathar, Jan 05 2009

a(n) = Sum_{k>=1} k * A346730(n,k). - Alois P. Heinz, Aug 01 2021

Prog

(PARI) a(n) = sum(i=2^(n-1), 2^n-1, numdiv(i)); \\ Michel Marcus, Oct 10 2021
(Python)
from math import isqrt
def A153876(n): return ((t:=isqrt(b:=(1<<n-1)-1))+(s:=isqrt(a:=(1<<n)-1)))*(t-s)+(sum(a//k for k in range(1, s+1))-sum(b//k for k in range(1, t+1))<<1) # Chai Wah Wu, Oct 23 2023

Crossrefs

Cf. A000005, A006218, A095256, A140480, A346730.

Sequence in context: A217918 A360447 A000604 * A036881 A275012 A055418

Adjacent sequences: A153873 A153874 A153875 * A153877 A153878 A153879

Keyword

nonn,easy

Author

Ctibor O. Zizka, Jan 03 2009

Extensions

a(14)-a(32) from Alois P. Heinz, Aug 01 2021

Status

approved