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

1, 0, 1, 2, 3, 3, 5, 7, 8, 11, 16, 24, 32, 42, 61, 82, 118, 166, 231, 322, 453, 635, 892, 1253, 1767, 2487, 3505, 4936, 6959, 9816, 13850, 19538, 27578, 38933, 54972, 77641, 109668, 154922, 218879, 309277, 437047, 617658, 872968, 1233896, 1744153, 2465547, 3485478

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 with n bits.

Examples

			The perfect-powers in each prescribed range (rows):
    1
    .
    4
    8    9
   16   25   27
   32   36   49
   64   81  100  121  125
  128  144  169  196  216  225  243
  256  289  324  343  361  400  441  484
  512  529  576  625  676  729  784  841  900  961 1000
Their binary expansions (columns):
  1  .  100  1000  10000  100000  1000000  10000000  100000000
             1001  11001  100100  1010001  10010000  100100001
                   11011  110001  1100100  10101001  101000100
                                  1111001  11000100  101010111
                                  1111101  11011000  101101001
                                           11100001  110010000
                                           11110011  110111001
                                                     111100100
		

Crossrefs

The union of all numbers counted is A001597, without powers of two A377702.

The version for squarefree numbers is A077643.

These are the first differences of A188951.

The version for prime-powers is A244508.

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

Not counting powers of 2 gives A377467.

The version for non-perfect-powers is A377701.

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, A345531, A377434.

Programs

Mathematica

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

Python

from sympy import mobius, integer_nthroot
def A377435(n):
    if n==0: return 1
    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) = A377467(n) + 1.

Extensions

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