cp's OEIS Frontend

A001694 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).

%I A001694 M3325 N1335 #216 Aug 04 2025 10:13:53
%S A001694 1,4,8,9,16,25,27,32,36,49,64,72,81,100,108,121,125,128,144,169,196,
%T A001694 200,216,225,243,256,288,289,324,343,361,392,400,432,441,484,500,512,
%U A001694 529,576,625,648,675,676,729,784,800,841,864,900,961,968,972,1000
%N A001694 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 A001694 Numbers of the form a^2*b^3, a >= 1, b >= 1.
%C A001694 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 A001694 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 A001694 This sequence is closed under multiplication. The primitive elements are A168363. - _Franklin T. Adams-Watters_, May 30 2011
%C A001694 Complement of A052485. - _Reinhard Zumkeller_, Sep 16 2011
%C A001694 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 A001694 a(10^n): 1, 49, 3136, 253472, 23002083, 2200079025, 215523459072, 21348015504200, 2125390162618116, ... . - _Robert G. Wilson v_, Aug 15 2014
%C A001694 a(m) mod prime(n) > 0 for m < A258599(n); a(A258599(n)) = A001248(n) = prime(n)^2. - _Reinhard Zumkeller_, Jun 06 2015
%C A001694 From _Des MacHale_, Mar 07 2021: (Start)
%C A001694 A number m is powerful if and only if |R/Z(R)| = m, for some finite non-commutative ring R.
%C A001694 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 A001694 Numbers n such that Sum_{k=1..n} phi(gcd(n,k))*mu(gcd(n,k)) > 0. - _Richard L. Ollerton_, May 09 2021
%D A001694 G. E. Hardy and M. V. Subbarao, Highly powerful numbers, Congress. Numer. 37 (1983), 277-307.
%D A001694 Aleksandar Ivić, The Riemann Zeta-Function, Wiley, NY, 1985, see p. 407.
%D A001694 Richard A. Mollin, Quadratics, CRC Press, 1996, Section 1.6.
%D A001694 Aine NiShe, Commutativity and Generalisations in Finite Groups, Ph.D. Thesis, University College Cork, 2000.
%D A001694 Paulo Ribenboim, Meine Zahlen, meine Freunde, 2009, Springer, 9.1 Potente Zahlen, pp. 241-247.
%D A001694 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001694 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A001694 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 A001694 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 A001694 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 A001694 Chris Bispels, Matthew Cohen, Joshua Harrington, Joshua Lowrance, Kaelyn Pontes, Leif Schaumann, and Tony W. H. Wong, <a href="https://arxiv.org/abs/2507.16135">A further investigation on covering systems with odd moduli</a>, arXiv:2507.16135 [math.NT], 2025. See p. 3.
%H A001694 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 A001694 Chris K. Caldwell, <a href="https://t5k.org/glossary/page.php?sort=PowerfulNumber">Powerful Numbers</a>.
%H A001694 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 A001694 Tsz Ho Chan, <a href="https://arxiv.org/abs/2503.21485">A note on three consecutive powerful numbers</a>, arXiv:2503.21485 [math.NT], 2025.
%H A001694 Jean-Marie De Koninck, Nicolas Doyon, and Florian 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 A001694 Paul Erdős and George 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 A001694 Solomon W. Golomb, <a href="http://www.jstor.org/stable/2317020">Powerful numbers</a>, Amer. Math. Monthly, Vol. 77 (1970), 848-852.
%H A001694 K. Schneider, PlanetMath.org, <a href="https://planetmath.org/squarefullnumber">Squarefull Number</a>.
%H A001694 Vladimir Shevelev, <a href="http://dx.doi.org/10.4064/aa8395-5-2016">S-exponential numbers</a>, Acta Arithmetica, Vol. 175(2016), 385-395.
%H A001694 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 A001694 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PowerfulNumber.html">Powerful Number</a>.
%H A001694 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Squareful.html">Squareful</a>.
%H A001694 Wikipedia, <a href="http://en.wikipedia.org/wiki/Powerful_number">Powerful number</a>.
%H A001694 <a href="/index/Pow#powerful">Index entries for sequences related to powerful numbers</a>.
%F A001694 A112526(a(n)) = 1. - _Reinhard Zumkeller_, Sep 16 2011
%F A001694 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 A001694 a(n) = A224866(n) - 1. - _Reinhard Zumkeller_, Jul 23 2013
%F A001694 Sum_{n>=1} 1/a(n) = zeta(2)*zeta(3)/zeta(6). - _Ivan Neretin_, Aug 30 2015
%F A001694 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 A001694 1 is a term because for every prime p that divides 1, p^2 also divides 1.
%e A001694 2 is not a term since 2 divides 2 but 2^2 does not.
%e A001694 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 A001694 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 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 A001694 seq(A001694(n),n=1..20) ; # _R. J. Mathar_, Jun 07 2011
%t A001694 Join[{1}, Select[ Range@ 1250, Min@ FactorInteger[#][[All, 2]] > 1 &]]
%t A001694 (* _Harvey P. Dale_, Sep 18 2011; modified by _Robert G. Wilson v_, Aug 11 2014 *)
%t A001694 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 A001694 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 A001694 (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 A001694 (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 A001694 (PARI) is=ispowerful \\ _Charles R Greathouse IV_, Nov 13 2012
%o A001694 (Haskell)
%o A001694 a001694 n = a001694_list !! (n-1)
%o A001694 a001694_list = filter ((== 1) . a112526) [1..]
%o A001694 -- _Reinhard Zumkeller_, Nov 30 2012
%o A001694 (Python)
%o A001694 from sympy import factorint
%o A001694 A001694 = [1]+[n for n in range(2,10**6) if min(factorint(n).values()) > 1]
%o A001694 # _Chai Wah Wu_, Aug 14 2014
%o A001694 (Python)
%o A001694 from math import isqrt
%o A001694 from sympy import mobius, integer_nthroot
%o A001694 def A001694(n):
%o A001694     def squarefreepi(n):
%o A001694         return int(sum(mobius(k)*(n//k**2) for k in range(1, isqrt(n)+1)))
%o A001694     def bisection(f,kmin=0,kmax=1):
%o A001694         while f(kmax) > kmax: kmax <<= 1
%o A001694         while kmax-kmin > 1:
%o A001694             kmid = kmax+kmin>>1
%o A001694             if f(kmid) <= kmid:
%o A001694                 kmax = kmid
%o A001694             else:
%o A001694                 kmin = kmid
%o A001694         return kmax
%o A001694     def f(x):
%o A001694         c, l = n+x, 0
%o A001694         j = isqrt(x)
%o A001694         while j>1:
%o A001694             k2 = integer_nthroot(x//j**2,3)[0]+1
%o A001694             w = squarefreepi(k2-1)
%o A001694             c -= j*(w-l)
%o A001694             l, j = w, isqrt(x//k2**3)
%o A001694         c -= squarefreepi(integer_nthroot(x,3)[0])-l
%o A001694         return c
%o A001694     return bisection(f,n,n) # _Chai Wah Wu_, Sep 09 2024
%o A001694 (Sage)
%o A001694 sloane.A001694.list(54) # _Peter Luschny_, Feb 08 2015
%Y A001694 Disjoint union of A062503 and A320966.
%Y A001694 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 A001694 Cf. A052485 (complement), A076446 (first differences), A376361, A376362.
%K A001694 nonn,nice,easy
%O A001694 1,2
%A A001694 _N. J. A. Sloane_
%E A001694 More terms from _Henry Bottomley_, Mar 16 2000
%E A001694 Definition expanded by _Jonathan Sondow_, Jan 03 2016