A100112 -id:A100112 - cp's OEIS frontend

A056911 Odd squarefree numbers.

1, 3, 5, 7, 11, 13, 15, 17, 19, 21, 23, 29, 31, 33, 35, 37, 39, 41, 43, 47, 51, 53, 55, 57, 59, 61, 65, 67, 69, 71, 73, 77, 79, 83, 85, 87, 89, 91, 93, 95, 97, 101, 103, 105, 107, 109, 111, 113, 115, 119, 123, 127, 129, 131, 133, 137, 139, 141, 143, 145, 149, 151

Offset: 1

James Sellers, Jul 07 2000

From Daniel Forgues, May 27 2009: (Start)
For any prime p, there are as many squarefree numbers having p as a factor as squarefree numbers not having p as a factor amongst all the squarefree numbers (one-to-one correspondence, both cardinality aleph_0).
E.g. there are as many even squarefree numbers as there are odd squarefree numbers.
For any prime p, the density of squarefree numbers having p as a factor is 1/p of the density of squarefree numbers not having p as a factor.
E.g. the density of even squarefree numbers is 1/p = 1/2 of the density of odd squarefree numbers (which means that 1/(p + 1) = 1/3 of the squarefree numbers are even and p/(p + 1) = 2/3 are odd). As a consequence the n-th even squarefree number is very nearly p = 2 times the n-th odd squarefree number (which means that the n-th even squarefree number is very nearly (p + 1) = 3 times the n-th squarefree number while the n-th odd squarefree number is very nearly (p + 1)/p = 3/2 the n-th squarefree number).
For any prime p, the n-th squarefree number not divisible by p is: n * (1 + 1/p) * zeta(2) + O(n^(1/2)) = n * (1 + 1/p) * (Pi^2 / 6) + O(n^(1/2)) (End)

			The exponents in the prime factorization of 15 are all equal to 1, so 15 appears here. The number 75 does not appear in this sequence, as it is divisible by the square number 25.

Zak Seidov, Table of n, a(n) for n = 1..12000
G. J. O. Jameson, Even and odd square-free numbers, Math. Gazette 94 (2010), 123-127; Author's copy.

Subsequence of A005117 and A036537.
Equals A039956/2.
Cf. A238711 (subsequence).

a056911 n = a056911_list !! (n-1)
a056911_list = filter ((== 1) . a008966) [1,3..]
-- Reinhard Zumkeller, Aug 27 2011

[n: n in [1..151 by 2] | IsSquarefree(n)]; // Bruno Berselli, Mar 03 2011

Select[Range[1,151,2],SquareFreeQ] (* Ant King, Mar 17 2013 *)

is(n)=n%2 && issquarefree(n) \\ Charles R Greathouse IV, Mar 26 2013

list(lim)=my(v=List()); forsquarefree(k=1,lim\1, if(k[1]%2, listput(v,k[1]))); Vec(v) \\ Charles R Greathouse IV, Jan 14 2025

A123314(A100112(a(n))) > 0. - Reinhard Zumkeller, Sep 25 2006
a(n) = n * (3/2) * zeta(2) + O(n^(1/2)) = n * (Pi^2 / 4) + O(n^(1/2)). - Daniel Forgues, May 27 2009
A008474(a(n)) * A000035(a(n)) = 1. - Reinhard Zumkeller, Aug 27 2011
Sum_{n>=1} 1/a(n)^s = ((2^s)* zeta(s))/((1+2^s)*zeta(2*s)). - Enrique Pérez Herrero, Sep 15 2012 [corrected by Amiram Eldar, Sep 26 2023]

A248663 Binary encoding of the prime factors of the squarefree part of n.

Original entry on oeis.org

0, 1, 2, 0, 4, 3, 8, 1, 0, 5, 16, 2, 32, 9, 6, 0, 64, 1, 128, 4, 10, 17, 256, 3, 0, 33, 2, 8, 512, 7, 1024, 1, 18, 65, 12, 0, 2048, 129, 34, 5, 4096, 11, 8192, 16, 4, 257, 16384, 2, 0, 1, 66, 32, 32768, 3, 20, 9, 130, 513, 65536, 6, 131072, 1025, 8, 0, 36, 19

