OFFSET
1,4
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.
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).
EXAMPLE
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.
MATHEMATICA
a[n_] := Sum[Ceiling[2^(n/k)] - 2, {k, 2, n}]; Array[a, 47]
PROG
(Python)
from sympy import integer_nthroot, integer_log
def A365931(n):
result, nMersenne, new = 0, (1<<n)-1, n
for it in range(1, integer_log(n, 2)[0]+1):
result += it * ((prev:=new) - (new:=integer_log(nMersenne, it+2)[0]+1))
for y in range(2, new): result += (integer_nthroot(nMersenne, y)[0]) - 1
return result
CROSSREFS
KEYWORD
nonn,easy,base
AUTHOR
Karl-Heinz Hofmann, Oct 07 2023
STATUS
approved