A377467 Number of perfect-powers x in the range 2^n < x < 2^(n+1).

0, 0, 0, 1, 2, 2, 4, 6, 7, 10, 15, 23, 31, 41, 60, 81, 117, 165, 230, 321, 452, 634, 891, 1252, 1766, 2486, 3504, 4935, 6958, 9815, 13849, 19537, 27577, 38932, 54971, 77640, 109667, 154921, 218878, 309276, 437046, 617657, 872967, 1233895, 1744152, 2465546, 3485477

Offset: 0

Author

Gus Wiseman, Nov 04 2024

Keywords

• nonn

Comments

Perfect-powers (A001597) are numbers with a proper integer root, complement A007916.

Also the number of perfect-powers, except for powers of 2, with n bits.

Examples

			The perfect-powers in each prescribed range (rows):
    .
    .
    .
    9
   25   27
   36   49
   81  100  121  125
  144  169  196  216  225  243
  289  324  343  361  400  441  484
  529  576  625  676  729  784  841  900  961 1000
The binary expansions for n >= 3 (columns):
    1001  11001  100100  1010001  10010000  100100001
          11011  110001  1100100  10101001  101000100
                         1111001  11000100  101010111
                         1111101  11011000  101101001
                                  11100001  110010000
                                  11110011  110111001
                                            111100100
		

Crossrefs

The version for squarefree numbers is A077643.

The version for prime-powers is A244508.

For primes instead of powers of 2 we have A377432, zeros A377436.

Including powers of 2 in the range gives A377435.

The version for non-perfect-powers is A377701.

The union of all numbers counted is A377702.

A000040 lists the primes, differences A001223.

A000961 lists the powers of primes, differences A057820.

A001597 lists the perfect-powers, differences A053289.

A007916 lists the non-perfect-powers, differences A375706.

A081676 gives the greatest perfect-power <= n.

A131605 lists perfect-powers that are not prime-powers.

A377468 gives the least perfect-power > n.

Cf. A000015, A013597, A014210, A014234, A023055, A031218, A045542, A052410, A065514, A069623, A216765, A246655, A345531.

Programs

Mathematica

perpowQ[n_]:=n==1||GCD@@FactorInteger[n][[All,2]]>1;
Table[Length[Select[Range[2^n+1,2^(n+1)-1],perpowQ]],{n,0,15}]

Python

from sympy import mobius, integer_nthroot
def A377467(n):
    def f(x): return int(1-sum(mobius(k)*(integer_nthroot(x,k)[0]-1) for k in range(2,x.bit_length())))
    return f((1<Chai Wah Wu, Nov 05 2024

Formula

For n != 1, a(n) = A377435(n) - 1.

Extensions

a(26)-a(46) from Chai Wah Wu, Nov 05 2024