# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/
Search: id:a005117
Showing 1-1 of 1
%I A005117 M0617 #488 Jul 23 2024 10:53:44
%S A005117 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 A005117 39,41,42,43,46,47,51,53,55,57,58,59,61,62,65,66,67,69,70,71,73,74,77,
%U A005117 78,79,82,83,85,86,87,89,91,93,94,95,97,101,102,103,105,106,107,109,110,111,113
%N A005117 Squarefree numbers: numbers that are not divisible by a square greater than 1.
%C A005117 1 together with the numbers that are products of distinct primes.
%C A005117 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 A005117 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 A005117 Numbers k such that A007913(k) > phi(k). - _Benoit Cloitre_, Apr 10 2002
%C A005117 a(n) is the smallest m with exactly n squarefree numbers <= m. - _Amarnath Murthy_, May 21 2002
%C A005117 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 A005117 Numbers k such that omega(k) = Omega(k) = A072047(k). - _Lekraj Beedassy_, Jul 11 2006
%C A005117 The LCM of any finite subset is in this sequence. - _Lekraj Beedassy_, Jul 11 2006
%C A005117 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 A005117 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 A005117 Numbers k such that gcd(k,k')=1 where k' is the arithmetic derivative (A003415) of k. - _Giorgio Balzarotti_, Apr 23 2011
%C A005117 Numbers k such that A007913(k) = core(k) = k. - _Franz Vrabec_, Aug 27 2011
%C A005117 Numbers k such that sqrt(k) cannot be simplified. - _Sean Loughran_, Sep 04 2011
%C A005117 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 A005117 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 A005117 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 A005117 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 A005117 Booker, Hiary, & Keating give a subexponential algorithm for testing membership in this sequence without factoring. - _Charles R Greathouse IV_, Jan 29 2014
%C A005117 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 A005117 From _Vladimir Shevelev_, Nov 20 2014: (Start)
%C A005117 The following is an Eratosthenes-type sieve for squarefree numbers. For integers > 1:
%C A005117 1) Remove even numbers, except for 2; the minimal non-removed number is 3.
%C A005117 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 A005117 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 A005117 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 A005117 5) Repeat using the last minimal non-removed number to sieve from the recovered multiples of previous steps.
%C A005117 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 A005117 (End)
%C A005117 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 A005117 0 is nonsquarefree because it is divisible by any square. - _Jon Perry_, Nov 22 2014, edited by _M. F. Hasler_, Aug 13 2015
%C A005117 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 A005117 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 A005117 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 A005117 a(n) = product of row n in A265668. - _Reinhard Zumkeller_, Dec 13 2015
%C A005117 Numbers without excess, i.e., numbers k such that A001221(k) = A001222(k). - _Juri-Stepan Gerasimov_, Sep 05 2016
%C A005117 Numbers k such that b^(phi(k)+1) == b (mod k) for every integer b. - _Thomas Ordowski_, Oct 09 2016
%C A005117 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 A005117 Numbers k such that A008836(k) = A008683(k). - _Enrique Pérez Herrero_, Apr 04 2018
%C A005117 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 A005117 Numbers k such that A007947(k) = k. - _Kyle Wyonch_, Jan 15 2021
%C A005117 The Schnirelmann density of the squarefree numbers is 53/88 (Rogers, 1964). - _Amiram Eldar_, Mar 12 2021
%C A005117 Comment from _Isaac Saffold_, Dec 21 2021: (Start)
%C A005117 Numbers k such that all groups of order k have a trivial Frattini subgroup [Dummit and Foote].
%C A005117 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 A005117 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 A005117 0 = A008683(a(n)) - A008836(a(n)) = A001615(a(n)) - A000203(a(n)). - _Torlach Rush_, Feb 08 2023
%C A005117 From _Robert D. Rosales_, May 20 2024: (Start)
%C A005117 Numbers n such that mu(n) != 0, where mu(n) is the Möbius function (A008683).
%C A005117 Solutions to the equation Sum_{d|n} mu(d)*sigma(d) = mu(n)*n, where sigma(n) is the sum of divisors function (A000203). (End)
%C A005117 a(n) is the smallest root of x = 1 + Sum_{k=1..n-1} floor(sqrt(x/a(k))) greater than a(n-1). - _Yifan Xie_, Jul 10 2024
%D A005117 Jean-Marie De Koninck, Ces nombres qui nous fascinent, Entry 165, p. 53, Ellipses, Paris, 2008.
%D A005117 Dummit, David S., and Richard M. Foote. Abstract algebra. Vol. 1999. Englewood Cliffs, NJ: Prentice Hall, 1991.
%D A005117 Ivan M. Niven and Herbert S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 251.
%D A005117 Michael Pohst and Hans J. Zassenhaus, Algorithmic Algebraic Number Theory, Cambridge Univ. Press, page 432.
%D A005117 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005117 Daniel Forgues, Table of n, a(n) for n = 1..60794 (first 10000 terms from T. D. Noe)
%H A005117 Zenon B. Batang, Squarefree integers and the abc conjecture, arXiv:2109.10226 [math.GM], 2021.
%H A005117 Andrew R. Booker, Ghaith A. Hiary and Jon P. Keating, Detecting squarefree numbers, Duke Mathematical Journal, Vol. 164, No. 2 (2015), pp. 235-275; arXiv preprint, arXiv:1304.6937 [math.NT], 2013-2015.
%H A005117 Iurie Boreico, Linear independence of radicals, The Harvard College Mathematics Review 2(1), 87-92, Spring 2008.
%H A005117 Ernesto Cesà ro, La serie di Lambert in aritmetica assintotica, Rendiconto della Reale Accademia delle Scienze di Napoli, Serie 2, Vol. 7 (1893), pp. 197-204.
%H A005117 Henri Cohen, Francois Dress, and Mohamed El Marraki, Explicit estimates for summatory functions linked to the Möbius μ-function, Functiones et Approximatio Commentarii Mathematici 37 (2007), part 1, pp. 51-63.
%H A005117 H. Gent, Letter to N. J. A. Sloane, Nov 27 1975.
%H A005117 Andrew Granville, ABC means we can count squarefrees, International Mathematical Research Notices 19 (1998), 991-1009.
%H A005117 Pentti Haukkanen, Mika Mattila, Jorma K. Merikoski and Timo Tossavainen, Can the Arithmetic Derivative be Defined on a Non-Unique Factorization Domain?, Journal of Integer Sequences, Vol. 16 (2013), Article 13.1.2.
%H A005117 Aaron Krowne, squarefree number, PlanetMath.org.
%H A005117 Louis Marmet, First occurrences of squarefree gaps and an algorithm for their computation.
%H A005117 Louis Marmet, First occurrences of square-free gaps and an algorithm for their computation, arXiv preprint arXiv:1210.3829 [math.NT], 2012.
%H A005117 Srinivasa Ramanujan, Irregular numbers, J. Indian Math. Soc., Vol. 5 (1913), pp. 105-106.
%H A005117 Kenneth Rogers, The Schnirelmann density of the squarefree integers, Proceedings of the American Mathematical Society, Vol. 15, No. 4 (1964), pp. 515-516.
%H A005117 J. A. Scott, Square-freedom revisited, The Mathematical Gazette, Vol. 90, No. 517 (2006), pp. 112-113.
%H A005117 Vladimir Shevelev, Set of all densities of exponentially S-numbers, arXiv preprint arXiv:1511.03860 [math.NT], 2015.
%H A005117 O. Trifonov, On the Squarefree Problem II, Math. Balkanica, Vol. 3 (1989), Fasc. 3-4.
%H A005117 Eric Weisstein's World of Mathematics, Squarefree.
%H A005117 Eric Weisstein's World of Mathematics, Prime Zeta Function.
%H A005117 Wikipedia, Squarefree integer.
%H A005117 Index entries for "core" sequences.
%F A005117 Limit_{n->oo} a(n)/n = Pi^2/6 (see A013661). - _Benoit Cloitre_, May 23 2002
%F A005117 Equals A039956 UNION A056911. - _R. J. Mathar_, May 16 2008
%F A005117 A122840(a(n)) <= 1; A010888(a(n)) < 9. - _Reinhard Zumkeller_, Mar 30 2010
%F A005117 a(n) = A055229(A062838(n)) and a(n) > A055229(m) for m < A062838(n). - _Reinhard Zumkeller_, Apr 09 2010
%F A005117 A008477(a(n)) = 1. - _Reinhard Zumkeller_, Feb 17 2012
%F A005117 A055653(a(n)) = a(n); A055654(a(n)) = 0. - _Reinhard Zumkeller_, Mar 11 2012
%F A005117 A008966(a(n)) = 1. - _Reinhard Zumkeller_, May 26 2012
%F A005117 Sum_{n>=1} 1/a(n)^s = zeta(s)/zeta(2*s). - _Enrique Pérez Herrero_, Jul 07 2012
%F A005117 A056170(a(n)) = 0. - _Reinhard Zumkeller_, Dec 29 2012
%F A005117 A013928(a(n)+1) = n. - _Antti Karttunen_, Jun 03 2014
%F A005117 A046660(a(n)) = 0. - _Reinhard Zumkeller_, Nov 29 2015
%F A005117 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 A005117 |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 A005117 From _Amiram Eldar_, Jul 07 2021: (Start)
%F A005117 Sum_{n>=1} (-1)^(a(n)+1)/a(n)^2 = 9/Pi^2.
%F A005117 Sum_{k=1..n} 1/a(k) ~ (6/Pi^2) * log(n).
%F A005117 Sum_{k=1..n} (-1)^(a(k)+1)/a(k) ~ (2/Pi^2) * log(n).
%F A005117 (all from Scott, 2006) (End)
%p A005117 with(numtheory); a := [ ]; for n from 1 to 200 do if issqrfree(n) then a := [ op(a), n ]; fi; od:
%p A005117 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 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 A005117 Select[ Range[ 113], SquareFreeQ] (* _Robert G. Wilson v_, Jan 31 2005 *)
%t A005117 Select[Range[150], Max[Last /@ FactorInteger[ # ]] < 2 &] (* Joseph Biberstine (jrbibers(AT)indiana.edu), Dec 26 2006 *)
%t A005117 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 *)
%t A005117 Select[Range[250], MoebiusMu[#] != 0 &] (* _Robert D. Rosales_, May 20 2024 *)
%o A005117 (Magma) [ n : n in [1..1000] | IsSquarefree(n) ];
%o A005117 (PARI) bnd = 1000; L = vector(bnd); j = 1; for (i=1,bnd, if(issquarefree(i),L[j]=i; j=j+1)); L
%o A005117 (PARI) {a(n)= local(m,c); if(n<=1,n==1, c=1; m=1; while( c