Offset: 1

Peter Kagey, Jan 11 2015

The binary digits of a(n) encode the prime factorization of A007913(n), where the i-th digit from the right is 1 if and only if prime(i) divides A007913(n), otherwise 0. - Robert Israel, Jan 12 2015
Old name: a(1) = 0; a(A000040(n)) = 2^(n-1), and a(n*m) = a(n) XOR a(m).
XOR is the bitwise exclusive or operation (A003987).
a(k^2) = 0 for a natural number k.
Equivalently, the i-th binary digit from the right is 1 iff prime(i) divides n an odd number of times, otherwise zero. - Ethan Beihl, Oct 15 2016
When a polynomial with nonnegative integer coefficients is encoded with the prime factorization of n (e.g., as in A206296, A260443, with scheme explained in A206284), then A048675(n) gives the evaluation of that polynomial at x=2. This sequence is otherwise similar, except the polynomial is evaluated over the field GF(2), which implies also that all its coefficients are essentially reduced modulo 2. - Antti Karttunen, Dec 11 2015
Squarefree numbers (A005117) give the positions k where a(k) = A048675(k). - Antti Karttunen, Oct 29 2016
From Peter Munn, Jun 07 2021: (Start)
When we encode polynomials with nonnegative integer coefficients as described by Antti Karttunen above, polynomial addition is represented by integer multiplication, multiplication is represented by A297845(.,.), and this sequence represents a surjective semiring homomorphism to polynomials in GF(2)[x] (encoded as described in A048720). The mapping of addition operations by this homomorphism is part of the sequence definition: "a(n*m) = a(n) XOR a(m)". The mapping of multiplication is given by a(A297845(n, k)) = A048720(a(n), a(k)).
In a related way, A329329 defines a representation of a different set of polynomials as positive integers, namely polynomials in GF(2)[x,y].
Let P_n(x,y) denote the polynomial represented, as in A329329, by n >= 1. If 0 is substituted for y in P_n(x,y), we get a polynomial P'_n(x,y) (in which y does not appear, of course) that is equivalent to a polynomial P'_n(x) in GF(2)[x]. a(n) is the integer encoding of P'_n(x) (described in A048720).
Viewed as above, this sequence represents another surjective homomorphism, a homomorphism between polynomial rings, with A329329(.,.)/A059897(.,.) and A048720(.,.)/A003987(.,.) as the respective ring operations.
a(n) can be composed as a(n) = A048675(A007913(n)) and the effect of the A007913(.) component corresponds to different operations on the respective polynomial domains of the two homomorphisms described above. In the first homomorphism, coefficients are reduced modulo 2; in the second, 0 is substituted for y. This is illustrated in the examples.
(End)

			a(3500) = a(2^2 * 5^3 * 7) = a(2) XOR a(2) XOR a(5) XOR a(5) XOR a(5) XOR a(7) = 1 XOR 1 XOR 4 XOR 4 XOR 4 XOR 8 = 0b0100 XOR 0b1000 = 0b1100 = 12.
From _Peter Munn_, Jun 07 2021: (Start)
The examples in the table below illustrate the homomorphisms (between polynomial structures) represented by this sequence.
The staggering of the rows is to show how the mapping n -> A007913(n) -> A048675(A007913(n)) = a(n) relates to the encoded polynomials, as not all encodings are relevant at each stage.
For an explanation of each polynomial encoding, see the sequence referenced in the relevant column heading. (Note also that A007913 generates squarefree numbers, and with these encodings, all squarefree numbers represent equivalent polynomials in N[x] and GF(2)[x,y].)
                     |<-----    encoded polynomials    ----->|
  n  A007913(n) a(n) |         N[x]    GF(2)[x,y]    GF(2)[x]|
                     |Cf.:  A206284       A329329     A048720|
--------------------------------------------------------------
  24                            x+3         x+y+1
          6                     x+1           x+1
                  3                                       x+1
--------------------------------------------------------------
  36                           2x+2          xy+y
          1                       0             0
                  0                                         0
--------------------------------------------------------------
  60                        x^2+x+2       x^2+x+y
         15                   x^2+x         x^2+x
                  6                                     x^2+x
