A378614 Number of composite numbers (A002808) between consecutive perfect powers (A001597), exclusive.

0, 1, 0, 4, 5, 1, 2, 3, 8, 11, 12, 15, 15, 3, 1, 12, 19, 21, 16, 7, 12, 11, 25, 29, 16, 13, 32, 33, 35, 22, 14, 40, 39, 42, 45, 46, 47, 50, 52, 32, 19, 55, 56, 59, 60, 27, 35, 65, 64, 67, 68, 40, 30, 75, 74, 77, 19, 57, 62, 9, 9, 81, 81, 88, 89, 87, 32, 55, 94

Offset

1,4

Comments

The inclusive version is a(n) + 2.

Links

Michael De Vlieger, Table of n, a(n) for n = 1..12127 (between consecutive perfect powers k <= 2^27)

Example

The composite numbers counted by a(n) cover A106543 with the following disjoint sets:
  .
  6
  .
  10 12 14 15
  18 20 21 22 24
  26
  28 30
  33 34 35
  38 39 40 42 44 45 46 48
  50 51 52 54 55 56 57 58 60 62 63

Mathematica

perpowQ[n_]:=n==1||GCD@@FactorInteger[n][[All, 2]]>1;
v=Select[Range[100], perpowQ[#]&];
Table[Length[Select[Range[v[[i]]+1, v[[i+1]]-1], CompositeQ]], {i, Length[v]-1}]

Prog

(Python)
from sympy import mobius, integer_nthroot, primepi
def A378614(n):
    def bisection(f, kmin=0, kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return int(n+x-1+sum(mobius(k)*(integer_nthroot(x, k)[0]-1) for k in range(2, x.bit_length())))
    return -(a:=bisection(f, n, n))+(b:=bisection(lambda x:f(x)+1, a+1, a+1))-primepi(b)+primepi(a)-1 # Chai Wah Wu, Dec 03 2024

Crossrefs

For prime instead of perfect power we have A046933.

For prime instead of composite we have A080769.

For nonsquarefree instead of perfect power we have A378373, for primes A236575.

For nonprime prime power instead of perfect power we have A378456.

A001597 lists the perfect powers, differences A053289.

A002808 lists the composite numbers.

A007916 lists the non perfect powers, differences A375706.

A069623 counts perfect powers <= n.

A076411 counts perfect powers < n.

A106543 lists the composite non perfect powers.

A377432 counts perfect powers between primes, see A377434, A377436, A377466.

A378365 gives the least prime > each perfect power, opposite A377283.

Cf. A045542, A052410, A065890, A076412, A081676, A216765, A276781, A377057, A377468, A378035, A378251.

Sequence in context: A374035 A016493 A101626 * A378456 A195853 A070769

Adjacent sequences: A378611 A378612 A378613 * A378615 A378616 A378617

Keyword

nonn,new

Author

Gus Wiseman, Dec 02 2024

Status

approved