A365930 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, 2, 4, 3, 8, 7, 10, 15, 19, 25, 38, 46, 66, 90, 126, 169, 240, 332, 467, 646, 909, 1270, 1787, 2513, 3529, 4966, 6998, 9853, 13897, 19594, 27644, 39011, 55064, 77741, 109790, 155062, 219049, 309472, 437278, 617928, 873288, 1234268, 1744597, 2466067, 3486093

Offset: 1

Author

Karl-Heinz Hofmann, Sep 23 2023

Keywords

• nonn
• base

Comments

Number of pairs {x,y} with (x,y > 1) for which applies: 2^(n-1) <= 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.

Terms of A365931 are the partial sums of this sequence.

Examples

			For n = 5 the smallest number with bit length 5 is 16 (= 10000 in binary), and the largest number with bit length 5 is 31 (= 11111 in binary). In this range 4 pairs can be found, namely: 2^4 = 16; 4^2 = 16; 5^2 = 25; 3^3 = 27.
		

Links

• Karl-Heinz Hofmann, Table of n, a(n) for n = 1..2000

Crossrefs

Cf. A072103, A365931 (partial sums).

Cf. A365932, A126726, A002193.

Programs

Mathematica

a[n_] := Sum[Ceiling[2^(n/k)] - Ceiling[2^((n-1)/k)], {k, 2, n}]; Array[a, 50] (* Amiram Eldar, Sep 23 2023 *)

PARI

for (blen = 0, 25, my (b1=2^blen, b2=2*b1-1, np=0); for (x = b1, b2, my (m=ispower(x)); if (m>1, np+=(sumdiv(m,y,1)-1), np+=m)); print1 (np,", ")) \\ Hugo Pfoertner, Oct 02 2023

Python

from sympy import integer_nthroot
def A365930(n):
    return sum(integer_nthroot((2**n)-1,y)[0]-integer_nthroot(2**(n-1)-1,y)[0] for y in range(2, n+1))

Python

from sympy import integer_nthroot, integer_log
def A365930(n): # a bit more efficient program
    c, y, a, b = 0, 2, (1<Chai Wah Wu, Oct 16 2023

Formula

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

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

a(n) = A365931(n) - A365931(n-1).