--------------------------------------------------------------
  90                       x^2+2x+1      x^2+xy+1
         10                   x^2+1         x^2+1
                  5                                     x^2+1
--------------------------------------------------------------
This sequence is a left inverse of A019565. A019565(.) maps a(n) to A007913(n) for all n, effectively reversing the second stage of the mapping from n to a(n) shown above. So, with the encodings used here, A019565(.) represents each of two injective homomorphisms that map polynomials in GF(2)[x] to equivalent polynomials in N[x] and GF(2)[x,y] respectively.
(End)

Peter Kagey, Table of n, a(n) for n = 1..5000
Eric Weisstein's World of Mathematics, Squarefree Part
Wikipedia, Polynomial ring
Index entries for sequences operating on GF(2)[X]-polynomials

Cf. A000040, A000079, A000720, A005117, A020639, A032742, A048672, A055396, A100112, A206284.
A048675 composed with A007913. A007814 composed with A225546.
A homomorphism from A297845/A003991 and from A329329/A059897 to A048720/A003987, mapping A206296 to A168081, A260443 to A264977, A265408 to A265407, A275734 to A275808, A276076 to A276074, A283477 to A006068.
A left inverse of A019565.
Other sequences used to express relationship between terms of this sequence: A003961, A007913, A331590, A334747.
Cf. also A099884, A277330.
A087207 is the analogous sequence with OR.
A277417 gives the positions where coincides with A277333.
A000290 gives the positions of zeros.

import Data.Bits (xor)
a248663 = foldr (xor) 0 . map (\i -> 2^(i - 1)) . a112798_row
-- Peter Kagey, Sep 16 2016

f:= proc(n)
local F,f;
F:= select(t -> t[2]::odd, ifactors(n)[2]);
add(2^(numtheory:-pi(f[1])-1), f = F)
end proc:
seq(f(i),i=1..100); # Robert Israel, Jan 12 2015

