cp's OEIS Frontend

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

%I A365930 #106 Nov 01 2023 11:49:07
%S A365930 0,0,1,2,4,3,8,7,10,15,19,25,38,46,66,90,126,169,240,332,467,646,909,
%T A365930 1270,1787,2513,3529,4966,6998,9853,13897,19594,27644,39011,55064,
%U A365930 77741,109790,155062,219049,309472,437278,617928,873288,1234268,1744597,2466067,3486093
%N A365930 a(n) = number of pairs {x,y} with (x,y > 1) such that x^y (= terms of A072103) has bit length n.
%C A365930 Number of pairs {x,y} with (x,y > 1) for which applies: 2^(n-1) <= x^y < 2^n-1.
%C A365930 In some special cases different pairs have the same result (see A072103 and the example here) and those multiple representations are counted separately.
%C A365930 There is no need to include 2^n-1 because it is a Mersenne number and it cannot be a power anyway.
%C A365930 Limit_{n->oo} a(n)/a(n-1) = sqrt(2) = A002193.
%C A365930 Terms of A365931 are the partial sums of this sequence.
%H A365930 Karl-Heinz Hofmann, <a href="/A365930/b365930.txt">Table of n, a(n) for n = 1..2000</a>
%F A365930 a(n) = Sum_{y=2..n} (ceiling(2^(n/y)) - ceiling(2^((n-1)/y))).
%F A365930 a(n) = Sum_{y=2..n} (floor((2^n-1)^(1/y)) - floor((2^(n-1)-1)^(1/y))).
%F A365930 a(n) = A365931(n) - A365931(n-1).
%e A365930 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.
%t A365930 a[n_] := Sum[Ceiling[2^(n/k)] - Ceiling[2^((n-1)/k)], {k, 2, n}]; Array[a, 50] (* _Amiram Eldar_, Sep 23 2023 *)
%o A365930 (Python)
%o A365930 from sympy import integer_nthroot
%o A365930 def A365930(n):
%o A365930     return sum(integer_nthroot((2**n)-1,y)[0]-integer_nthroot(2**(n-1)-1,y)[0] for y in range(2, n+1))
%o A365930 (Python)
%o A365930 from sympy import integer_nthroot, integer_log
%o A365930 def A365930(n): # a bit more efficient program
%o A365930     c, y, a, b = 0, 2, (1<<n)-1, (1<<n-1)-1
%o A365930     while y<n:
%o A365930         c += (m:=integer_nthroot(a,y)[0])-(k:=integer_nthroot(b,y)[0])
%o A365930         y = (integer_log(b,k)[0] if m==k else y)+1
%o A365930     return c # _Chai Wah Wu_, Oct 16 2023
%o A365930 (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
%Y A365930 Cf. A072103, A365931 (partial sums).
%Y A365930 Cf. A365932, A126726, A002193.
%K A365930 nonn,base
%O A365930 1,4
%A A365930 _Karl-Heinz Hofmann_, Sep 23 2023