cp's OEIS Frontend

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

%I A378614 #22 Dec 03 2024 12:22:02
%S A378614 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 A378614 33,35,22,14,40,39,42,45,46,47,50,52,32,19,55,56,59,60,27,35,65,64,67,
%U A378614 68,40,30,75,74,77,19,57,62,9,9,81,81,88,89,87,32,55,94
%N A378614 Number of composite numbers (A002808) between consecutive perfect powers (A001597), exclusive.
%C A378614 The inclusive version is a(n) + 2.
%H A378614 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 A378614 The composite numbers counted by a(n) cover A106543 with the following disjoint sets:
%e A378614   .
%e A378614   6
%e A378614   .
%e A378614   10 12 14 15
%e A378614   18 20 21 22 24
%e A378614   26
%e A378614   28 30
%e A378614   33 34 35
%e A378614   38 39 40 42 44 45 46 48
%e A378614   50 51 52 54 55 56 57 58 60 62 63
%t A378614 perpowQ[n_]:=n==1||GCD@@FactorInteger[n][[All,2]]>1;
%t A378614 v=Select[Range[100],perpowQ[#]&];
%t A378614 Table[Length[Select[Range[v[[i]]+1,v[[i+1]]-1],CompositeQ]],{i,Length[v]-1}]
%o A378614 (Python)
%o A378614 from sympy import mobius, integer_nthroot, primepi
%o A378614 def A378614(n):
%o A378614     def bisection(f,kmin=0,kmax=1):
%o A378614         while f(kmax) > kmax: kmax <<= 1
%o A378614         while kmax-kmin > 1:
%o A378614             kmid = kmax+kmin>>1
%o A378614             if f(kmid) <= kmid:
%o A378614                 kmax = kmid
%o A378614             else:
%o A378614                 kmin = kmid
%o A378614         return kmax
%o A378614     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 A378614     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 A378614 For prime instead of perfect power we have A046933.
%Y A378614 For prime instead of composite we have A080769.
%Y A378614 For nonsquarefree instead of perfect power we have A378373, for primes A236575.
%Y A378614 For nonprime prime power instead of perfect power we have A378456.
%Y A378614 A001597 lists the perfect powers, differences A053289.
%Y A378614 A002808 lists the composite numbers.
%Y A378614 A007916 lists the non perfect powers, differences A375706.
%Y A378614 A069623 counts perfect powers <= n.
%Y A378614 A076411 counts perfect powers < n.
%Y A378614 A106543 lists the composite non perfect powers.
%Y A378614 A377432 counts perfect powers between primes, see A377434, A377436, A377466.
%Y A378614 A378365 gives the least prime > each perfect power, opposite A377283.
%Y A378614 Cf. A045542, A052410, A065890, A076412, A081676, A216765, A276781, A377057, A377468, A378035, A378251.
%K A378614 nonn
%O A378614 1,4
%A A378614 _Gus Wiseman_, Dec 02 2024