login
A365930
a(n) = number of pairs {x,y} with (x,y > 1) such that x^y (= terms of A072103) has bit length n.
3
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
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).
Sequence in context: A237739 A337909 A358523 * A111699 A067179 A318993
KEYWORD
nonn,base
AUTHOR
Karl-Heinz Hofmann, Sep 23 2023
STATUS
approved