A365931 a(n) = number of pairs {x,y} with (x,y > 1) such that x^y (= terms of A072103) has bit length <= n.

0, 0, 1, 3, 7, 10, 18, 25, 35, 50, 69, 94, 132, 178, 244, 334, 460, 629, 869, 1201, 1668, 2314, 3223, 4493, 6280, 8793, 12322, 17288, 24286, 34139, 48036, 67630, 95274, 134285, 189349, 267090, 376880, 531942, 750991, 1060463, 1497741, 2115669, 2988957, 4223225, 5967822, 8433889

Offset: 1

Author

Karl-Heinz Hofmann, Oct 07 2023

Keywords

• nonn
• easy
• base

Comments

Number of pairs {x,y} with (x,y > 1) for which x^y < 2^n-1.

In some special cases different pairs have the same result (see A072103 and the example here) and those multiple representations are counted separately.

There is no need to include 2^n-1 because it is a Mersenne number and it cannot be a power anyway.

Limit_{n->oo} a(n)/a(n-1) = sqrt(2) = A002193.

Partial sums of A365930.

Examples

			For n = 6: the Mersenne number 2^6-1 = 63 is the largest number with bit length 6 and the upper bound for the following a(6) = 10 powers: 2^2, 2^3, 2^4, 2^5, 3^2, 3^3, 4^2, 5^2, 6^2, 7^2.
		

Crossrefs

Cf. A072103, A002193, A365930 (first differences).

Cf. A017912 (squares), A017981 (cubes).

Programs

Mathematica

a[n_] := Sum[Ceiling[2^(n/k)] - 2, {k, 2, n}]; Array[a, 47]

Python

from sympy import integer_nthroot, integer_log
def A365931(n):
    result, nMersenne, new = 0, (1<
				

Formula

a(n) = Sum_{y = 2..n} (ceiling(2^(n/y)) - 2)

a(n) = Sum_{y = 2..n} (floor((2^n-1)^(1/y)) - 1)

a(n) = Sum_{k = 1..n} A365930(k).