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

Comments

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

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

Links

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

Formula

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

Example

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

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

Prog

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

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.

Sequence in context: A348124 A095768 A002478 * A106496 A052933 A071014

Adjacent sequences: A377698 A377699 A377700 * A377702 A377703 A377704

Keyword

nonn

Author

Gus Wiseman, Nov 05 2024

Extensions

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

Status

approved