login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005117 Squarefree numbers (or square-free numbers): numbers that are not divisible by a square greater than 1.
(Formerly M0617)
476
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, 39, 41, 42, 43, 46, 47, 51, 53, 55, 57, 58, 59, 61, 62, 65, 66, 67, 69, 70, 71, 73, 74, 77, 78, 79, 82, 83, 85, 86, 87, 89, 91, 93, 94, 95, 97, 101, 102, 103, 105, 106, 107, 109, 110, 111, 113 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

1 together with the numbers that are products of distinct primes.

Also smallest sequence with the property that a(m)*a(n) is never a square for n <> m. - Ulrich Schimke (ulrschimke(AT)aol.com), Dec 12 2001

Numbers n such that there is only one Abelian group with n elements, the cyclic group of order n (the numbers such that A000688(n) = 1). - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 25 2001

Numbers n such that A007913(n) > phi(n). - Benoit Cloitre, Apr 10 2002

a(n) = smallest m with exactly n squarefree numbers <= m. - Amarnath Murthy, May 21 2002

n is squarefree <=> n divides n# where n# = product of first n prime numbers. - Mohammed Bouayoun (bouyao(AT)wanadoo.fr), Mar 30 2004

Numbers n such that omega(n) = Omega(n) = A072047(n). - Lekraj Beedassy, Jul 11 2006

The lcm of any finite subset is in this sequence. - Lekraj Beedassy, Jul 11 2006

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

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

A122840(a(n)) <= 1; A010888(a(n)) < 9. - Reinhard Zumkeller, Mar 30 2010

a(n) = A055229(A062838(n)) and a(n) > A055229(m) for m < A062838(n). - Reinhard Zumkeller, Apr 09 2010

Numbers n such that gcd(n,n')=1 where n' is the  arithmetic derivative (A003415) of n. - Giorgio Balzarotti, Apr 23 2011

Numbers n such that A007913(n)=core(n)=n. - Franz Vrabec, Aug 27 2011

Numbers n such that sqrt(n) cannot be simplified. - Sean Loughran, Sep 04 2011

Indices where A057918(n)=0, i.e., positive integers m for which there are no integers k in {1,2,...,m-1} such that k*m is aquare. - John W. Layman, Sep 08 2011

It appears that these are numbers n such that product(ithprime(k), k=1..n) mod n = 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 non-squarefree 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

A008477(a(n)) = 1. - Reinhard Zumkeller, Feb 17 2012

A055653(a(n)) = a(n); A055654(a(n)) = 0. - Reinhard Zumkeller, Mar 11 2012

A008966(a(n)) = 1. - Reinhard Zumkeller, May 26 2012

Sum(n>=1, 1/a(n)^s) = Zeta(s)/Zeta(2*s). - Enrique Pérez Herrero, Jul 07 2012

A056170(a(n)) = 0. - Reinhard Zumkeller, Dec 29 2012

A013928(a(n)+1) = n. - Antti Karttunen, Jun 03 2014

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

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

Booker, Hiary, & Keating give a subexponential algorithm for testing membership in this sequence without factoring. - Charles R Greathouse IV, Jan 29 2014

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

REFERENCES

E. Cesàro, La serie di Lambert in aritmetica assintotica, Rend. Acc. Sc. Napoli, 1893

J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 165, p. 53, Ellipses, Paris 2008.

I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 251.

M. Pohst and H. Zassenhaus, Algorithmic Algebraic Number Theory, Cambridge Univ. Press, page 432.

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

LINKS

T. D. Noe and Daniel Forgues, Table of n, a(n) for n = 1..60794 (first 10000 terms from T. D. Noe)

Andrew R. Booker, Ghaith A. Hiary, and Jon P. Keating, Detecting squarefree numbers, (2013)

A. Granville, ABC means we can count squarefrees, International Mathematical Research Notices 19 (1998), 991-1009.

P. Haukkanen, M. Mattila, J. K. Merikoski and T. Tossavainen, Can the Arithmetic Derivative be Defined on a Non-Unique Factorization Domain?, Journal of Integer Sequences, 16 (2013), #13.1.2. - N. J. A. Sloane, Feb 03 2013

A. Krowne, PlanetMath.org, squarefree number

L. Marmet, First occurrences of squarefree gaps and an algorithm for their computation

L. Marmet, First occurrences of square-free gaps and an algorithm for their computation, arXiv preprint arXiv:1210.3829, 2012. [from N. J. A. Sloane, Jan 01 2013]

S. Ramanujan, Irregular numbers, J. Indian Math. Soc. 5 (1913) 105-106.

Eric Weisstein's World of Mathematics, Squarefree

Wikipedia, Squarefree integer

FORMULA

Lim n -> infinity a(n)/n = Pi^2/6. - Benoit Cloitre, May 23 2002

A039956 UNION A056911. - R. J. Mathar, May 16 2008

MAPLE

with(numtheory); a := [ ]; for n from 1 to 200 do if issqrfree(n) then a := [ op(a), n ]; fi; od:

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

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

MATHEMATICA

Select[ Range[ 113], SquareFreeQ[ # ] &] (* Robert G. Wilson v, Jan 31 2005 *)

Select[Range[150], Max[Last /@ FactorInteger[ # ]] < 2 &] (* Joseph Biberstine (jrbibers(AT)indiana.edu), Dec 26 2006 *)

max = 0; a = {}; Do[m = FactorInteger[n]; w = Product[m[[k]][[1]], {k, 1, Length[m]}]; If[w > max, AppendTo[a, n]; max = w], {n, 1, 1000}]; a (* Artur Jasinski, Apr 06 2008 *)

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 *)

PROG

(MAGMA) [ n : n in [1..1000] | IsSquarefree(n) ];

(PARI) bnd = 1000; L = vector(bnd); j = 1; for (i=1, bnd, if(issquarefree(i), L[j]=i:j=j+1)); L

(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 */

(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

(Haskell)

a005117 n = a005117_list !! (n-1)

a005117_list = filter ((== 1) . a008966) [1..]

-- Reinhard Zumkeller, Aug 15 2011, May 10 2011

CROSSREFS

Complement of A013929. Subsequence of A072774 and A209061.

Characteristic function: A008966 (mu(n)^2, where mu = A008683).

Subsequences: A000040, A002110, A235488.

Cf. A076259 (first differences), A173143 (partial sums), A013928, A053797, A243348, A243351, A039956, A056911, A033197, A020753, A020754, A020755, A000688, A003277, A136742, A136743, A072284, A120992, A057918, A133466, A030059, A030229, A160764, A071403, A059956, A048672, A243347, A243289.

Sequence in context: A193304 A076144 * A144338 A077377 A076786 A167171

Adjacent sequences:  A005114 A005115 A005116 * A005118 A005119 A005120

KEYWORD

nonn,easy,nice,core

AUTHOR

N. J. A. Sloane

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified August 21 15:23 EDT 2014. Contains 245856 sequences.