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

0, 1, 3, 6, 13, 29, 59, 121, 248, 501, 1008, 2024, 4064, 8150, 16323, 32686, 65418, 130906, 261913, 523966, 1048123, 2096517, 4193412, 8387355, 16775449, 33551945, 67105359, 134212792, 268428497, 536861096, 1073727974, 2147464110, 4294939718, 8589895659

Offset: 0

Author

Gus Wiseman, Nov 05 2024

Keywords

• nonn

Comments

Non-perfect-powers (A007916) are numbers without a proper integer root.

Also the number of non-perfect-powers with n bits.

Examples

			The non-perfect-powers in each range (rows):
   .
   3
   5  6  7
  10 11 12 13 14 15
  17 18 19 20 21 22 23 24 26 28 29 30 31
Their binary expansions (columns):
  .  11  101  1010  10001
         110  1011  10010
         111  1100  10011
              1101  10100
              1110  10101
              1111  10110
                    10111
                    11000
                    11010
                    11100
                    11101
                    11110
                    11111
		

Crossrefs

The union of all numbers counted is A007916.

For squarefree numbers we have A077643.

For prime-powers we have A244508.

For primes instead of powers of 2 we have A377433, ones A029707.

For perfect-powers we have A377467, for primes A377432, zeros A377436.

A000225(n) counts the interval from A000051(n) to A000225(n+1).

A000961 lists the powers of primes, differences A057820.

A001597 lists the perfect-powers, differences A053289, seconds A376559.

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

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, A045542, A052410, A061398, A304521, A377434, A377435, A377702.

Programs

Mathematica

radQ[n_]:=n>1&&GCD@@Last/@FactorInteger[n]==1;
Table[Length[Select[Range[2^n+1, 2^(n+1)-1],radQ]],{n,0,15}]

Python

from sympy import mobius, integer_nthroot
def A377701(n):
    def f(x): return int(x-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 06 2024

Formula

a(n) = 2^n-1-A377467(n). - Pontus von Brömssen, Nov 06 2024

Extensions

Offset corrected by, and a(16)-a(33) from Pontus von Brömssen, Nov 06 2024