A377435 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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):

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

AUTHOR

Gus Wiseman, Nov 04 2024

EXTENSIONS

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

STATUS

approved