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

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.

Links

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

Formula

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

Example

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

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

Prog

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

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.

Sequence in context: A227560 A046639 A178702 * A265992 A089284 A297106

Adjacent sequences: A377464 A377465 A377466 * A377468 A377469 A377470

Keyword

nonn

Author

Gus Wiseman, Nov 04 2024

Extensions

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

Status

approved