cp's OEIS Frontend

A336175 Numbers k such that there are no powerful numbers between k^2 and (k+1)^2.

%I A336175 #17 Sep 15 2024 22:01:39
%S A336175 1,3,4,6,7,9,12,13,17,21,23,24,26,27,30,32,34,35,38,40,43,47,49,54,60,
%T A336175 61,64,66,68,69,71,75,80,81,85,86,91,95,97,99,105,106,108,112,120,123,
%U A336175 125,128,131,133,136,137,139,142,143,151,153,154,159,160,162,163
%N A336175 Numbers k such that there are no powerful numbers between k^2 and (k+1)^2.
%C A336175 Positions of 0's in A119241.
%C A336175 Shiu (1980) proved that this sequence has an asymptotic density 0.2759... A more accurate calculation using his formula gives 0.275965511407718981...
%D A336175 József Sándor, Dragoslav S. Mitrinovic and Borislav Crstici, Handbook of Number Theory I, Springer Science & Business Media, 2005, chapter VI, p. 226.
%H A336175 Amiram Eldar, <a href="/A336175/b336175.txt">Table of n, a(n) for n = 1..10000</a>
%H A336175 P. Shiu, <a href="https://doi.org/10.1112/S0025579300010056">On the number of square-full integers between successive squares</a>, Mathematika, Vol. 27, No. 2 (1980), pp. 171-178.
%F A336175 a(n) ~ k*n, where k = 3.623641211175... is the inverse of the density, see Shiu link. - _Charles R Greathouse IV_, Oct 31 2022
%e A336175 1 is a term since the two numbers between 1^2 = 1 and (1+1)^2 = 4, 2 and 3, are not powerful.
%e A336175 2 is not a term since there is a powerful number, 8 = 2^3, between 2^2 = 4 and (2+1)^2 = 9.
%t A336175 powQ[n_] := (n == 1) || Min @@ FactorInteger[n][[;; , 2]] > 1; Select[Range[150], ! AnyTrue[Range[#^2 + 1, (# + 1)^2 - 1], powQ] &]
%o A336175 (PARI) is(n)=forfactored(k=n^2+1,n^2+2*n, if(ispowerful(k), return(0))); 1 \\ _Charles R Greathouse IV_, Oct 31 2022
%o A336175 (Python)
%o A336175 from functools import lru_cache
%o A336175 from math import isqrt
%o A336175 from sympy import mobius, integer_nthroot
%o A336175 def A336175(n):
%o A336175     def squarefreepi(n): return int(sum(mobius(k)*(n//k**2) for k in range(1, isqrt(n)+1)))
%o A336175     def bisection(f,kmin=0,kmax=1):
%o A336175         while f(kmax) > kmax: kmax <<= 1
%o A336175         while kmax-kmin > 1:
%o A336175             kmid = kmax+kmin>>1
%o A336175             if f(kmid) <= kmid:
%o A336175                 kmax = kmid
%o A336175             else:
%o A336175                 kmin = kmid
%o A336175         return kmax
%o A336175     @lru_cache(maxsize=None)
%o A336175     def g(x):
%o A336175         c, l = 0, 0
%o A336175         j = isqrt(x)
%o A336175         while j>1:
%o A336175             k2 = integer_nthroot(x//j**2,3)[0]+1
%o A336175             w = squarefreepi(k2-1)
%o A336175             c += j*(w-l)
%o A336175             l, j = w, isqrt(x//k2**3)
%o A336175         c += squarefreepi(integer_nthroot(x,3)[0])-l
%o A336175         return c
%o A336175     def f(x):
%o A336175         c, a = n+x, 1
%o A336175         for k in range(1,x+1):
%o A336175             b = g((k+1)**2)
%o A336175             if b == a+1:
%o A336175                 c -= 1
%o A336175             a = b
%o A336175         return c
%o A336175     return bisection(f,n,n) # _Chai Wah Wu_, Sep 14 2024
%Y A336175 Cf. A001694, A119241, A119242, A336176, A336177, A336178.
%K A336175 nonn
%O A336175 1,2
%A A336175 _Amiram Eldar_, Jul 10 2020