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

Author

Gus Wiseman, Dec 02 2024

Keywords

• nonn

Comments

The inclusive version is a(n) + 2.

Examples

			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
		

Links

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

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.

Programs

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

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