login
Powerful numbers, definition (1): if a prime p divides n then p^2 must also divide n (also called squareful, square full, square-full or 2-powerful numbers).
(Formerly M3325 N1335)
371

%I M3325 N1335 #207 Sep 22 2024 03:54:30

%S 1,4,8,9,16,25,27,32,36,49,64,72,81,100,108,121,125,128,144,169,196,

%T 200,216,225,243,256,288,289,324,343,361,392,400,432,441,484,500,512,

%U 529,576,625,648,675,676,729,784,800,841,864,900,961,968,972,1000

%N Powerful numbers, definition (1): if a prime p divides n then p^2 must also divide n (also called squareful, square full, square-full or 2-powerful numbers).

%C Numbers of the form a^2*b^3, a >= 1, b >= 1.

%C In other words, if the prime factorization of n is Product_k p_k^e_k then all e_k are greater than 1.

%C Numbers n such that Sum_{d|n} phi(d)*phi(n/d)*mu(d) > 0; places of nonzero A300717. - _Benoit Cloitre_, Nov 30 2002

%C This sequence is closed under multiplication. The primitive elements are A168363. - _Franklin T. Adams-Watters_, May 30 2011

%C Complement of A052485. - _Reinhard Zumkeller_, Sep 16 2011

%C The number of terms less than or equal to 10^k beginning with k = 0: 1, 4, 14, 54, 185, 619, 2027, 6553, 21044, ...: A118896. - _Robert G. Wilson v_, Aug 11 2014

%C a(10^n): 1, 49, 3136, 253472, 23002083, 2200079025, 215523459072, 21348015504200, 2125390162618116, ... . - _Robert G. Wilson v_, Aug 15 2014

%C a(m) mod prime(n) > 0 for m < A258599(n); a(A258599(n)) = A001248(n) = prime(n)^2. - _Reinhard Zumkeller_, Jun 06 2015

%C From _Des MacHale_, Mar 07 2021: (Start)

%C A number m is powerful if and only if |R/Z(R)| = m, for some finite non-commutative ring R.

%C A number m is powerful if and only if |G/Z(G)| = m, for some finite nilpotent class two group G (Reference Aine Nishe). (End)

%C Numbers n such that Sum_{k=1..n} phi(gcd(n,k))*mu(gcd(n,k)) > 0. - _Richard L. Ollerton_, May 09 2021

%D G. E. Hardy and M. V. Subbarao, Highly powerful numbers, Congress. Numer. 37 (1983), 277-307.

%D Aleksandar Ivić, The Riemann Zeta-Function, Wiley, NY, 1985, see p. 407.

%D Richard A. Mollin, Quadratics, CRC Press, 1996, Section 1.6.

%D Aine NiShe, Commutativity and Generalisations in Finite Groups, Ph.D. Thesis, University College Cork, 2000.

%D Paulo Ribenboim, Meine Zahlen, meine Freunde, 2009, Springer, 9.1 Potente Zahlen, pp. 241-247.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D Gérald Tenenbaum, Introduction to analytic and probabilistic number theory, Cambridge University Press, 1995, p. 54, exercise 10 (in the third edition 2015, p. 63, exercise 70).

%H Amiram Eldar, <a href="/A001694/b001694.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..1000 from T. D. Noe, terms 1001..5000 from G. C. Greubel)

%H Paul T. Bateman and Emil Grosswald, <a href="http://projecteuclid.org/euclid.ijm/1255380836">On a theorem of Erdős and Szekeres</a>, Illinois J. Math. 2:1 (1958), pp. 88-98.

%H Valentin Blomer, <a href="http://dx.doi.org/10.1112/S0024610704006040">Binary quadratic forms with large discriminants and sums of two squareful numbers II</a>, Journal of the London Mathematical Society 71:1 (2005), pp. 69-84.

%H C. K. Caldwell, <a href="https://t5k.org/glossary/page.php?sort=PowerfulNumber">Powerful Numbers</a>.

%H Tsz Ho Chan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Chan/chan33.html">Arithmetic Progressions Among Powerful Numbers</a>, J. Int. Seq., Vol. 26 (2023), Article 23.1.1.

%H J.-M. de Koninck, N. Doyon, and F. Luca, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/DeKoninck/dek.html">Powerful Values of Quadratic Polynomials</a>, J. Int. Seq. 14 (2011), Article 11.3.3.

%H P. Erdős and G. Szekeres, <a href="http://pub.acta.hu/acta/showCustomerArticle.action?id=5508&amp;dataObjectType=article">Über die Anzahl der Abelschen Gruppen gegebener Ordnung und über ein verwandtes zahlentheoretisches Problem</a>, Acta Sci. Math. (Szeged), 7 (1935), 95-102. [Zahlen i-ter Art, p. 101]

%H S. W. Golomb, <a href="http://www.jstor.org/stable/2317020">Powerful numbers</a>, Amer. Math. Monthly, Vol. 77 (1970), 848-852.

%H K. Schneider, PlanetMath.org, <a href="http://planetmath.org/encyclopedia/SquarefullNumber.html">Squarefull Number</a>.

%H V. Shevelev, <a href="http://dx.doi.org/10.4064/aa8395-5-2016">S-exponential numbers</a>, Acta Arithmetica, Vol. 175(2016), 385-395.

