|
%I M0617 #470 Mar 22 2024 07:35:16
%S 1,2,3,5,6,7,10,11,13,14,15,17,19,21,22,23,26,29,30,31,33,34,35,37,38,
%T 39,41,42,43,46,47,51,53,55,57,58,59,61,62,65,66,67,69,70,71,73,74,77,
%U 78,79,82,83,85,86,87,89,91,93,94,95,97,101,102,103,105,106,107,109,110,111,113
%N Squarefree numbers: numbers that are not divisible by a square greater than 1.
%C 1 together with the numbers that are products of distinct primes.
%C Also smallest sequence with the property that a(m)*a(k) is never a square for k != m. - Ulrich Schimke (ulrschimke(AT)aol.com), Dec 12 2001
%C Numbers k such that there is only one Abelian group with k elements, the cyclic group of order k (the numbers such that A000688(k) = 1). - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 25 2001
%C Numbers k such that A007913(k) > phi(k). - _Benoit Cloitre_, Apr 10 2002
%C a(n) is the smallest m with exactly n squarefree numbers <= m. - _Amarnath Murthy_, May 21 2002
%C k is squarefree <=> k divides prime(k)# where prime(k)# = product of first k prime numbers. - Mohammed Bouayoun (bouyao(AT)wanadoo.fr), Mar 30 2004
%C Numbers k such that omega(k) = Omega(k) = A072047(k). - _Lekraj Beedassy_, Jul 11 2006
%C The LCM of any finite subset is in this sequence. - _Lekraj Beedassy_, Jul 11 2006
%C This sequence and the Beatty Pi^2/6 sequence (A059535) are "incestuous": the first 20000 terms are bounded within (-9, 14). - _Ed Pegg Jr_, Jul 22 2008
%C Let us introduce a function D(n) = sigma_0(n)/2^(alpha(1) + ... + alpha(r)), sigma_0(n) number of divisors of n (A000005), prime factorization of n = p(1)^alpha(1) * ... * p(r)^alpha(r), alpha(1) + ... + alpha(r) is sequence (A086436). Function D(n) splits the set of positive integers into subsets, according to the value of D(n). Squarefree numbers (A005117) has D(n)=1, other numbers are "deviated" from the squarefree ideal and have 0 < D(n) < 1. For D(n)=1/2 we have A048109, for D(n)=3/4 we have A067295. - _Ctibor O. Zizka_, Sep 21 2008
%C Numbers k such that gcd(k,k')=1 where k' is the arithmetic derivative (A003415) of k. - _Giorgio Balzarotti_, Apr 23 2011
%C Numbers k such that A007913(k) = core(k) = k. - _Franz Vrabec_, Aug 27 2011
%C Numbers k such that sqrt(k) cannot be simplified. - _Sean Loughran_, Sep 04 2011
%C Indices m where A057918(m)=0, i.e., positive integers m for which there are no integers k in {1,2,...,m-1} such that k*m is a square. - _John W. Layman_, Sep 08 2011
%C It appears that these are numbers j such that Product_{k=1..j} (prime(k) mod j) = 0 (see Maple code). - _Gary Detlefs_, Dec 07 2011. - This is the same claim as Mohammed Bouayoun's Mar 30 2004 comment above. To see why it holds: Primorial numbers, A002110, a subsequence of this sequence, are never divisible by any nonsquarefree number, A013929, and on the other hand, the index of the greatest prime dividing any n is less than n. Cf. A243291. - _Antti Karttunen_, Jun 03 2014
%C Conjecture: For each n=2,3,... there are infinitely many integers b > a(n) such that Sum_{k=1..n} a(k)*b^(k-1) is prime, and the smallest such an integer b does not exceed (n+3)*(n+4). - _Zhi-Wei Sun_, Mar 26 2013
%C The probability that a random natural number belongs to the sequence is 6/Pi^2, A059956 (see Cesàro reference). - _Giorgio Balzarotti_, Nov 21 2013
%C Booker, Hiary, & Keating give a subexponential algorithm for testing membership in this sequence without factoring. - _Charles R Greathouse IV_, Jan 29 2014
%C Because in the factorizations into prime numbers these a(n) (n >= 2) have exponents which are either 0 or 1 one could call the a(n) 'numbers with a fermionic prime number decomposition'. The levels are the prime numbers prime(j), j >= 1, and the occupation numbers (exponents) e(j) are 0 or 1 (like in Pauli's exclusion principle). A 'fermionic state' is then denoted by a sequence with entries 0 or 1, where, except for the zero sequence, trailing zeros are omitted. The zero sequence stands for a(1) = 1. For example a(5) = 6 = 2^1*3^1 is denoted by the 'fermionic state' [1, 1], a(7) = 10 by [1, 0, 1]. Compare with 'fermionic partitions' counted in A000009. - _Wolfdieter Lang_, May 14 2014
%C From _Vladimir Shevelev_, Nov 20 2014: (Start)
%C The following is an Eratosthenes-type sieve for squarefree numbers. For integers > 1:
%C 1) Remove even numbers, except for 2; the minimal non-removed number is 3.
%C 2) Replace multiples of 3 removed in step 1, and remove multiples of 3 except for 3 itself; the minimal non-removed number is 5.
%C 3) Replace multiples of 5 removed as a result of steps 1 and 2, and remove multiples of 5 except for 5 itself; the minimal non-removed number is 6.
%C 4) Replace multiples of 6 removed as a result of steps 1, 2 and 3 and remove multiples of 6 except for 6 itself; the minimal non-removed number is 7.
%C 5) Repeat using the last minimal non-removed number to sieve from the recovered multiples of previous steps.
%C Proof. We use induction. Suppose that as a result of the algorithm, we have found all squarefree numbers less than n and no other numbers. If n is squarefree, then the number of its proper divisors d > 1 is even (it is 2^k - 2, where k is the number of its prime divisors), and, by the algorithm, it remains in the sequence. Otherwise, n is removed, since the number of its squarefree divisors > 1 is odd (it is 2^k-1).
%C (End)
%C The lexicographically least sequence of integers > 1 such that each entry has an even number of proper divisors occurring in the sequence (that's the sieve restated). - _Glen Whitney_, Aug 30 2015
%C 0 is nonsquarefree because it is divisible by any square. - _Jon Perry_, Nov 22 2014, edited by _M. F. Hasler_, Aug 13 2015
%C The Heinz numbers of partitions with distinct parts. We define the Heinz number of a partition p = [p_1, p_2, ..., p_r] as Product_{j=1..r} prime(j) (concept used by _Alois P. Heinz_ in A215366 as an "encoding" of a partition). For example, for the partition [1, 1, 2, 4, 10] the Heinz number is 2*2*3*7*29 = 2436. The number 30 (= 2*3*5) is in the sequence because it is the Heinz number of the partition [1,2,3]. - _Emeric Deutsch_, May 21 2015
%C It is possible for 2 consecutive terms to be even; for example a(258)=422 and a(259)=426. - _Thomas Ordowski_, Jul 21 2015. [These form a subsequence of A077395 since their product is divisible by 4. - _M. F. Hasler_, Aug 13 2015]
%C There are never more than 3 consecutive terms. Runs of 3 terms start at 1, 5, 13, 21, 29, 33, ... (A007675). - _Ivan Neretin_, Nov 07 2015
%C a(n) = product of row n in A265668. - _Reinhard Zumkeller_, Dec 13 2015
%C Numbers without excess, i.e., numbers k such that A001221(k) = A001222(k). - _Juri-Stepan Gerasimov_, Sep 05 2016
%C Numbers k such that b^(phi(k)+1) == b (mod k) for every integer b. - _Thomas Ordowski_, Oct 09 2016
%C Boreico shows that the set of square roots of the terms of this sequence is linearly independent over the rationals. - _Jason Kimberley_, Nov 25 2016 (reference found by Michael Coons).
%C Numbers k such that A008836(k) = A008683(k). - _Enrique Pérez Herrero_, Apr 04 2018
%C The prime zeta function P(s) "has singular points along the real axis for s=1/k where k runs through all positive integers without a square factor". See Wolfram link. - _Maleval Francis_, Jun 23 2018
%C Numbers k such that A007947(k) = k. - _Kyle Wyonch_, Jan 15 2021
%C The Schnirelmann density of the squarefree numbers is 53/88 (Rogers, 1964). - _Amiram Eldar_, Mar 12 2021
%C Comment from _Isaac Saffold_, Dec 21 2021: (Start)
%C Numbers k such that all groups of order k have a trivial Frattini subgroup [Dummit and Foote].
%C Let the group G have order n. If n is squarefree and n > 1, then G is solvable, and thus by Hall's Theorem contains a subgroup H_p of index p for all p | n. Each H_p is maximal in G by order considerations, and the intersection of all the H_p's is trivial. Thus G's Frattini subgroup Phi(G), being the intersection of G's maximal subgroups, must be trivial. If n is not squarefree, the cyclic group of order n has a nontrivial Frattini subgroup. (End)
%C Numbers for which the squarefree divisors (A206778) and the unitary divisors (A077610) are the same; moreover they are also the set of divisors (A027750). - _Bernard Schott_, Nov 04 2022
%C 0 = A008683(a(n)) - A008836(a(n)) = A001615(a(n)) - A000203(a(n)). - _Torlach Rush_, Feb 08 2023
%D Jean-Marie De Koninck, Ces nombres qui nous fascinent, Entry 165, p. 53, Ellipses, Paris, 2008.
%D Dummit, David S., and Richard M. Foote. Abstract algebra. Vol. 1999. Englewood Cliffs, NJ: Prentice Hall, 1991.
%D Ivan M. Niven and Herbert S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 251.
%D Michael Pohst and Hans J. Zassenhaus, Algorithmic Algebraic Number Theory, Cambridge Univ. Press, page 432.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Daniel Forgues, <a href="/A005117/b005117.txt">Table of n, a(n) for n = 1..60794</a> (first 10000 terms from T. D. Noe)
%H Zenon B. Batang, <a href="https://arxiv.org/abs/2109.10226">Squarefree integers and the abc conjecture</a>, arXiv:2109.10226 [math.GM], 2021.
%H Andrew R. Booker, Ghaith A. Hiary and Jon P. Keating, <a href="https://doi.org/10.1215/00127094-2856619">Detecting squarefree numbers</a>, Duke Mathematical Journal, Vol. 164, No. 2 (2015), pp. 235-275; <a href="https://arxiv.org/abs/1304.6937">arXiv preprint</a>, arXiv:1304.6937 [math.NT], 2013-2015.
%H Iurie Boreico, <a href="https://web.archive.org/web/20190419095544/http://www.math.harvard.edu/hcmr/issues/2.pdf">Linear independence of radicals</a>, The Harvard College Mathematics Review 2(1), 87-92, Spring 2008.
%H Ernesto Cesàro, <a href="https://babel.hathitrust.org/cgi/pt?id=uc1.$c161216&view=1up&seq=207">La serie di Lambert in aritmetica assintotica</a>, Rendiconto della Reale Accademia delle Scienze di Napoli, Serie 2, Vol. 7 (1893), pp. 197-204.
%H Henri Cohen, Francois Dress, and Mohamed El Marraki, <a href="https://projecteuclid.org/euclid.facm/1229618741">Explicit estimates for summatory functions linked to the Möbius μ-function</a>, Functiones et Approximatio Commentarii Mathematici 37 (2007), part 1, pp. 51-63.
%H H. Gent, <a href="/A005117/a005117.pdf">Letter to N. J. A. Sloane</a>, Nov 27 1975.
%H Andrew Granville, <a href="http://www.dms.umontreal.ca/~andrew/PDF/polysq3.pdf">ABC means we can count squarefrees</a>, International Mathematical Research Notices 19 (1998), 991-1009.
%H Pentti Haukkanen, Mika Mattila, Jorma K. Merikoski and Timo Tossavainen, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Tossavainen/tossavainen4.html">Can the Arithmetic Derivative be Defined on a Non-Unique Factorization Domain?</a>, Journal of Integer Sequences, Vol. 16 (2013), Article 13.1.2.
%H Aaron Krowne, <a href="https://planetmath.org/SquarefreeNumber">squarefree number</a>, PlanetMath.org.
%H Louis Marmet, <a href="http://www.marmet.org/louis/sqfgap/">First occurrences of squarefree gaps and an algorithm for their computation</a>.
%H Louis Marmet, <a href="http://arxiv.org/abs/1210.3829">First occurrences of square-free gaps and an algorithm for their computation</a>, arXiv preprint arXiv:1210.3829 [math.NT], 2012.
%H Srinivasa Ramanujan, <a href="http://www.imsc.res.in/~rao/ramanujan/CamUnivCpapers/Cpaper4/page1.htm">Irregular numbers</a>, J. Indian Math. Soc., Vol. 5 (1913), pp. 105-106.
%H Kenneth Rogers, <a href="https://doi.org/10.1090/S0002-9939-1964-0163893-X">The Schnirelmann density of the squarefree integers</a>, Proceedings of the American Mathematical Society, Vol. 15, No. 4 (1964), pp. 515-516.
%H J. A. Scott, <a href="https://www.jstor.org/stable/3621428">Square-freedom revisited</a>, The Mathematical Gazette, Vol. 90, No. 517 (2006), pp. 112-113.
%H Vladimir Shevelev, <a href="http://arxiv.org/abs/1511.03860">Set of all densities of exponentially S-numbers</a>, arXiv preprint arXiv:1511.03860 [math.NT], 2015.
%H O. Trifonov, <a href="http://www.math.bas.bg/infres/MathBalk/MB-03/MB-03-284-295.pdf">On the Squarefree Problem II</a>, Math. Balkanica, Vol. 3 (1989), Fasc. 3-4.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Squarefree.html">Squarefree</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PrimeZetaFunction.html">Prime Zeta Function</a>.
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Squarefree_integer">Squarefree integer</a>.
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>.
%F Limit_{n->oo} a(n)/n = Pi^2/6 (see A013661). - _Benoit Cloitre_, May 23 2002
%F Equals A039956 UNION A056911. - _R. J. Mathar_, May 16 2008
%F A122840(a(n)) <= 1; A010888(a(n)) < 9. - _Reinhard Zumkeller_, Mar 30 2010
%F a(n) = A055229(A062838(n)) and a(n) > A055229(m) for m < A062838(n). - _Reinhard Zumkeller_, Apr 09 2010
%F A008477(a(n)) = 1. - _Reinhard Zumkeller_, Feb 17 2012
%F A055653(a(n)) = a(n); A055654(a(n)) = 0. - _Reinhard Zumkeller_, Mar 11 2012
%F A008966(a(n)) = 1. - _Reinhard Zumkeller_, May 26 2012
%F Sum_{n>=1} 1/a(n)^s = zeta(s)/zeta(2*s). - _Enrique Pérez Herrero_, Jul 07 2012
%F A056170(a(n)) = 0. - _Reinhard Zumkeller_, Dec 29 2012
%F A013928(a(n)+1) = n. - _Antti Karttunen_, Jun 03 2014
%F A046660(a(n)) = 0. - _Reinhard Zumkeller_, Nov 29 2015
%F Equals {1} UNION A000040 UNION A006881 UNION A007304 UNION A046386 UNION A046387 UNION A067885 UNION A123321 UNION A123322 UNION A115343 ... - _R. J. Mathar_, Nov 05 2016
%F |a(n) - n*Pi^2/6| < 0.058377*sqrt(n) for n >= 268293; this result can be derived from Cohen, Dress, & El Marraki, see links. - _Charles R Greathouse IV_, Jan 18 2018
%F From _Amiram Eldar_, Jul 07 2021: (Start)
%F Sum_{n>=1} (-1)^(a(n)+1)/a(n)^2 = 9/Pi^2.
%F Sum_{k=1..n} 1/a(k) ~ (6/Pi^2) * log(n).
%F Sum_{k=1..n} (-1)^(a(k)+1)/a(k) ~ (2/Pi^2) * log(n).
%F (all from Scott, 2006) (End)
%p with(numtheory); a := [ ]; for n from 1 to 200 do if issqrfree(n) then a := [ op(a), n ]; fi; od:
%p t:= n-> product(ithprime(k),k=1..n): for n from 1 to 113 do if(t(n) mod n = 0) then print(n) fi od; # _Gary Detlefs_, Dec 07 2011
%p A005117 := proc(n) option remember; if n = 1 then 1; else for a from procname(n-1)+1 do if numtheory[issqrfree](a) then return a; end if; end do: end if; end proc: # _R. J. Mathar_, Jan 09 2013
%t Select[ Range[ 113], SquareFreeQ] (* _Robert G. Wilson v_, Jan 31 2005 *)
%t Select[Range[150], Max[Last /@ FactorInteger[ # ]] < 2 &] (* Joseph Biberstine (jrbibers(AT)indiana.edu), Dec 26 2006 *)
%t NextSquareFree[n_, k_: 1] := Block[{c = 0, sgn = Sign[k]}, sf = n + sgn; While[c < Abs[k], While[ ! SquareFreeQ@ sf, If[sgn < 0, sf--, sf++]]; If[ sgn < 0, sf--, sf++]; c++]; sf + If[ sgn < 0, 1, -1]]; NestList[ NextSquareFree, 1, 70] (* _Robert G. Wilson v_, Apr 18 2014 *)
%o (Magma) [ n : n in [1..1000] | IsSquarefree(n) ];
%o (PARI) bnd = 1000; L = vector(bnd); j = 1; for (i=1,bnd, if(issquarefree(i),L[j]=i; j=j+1)); L
%o (PARI) {a(n)= local(m,c); if(n<=1,n==1, c=1; m=1; while( c<n, m++; if(issquarefree(m), c++)); m)} /* _Michael Somos_, Apr 29 2005 */
%o (PARI) list(n)=my(v=vectorsmall(n,i,1),u,j); forprime(p=2,sqrtint(n), forstep(i=p^2, n, p^2, v[i]=0)); u=vector(sum(i=1,n,v[i])); for(i=1,n,if(v[i],u[j++]=i)); u \\ _Charles R Greathouse IV_, Jun 08 2012
%o (PARI) for(n=1, 113, if(core(n)==n, print1(n, ", "))); \\ _Arkadiusz Wesolowski_, Aug 02 2016
%o (PARI)
%o S(n) = my(s); forsquarefree(k=1,sqrtint(n),s+=n\k[1]^2*moebius(k)); s;
%o a(n) = my(min=1, max=231, k=0, sc=0); if(n >= 144, min=floor(zeta(2)*n - 5*sqrt(n)); max=ceil(zeta(2)*n + 5*sqrt(n))); while(min <= max, k=(min+max)\2; sc=S(k); if(abs(sc-n) <= sqrtint(n), break); if(sc > n, max=k-1, if(sc < n, min=k+1, break))); while(!issquarefree(k), k-=1); while(sc != n, my(j=1); if(sc > n, j = -1); k += j; sc += j; while(!issquarefree(k), k += j)); k; \\ _Daniel Suteu_, Jul 07 2022
%o (PARI) first(n)=my(v=vector(n),i); forsquarefree(k=1,if(n<268293,(33*n+30)\20,(n*Pi^2/6+0.058377*sqrt(n))\1), if(i++>n, return(v)); v[i]=k[1]); v \\ _Charles R Greathouse IV_, Jan 10 2023
%o (Haskell)
%o a005117 n = a005117_list !! (n-1)
%o a005117_list = filter ((== 1) . a008966) [1..]
%o -- _Reinhard Zumkeller_, Aug 15 2011, May 10 2011
%o (Python)
%o from sympy.ntheory.factor_ import core
%o def ok(n): return core(n, 2) == n
%o print(list(filter(ok, range(1, 114)))) # _Michael S. Branicky_, Jul 31 2021
%o (Python)
%o from itertools import count, islice
%o from sympy import factorint
%o def A005117_gen(startvalue=1): # generator of terms >= startvalue
%o return filter(lambda n:all(x == 1 for x in factorint(n).values()),count(max(startvalue,1)))
%o A005117_list = list(islice(A005117_gen(),20)) # _Chai Wah Wu_, May 09 2022
%Y Complement of A013929. Subsequence of A072774 and A209061.
%Y Characteristic function: A008966 (mu(n)^2, where mu = A008683).
%Y Subsequences: A000040, A002110, A235488.
%Y Cf. A076259 (first differences), A173143 (partial sums), A000688, A003277, A013928, A020753, A020754, A020755, A030059, A030229, A033197, A034444, A039956, A048672, A053797, A057918, A059956, A071403, A072284, A120992, A133466, A136742, A136743, A160764, A243289, A243347, A243348, A243351, A215366, A046660, A265668, A265675.
%Y Cf. A027750, A077610, A206778.
%Y Subsequences: numbers j such that j*a(k) is squarefree where k > 1: A056911 (k = 2), A261034 (k = 3), A274546 (k = 5), A276378 (k = 6).
%K nonn,easy,nice,core
%O 1,2
%A _N. J. A. Sloane_
|
