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,4

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.

Links

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

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).

Example

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.

Mathematica

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

Prog

(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<<n)-1, (1<<n-1)-1
    while y<n:
        c += (m:=integer_nthroot(a, y)[0])-(k:=integer_nthroot(b, y)[0])
        y = (integer_log(b, k)[0] if m==k else y)+1
    return c # Chai Wah Wu, Oct 16 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

Crossrefs

Cf. A072103, A365931 (partial sums).

Cf. A365932, A126726, A002193.

Sequence in context: A237739 A337909 A358523 * A111699 A067179 A318993

Adjacent sequences: A365927 A365928 A365929 * A365931 A365932 A365933

Keyword

nonn,base

Author

Karl-Heinz Hofmann, Sep 23 2023

Status

approved