a[1] = 0; a[n_] := a[n] = If[PrimeQ@ n, 2^(PrimePi@ n - 1), BitXor[a[#], a[n/#]] &@ FactorInteger[n][[1, 1]]]; Array[a, 66] (* Michael De Vlieger, Sep 16 2016 *)

A248663(n) = vecsum(apply(p -> 2^(primepi(p)-1),factor(core(n))[,1])); \\ Antti Karttunen, Feb 15 2021

from sympy import factorint, primepi
from sympy.ntheory.factor_ import core
def a048675(n):
    f=factorint(n)
    return 0 if n==1 else sum([f[i]*2**(primepi(i) - 1) for i in f])
def a(n): return a048675(core(n))
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Jun 21 2017

require 'prime'
def f(n)
  a = 0
  reverse_primes = Prime.each(n).to_a.reverse
  reverse_primes.each do |prime|
    a <<= 1
    while n % prime == 0
      n /= prime
      a ^= 1
    end
  end
  a
end
(Scheme, with memoizing-macro definec)
(definec (A248663 n) (cond ((= 1 n) 0) ((= 1 (A010051 n)) (A000079 (- (A000720 n) 1))) (else (A003987bi (A248663 (A020639 n)) (A248663 (A032742 n)))))) ;; Where A003987bi computes bitwise-XOR as in A003987.
;; Alternatively:
(definec (A248663 n) (cond ((= 1 n) 0) (else (A003987bi (A000079 (- (A055396 n) 1)) (A248663 (A032742 n))))))
;; Antti Karttunen, Dec 11 2015

a(1) = 0; for n > 1, if n is a prime, a(n) = 2^(A000720(n)-1), otherwise a(A020639(n)) XOR a(A032742(n)). [After the definition.] - Antti Karttunen, Dec 11 2015
For n > 1, this simplifies to: a(n) = 2^(A055396(n)-1) XOR a(A032742(n)). [Where A055396(n) gives the index of the smallest prime dividing n and A032742(n) gives the largest proper divisor of n. Cf. a similar formula for A048675.]
Other identities and observations. For all n >= 0:
a(n) = A048672(A100112(A007913(n))). - Peter Kagey, Dec 10 2015
From Antti Karttunen, Dec 11 2015, Sep 19 & Oct 27 2016, Feb 15 2021: (Start)
a(n) = a(A007913(n)). [The result depends only on the squarefree part of n.]
a(n) = A048675(A007913(n)).
a(A206296(n)) = A168081(n).
a(A260443(n)) = A264977(n).
a(A265408(n)) = A265407(n).
a(A275734(n)) = A275808(n).
a(A276076(n)) = A276074(n).
a(A283477(n)) = A006068(n).
(End)
From Peter Munn, Jan 09 2021 and Apr 20 2021: (Start)
a(n) = A007814(A225546(n)).
a(A019565(n)) = n; A019565(a(n)) = A007913(n).
a(A003961(n)) = 2 * a(n).
a(A297845(n, k)) = A048720(a(n), a(k)).
a(A329329(n, k)) = A048720(a(n), a(k)).
a(A059897(n, k)) = A003987(a(n), a(k)).
a(A331590(n, k)) = a(n) + a(k).
a(A334747(n)) = a(n) + 1.
(End)

New name from Peter Munn, Nov 01 2023

A100113 a(n) = n if n <= 2, otherwise (smallest squarefree number m not occurring earlier such that gcd(m, a(n-1)) > 1).

Original entry on oeis.org

1, 2, 6, 3, 15, 5, 10, 14, 7, 21, 30, 22, 11, 33, 39, 13, 26, 34, 17, 51, 42, 35, 55, 65, 70, 38, 19, 57, 66, 46, 23, 69, 78, 58, 29, 87, 93, 31, 62, 74, 37, 111, 102, 82, 41, 123, 105, 77, 91, 119, 85, 95, 110, 86, 43, 129, 114, 94, 47, 141, 138, 106, 53, 159, 165, 115, 130

Offset: 1

Reinhard Zumkeller, Nov 07 2004

nonn

a(A100112(n)) and A100114(A100112(n)) define a pair of inverse permutations of the squarefree numbers: a(A100112(A100114(n))) = A100114(A100112(a(n))) = A005117(n);
A100115(n) = if n is squarefree then a(A100112(n)), otherwise n.
Comments from N. J. A. Sloane, Oct 29 2020: (Start)
An alternative definition is that this is the lexicographically earliest infinite sequence of distinct positive squarefree numbers with the property that gcd(a(n), a(n-1)) > 1 for n >= 3.
Described in this way, this is a squarefree version of the EKG sequence A064413, and it is easy to modify the proof that that sequence is a permutation of the positive integers so as to show that the present sequence is a permutation of the positive squarefree numbers, as claimed in the first comment.
Conjecture: With the three exceptions p = 2, 5, 13, and 31, when a prime p appears it is preceded by 2*p and followed by 3*p.
(End)

Scott R. Shannon, Table of n, a(n) for n = 1..10000 (terms 1..623 from N. J. A. Sloane)
Eric Weisstein's World of Mathematics, Squarefree

Cf. A005117, A064413, A100112, A100114.

A251391 Indices of squarefree numbers in A098550.

Original entry on oeis.org

1, 2, 3, 7, 8, 9, 10, 13, 15, 16, 17, 20, 21, 22, 23, 24, 25, 28, 30, 32, 34, 35, 36, 38, 39, 41, 43, 44, 45, 47, 49, 51, 53, 56, 59, 60, 61, 62, 63, 64, 68, 70, 72, 73, 74, 77, 78, 79, 80, 81, 85, 86, 87, 88, 89, 90, 95, 96, 98, 99, 100, 101, 103, 105, 109

Offset: 1

Reinhard Zumkeller, Dec 02 2014

nonn

A008966(A098550(a(n))) = 1; A100112(A098550(a(n))) > 0;

A098550(a(n)) = A005117(n).

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A098550, A005117, A008966, A100112, A251239 (subsequence).

a251391 n = a251391_list !! (n-1)
a251391_list = filter ((== 1) . a008966 . fromIntegral . a098550) [1..]

A123314 Number of times the n-th squarefree number occurs as maximal greatest common divisor of pairs of distinct squarefree numbers.

Original entry on oeis.org

4, 0, 2, 3, 0, 5, 0, 2, 2, 0, 3, 3, 3, 2, 0, 6, 0, 3, 0, 2, 3, 0, 3, 2, 0, 2, 3, 0, 5, 0, 4, 3, 3, 3, 2, 0, 2, 4, 0, 3, 0, 2, 3, 0, 3, 3, 0, 3, 0, 5, 0, 2, 2, 0, 2, 3, 3, 2, 0, 3, 5, 3, 0, 2, 3, 0, 3, 3, 0, 2, 3, 0, 5, 0, 3, 0, 5, 3, 2, 0, 3, 5, 0, 2, 0, 2, 3, 0, 2, 4, 0, 3, 5, 0, 3, 2, 0, 3, 2, 3, 2, 0, 6, 0, 4

Offset: 1

Reinhard Zumkeller, Sep 25 2006

nonn

a(n) > 0 iff A005117(n) is an odd squarefree number: a(A100112(A056911(n)))>0;

a(n) = 0 iff A005117(n) is an even squarefree number: a(A100112(A039956(n)))=0.

a(n) = #{k: A123313(k) = A005117(n)}.

A158819 a(n) = (number of squarefree numbers <= n) minus round(n/zeta(2)).

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 2, 1, 2, 2, 1, 1, 1, 2, 2, 1, 1, 1, 2, 1, 1, 2, 2, 2, 2, 1, 2, 1, 1, 2, 2, 2, 2, 1, 1, 0, 1, 1, 1, 1, 1

Offset: 1

Daniel Forgues, Mar 27 2009

sign

Race between the number of squarefree numbers and round(n/zeta(2)).

First term < 0: a(172) = -1.

G. H. Hardy and S. Ramanujan, The normal number of prime factors of a number n, Q. J. Math., 48 (1917), pp. 76-92.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth edition, Clarendon Press, 1979, pp. 269-270.

Daniel Forgues, Table of n, a(n) for n=1..100000
Andrew Granville, ABC allows us to count squarefrees, International Mathematics Research Notices, Vol. 1998, No. 19 (1998), pp. 991-1109; alternative link.

Cf. A008966 (1 if n is squarefree, else 0).
Cf. A013928 (number of squarefree numbers < n).
Cf. A100112 (if n is the k-th squarefree number then k else 0).
Cf. A057627 (number of nonsquarefree numbers not exceeding n).
Cf. A005117 (squarefree numbers).
Cf. A013929 (nonsquarefree numbers).
Cf. A013661 (zeta(2)).

seq[lim_] := Accumulate[Boole[SquareFreeQ /@ Range[lim]]] - Round[Range[lim]/Zeta[2]]; seq[105] (* Amiram Eldar, Jan 20 2025 *)

Since zeta(2) = Sum_{i>=1} 1/(i^2) = (Pi^2)/6, we get:
a(n) = A013928(n+1) - n/Sum_{i>=1} 1/(i^2) = O(sqrt(n));
a(n) = A013928(n+1) - 6*n/(Pi^2) = O(sqrt(n)).

cp's OEIS Frontend

A102510 If n is squarefree then A090705(A100112(n)) else n.

Views

Author

Keywords

Comments

Links

Crossrefs

A100114 a(n) = the unique squarefree m such that A100113(A100112(m))=A005117(n).

Views

Author

Keywords

Comments

Links

A100115 If n is squarefree then A100113(A100112(n)) else n.

Views

Author

Keywords

Comments

Links

Crossrefs

A100116 If n is squarefree then A100114(A100112(n)) else n.

Views

Author

Keywords

Comments

Links

Crossrefs

A056911 Odd squarefree numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

PARI

Formula

A248663 Binary encoding of the prime factors of the squarefree part of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Ruby

Formula

Extensions

A100113 a(n) = n if n <= 2, otherwise (smallest squarefree number m not occurring earlier such that gcd(m, a(n-1)) > 1).

Views

Author

Keywords

Comments

Links

Crossrefs

A251391 Indices of squarefree numbers in A098550.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

A123314 Number of times the n-th squarefree number occurs as maximal greatest common divisor of pairs of distinct squarefree numbers.

Views

Author

Keywords