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,4

Comments

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

Also the number of perfect-powers with n bits.

Links

Table of n, a(n) for n=0..46.

Formula

For n != 1, a(n) = A377467(n) + 1.

Example

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

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}]

Prog

(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<<n+1)-1)-f((1<<n)-1) # Chai Wah Wu, Nov 05 2024

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.

Sequence in context: A320036 A053271 A035360 * A027587 A363300 A030779

Adjacent sequences: A377432 A377433 A377434 * A377436 A377438 A377439

Keyword

nonn

Author

Gus Wiseman, Nov 04 2024

Extensions

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

Status

approved