A378614 - OEIS

%I #22 Dec 03 2024 12:22:02

%S 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,

%T 33,35,22,14,40,39,42,45,46,47,50,52,32,19,55,56,59,60,27,35,65,64,67,

%U 68,40,30,75,74,77,19,57,62,9,9,81,81,88,89,87,32,55,94

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

%C The inclusive version is a(n) + 2.

%H Michael De Vlieger, <a href="/A378614/b378614.txt">Table of n, a(n) for n = 1..12127</a> (between consecutive perfect powers k <= 2^27)

%e The composite numbers counted by a(n) cover A106543 with the following disjoint sets:

%e   .

%e   6

%e   .

%e   10 12 14 15

%e   18 20 21 22 24

%e   26

%e   28 30

%e   33 34 35

%e   38 39 40 42 44 45 46 48

%e   50 51 52 54 55 56 57 58 60 62 63

%t perpowQ[n_]:=n==1||GCD@@FactorInteger[n][[All,2]]>1;

%t v=Select[Range[100],perpowQ[#]&];

%t Table[Length[Select[Range[v[[i]]+1,v[[i+1]]-1],CompositeQ]],{i,Length[v]-1}]

%o (Python)

%o from sympy import mobius, integer_nthroot, primepi

%o def A378614(n):

%o     def bisection(f,kmin=0,kmax=1):

%o         while f(kmax) > kmax: kmax <<= 1

%o         while kmax-kmin > 1:

%o             kmid = kmax+kmin>>1

%o             if f(kmid) <= kmid:

%o                 kmax = kmid

%o             else:

%o                 kmin = kmid

%o         return kmax

%o     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())))

%o     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

%Y For prime instead of perfect power we have A046933.

%Y For prime instead of composite we have A080769.

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

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

%Y A001597 lists the perfect powers, differences A053289.

%Y A002808 lists the composite numbers.

%Y A007916 lists the non perfect powers, differences A375706.

%Y A069623 counts perfect powers <= n.

%Y A076411 counts perfect powers < n.

%Y A106543 lists the composite non perfect powers.

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

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

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

%K nonn,new

%O 1,4

%A _Gus Wiseman_, Dec 02 2024