login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #31 Nov 01 2023 10:01:50

%S 0,0,1,3,7,10,18,25,35,50,69,94,132,178,244,334,460,629,869,1201,1668,

%T 2314,3223,4493,6280,8793,12322,17288,24286,34139,48036,67630,95274,

%U 134285,189349,267090,376880,531942,750991,1060463,1497741,2115669,2988957,4223225,5967822,8433889

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

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

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

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

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

%C Partial sums of A365930.

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

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

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

%e 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.

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

%o (Python)

%o from sympy import integer_nthroot, integer_log

%o def A365931(n):

%o result, nMersenne, new = 0, (1<<n)-1, n

%o for it in range(1,integer_log(n,2)[0]+1):

%o result += it * ((prev:=new) - (new:=integer_log(nMersenne,it+2)[0]+1))

%o for y in range(2,new): result += (integer_nthroot(nMersenne, y)[0]) - 1

%o return result

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

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

%K nonn,easy,base

%O 1,4

%A _Karl-Heinz Hofmann_, Oct 07 2023