A300509 a(n) is the number of numbers in the interval [2^(n-1), 2^n-1] that have exactly n divisors.

1, 2, 1, 4, 1, 6, 1, 25, 3, 10, 1, 212, 1, 27, 8, 3625, 1, 1291, 1, 7687, 18, 265, 1, 629369, 4, 885, 695, 365370, 1, 685360, 1, 178723829, 131, 10782, 12, 311470930, 1, 38692, 413, 6162245368, 1, 381481569, 1, 1067082439, 139407, 513855, 1

Offset: 1

Author

Jon E. Schoenfield, May 25 2018

Keywords

• nonn
• more
• hard

Comments

Number of n-digit binary numbers with exactly n divisors.

If p is an odd prime, then the only p-digit binary number having exactly p divisors is 2^(p-1), so a(p) = 1.

Only squares have an odd number of divisors, so for odd values of n, a(n) is the number of numbers in the interval [ceiling(sqrt(2^(n-1))), floor(sqrt(2^n-1))] whose squares have exactly n divisors. The next few odd-indexed terms are a(41) = 1, a(43) = 1, a(45) = 139407, a(47) = 1, and a(49) = 8. - Jon E. Schoenfield, May 26 2018

Examples

			a(1) = 1 because the only number in the interval [2^(1-1), 2^1 - 1] = [1, 1] having exactly 1 divisor is 1.
a(2) = 2 because each of the two numbers in the interval [2^(2-1), 2^2 - 1] = [2, 3] has exactly 2 divisors.
a(8) = 25 because the numbers in the interval [2^(8-1), 2^8 - 1] = [128, 255] having exactly 8 divisors are the 1 number of the form p^7 {i.e., 2^7 = 128}, the 8 numbers of the form p^3 * q {135, 136, 152, 184, 189, 232, 248, 250}, and the 16 numbers of the form p*q*r {130, 138, 154, 165, 170, 174, 182, 186, 190, 195, 222, 230, 231, 238, 246, 255}; 1 + 8 + 16 = 25.
		

Crossrefs

Cf. A000005, A284398.

Main diagonal of A346730.

Programs

PARI

a(n) = sum(k=2^(n-1), 2^n-1, numdiv(k)==n); \\ Michel Marcus, May 26 2018

Extensions

a(26)-a(38) from Giovanni Resta, May 26 2018

a(39) from Jon E. Schoenfield, May 26 2018

a(40)-a(41) from Giovanni Resta, May 27 2018

a(42)-a(47) from Jon E. Schoenfield, May 27 2018