%H D. Suryanarayana and R. Sita Rama Chandra Rao, <a href="https://projecteuclid.org/euclid.afm/1485896165">The distribution of square-full integers</a>, Ark. Mat., Volume 11, Number 1-2 (1973), 195-201.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PowerfulNumber.html">Powerful Number</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Squareful.html">Squareful</a>.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Powerful_number">Powerful number</a>.

%H <a href="/index/Pow#powerful">Index entries for sequences related to powerful numbers</a>.

%F A112526(a(n)) = 1. - _Reinhard Zumkeller_, Sep 16 2011

%F Bateman & Grosswald prove that there are zeta(3/2)/zeta(3) x^{1/2} + zeta(2/3)/zeta(2) x^{1/3} + O(x^{1/6}) terms up to x; see section 5 for a more precise error term. - _Charles R Greathouse IV_, Nov 19 2012

%F a(n) = A224866(n) - 1. - _Reinhard Zumkeller_, Jul 23 2013

%F Sum_{n>=1} 1/a(n) = zeta(2)*zeta(3)/zeta(6). - _Ivan Neretin_, Aug 30 2015

%F Sum_{n>=1} 1/a(n)^s = zeta(2*s)*zeta(3*s)/zeta(6*s), s > 1/2 (Golomb, 1970). - _Amiram Eldar_, Oct 02 2022

%e 1 is a term because for every prime p that divides 1, p^2 also divides 1.

%e 2 is not a term since 2 divides 2 but 2^2 does not.

%e 4 is a term because 2 is the only prime that divides 4 and 2^2 does divide 4. - _N. J. A. Sloane_, Jan 16 2022

%p isA001694 := proc(n) for p in ifactors(n)[2] do if op(2,p) = 1 then return false; end if; end do; return true; end proc:

%p A001694 := proc(n) option remember; if n = 1 then 1; else for a from procname(n-1)+1 do if isA001694(a) then return a; end if; end do; end if; end proc:

%p seq(A001694(n),n=1..20) ; # _R. J. Mathar_, Jun 07 2011

%t Join[{1}, Select[ Range@ 1250, Min@ FactorInteger[#][[All, 2]] > 1 &]]

%t (* _Harvey P. Dale_, Sep 18 2011; modified by _Robert G. Wilson v_, Aug 11 2014 *)

%t max = 10^3; Union@ Flatten@ Table[a^2*b^3, {b, max^(1/3)}, {a, Sqrt[max/b^3]}] (* _Robert G. Wilson v_, Aug 11 2014 *)

%t nextPowerfulNumber[n_] := Block[{r = Range[ Floor[1 + n^(1/3)]]^3}, Min@ Select[ Sort[ r*Floor[1 + Sqrt[n/r]]^2], # > n &]]; NestList[ nextPowerfulNumber, 1, 55] (* _Robert G. Wilson v_, Aug 16 2014 *)

%o (PARI) isA001694(n)=n=factor(n)[,2];for(i=1,#n,if(n[i]==1,return(0)));1 \\ _Charles R Greathouse IV_, Feb 11 2011

%o (PARI) list(lim,mn=2)=my(v=List(),t); for(m=1,sqrtnint(lim\1,3), t=m^3; for(n=1,sqrtint(lim\t), listput(v,t*n^2))); Set(v) \\ _Charles R Greathouse IV_, Jul 31 2011; edited Sep 22 2015

%o (PARI) is=ispowerful \\ _Charles R Greathouse IV_, Nov 13 2012

%o (Haskell)

%o a001694 n = a001694_list !! (n-1)

%o a001694_list = filter ((== 1) . a112526) [1..]

%o -- _Reinhard Zumkeller_, Nov 30 2012

%o (Python)

%o from sympy import factorint

%o A001694 = [1]+[n for n in range(2,10**6) if min(factorint(n).values()) > 1]

%o # _Chai Wah Wu_, Aug 14 2014

%o (Python)

%o from math import isqrt

%o from sympy import mobius, integer_nthroot

%o def A001694(n):

%o def squarefreepi(n):

%o return int(sum(mobius(k)*(n//k**2) for k in range(1, isqrt(n)+1)))

%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):

%o c, l = n+x, 0

%o j = isqrt(x)

%o while j>1:

%o k2 = integer_nthroot(x//j**2,3)[0]+1

%o w = squarefreepi(k2-1)

%o c -= j*(w-l)

%o l, j = w, isqrt(x//k2**3)

%o c -= squarefreepi(integer_nthroot(x,3)[0])-l

%o return c

%o return bisection(f,n,n) # _Chai Wah Wu_, Sep 09 2024

%o (Sage)

%o sloane.A001694.list(54) # _Peter Luschny_, Feb 08 2015

%Y Disjoint union of A062503 and A320966.

%Y Cf. A007532 (Powerful numbers, definition (2)), A005934, A005188, A003321, A014576, A023052 (Powerful numbers, definition (3)), A046074, A013929, A076871, A258599, A001248, A112526, A168363, A224866, A261883, A300717.

%Y Cf. A052485 (complement), A076446 (first differences), A376361, A376362.

%K nonn,nice,easy

%O 1,2

%A _N. J. A. Sloane_

%E More terms from _Henry Bottomley_, Mar 16 2000

%E Definition expanded by _Jonathan Sondow_, Jan 03 2016