A107079 Minimal number of squared primes in a squarefree gap of length n.

1, 2, 3, 4, 4, 5, 6, 7, 7, 7, 8, 9, 9, 10, 11, 12, 12, 13, 13, 14, 14, 15, 16, 17, 17, 17, 18, 18, 18, 19, 20, 21, 21, 22, 23, 24, 24, 25, 26, 27, 27, 28, 29, 30, 30, 30, 31, 32, 32, 32, 32, 33, 33, 34, 34, 35, 35, 36, 37, 38, 38, 39, 40, 40, 40, 41, 42, 43, 43, 44, 45, 46, 46, 47

Offset: 1

Author

Paul Barry, May 10 2005

Keywords

• nonn

Links

• Antti Karttunen, Table of n, a(n) for n = 1..100000
• Louis Marmet, First occurrences of squarefree gaps and an algorithm for their computation
• Louis Marmet, First occurrences of square-free gaps and an algorithm for their computation, arXiv preprint arXiv:1210.3829 [math.NT], 2012. - _N. J. A. Sloane_, Jan 01 2013

Crossrefs

One more than A013928. A left inverse of A005117.

Cf. A045882, A107078.

Programs

Mathematica

a[n_] := Sum[Boole[SquareFreeQ[k]], {k, 1, n-1}] + 1;
Array[a, 100] (* Jean-François Alcover, Sep 11 2018, from A013928 *)

PARI

A107079(n)=1+sum(k=1,n-1,bitand(moebius(k),1)) \\ Charles R Greathouse IV, Sep 22 2008

Python

from math import isqrt
from sympy import mobius
def A107079(n): return 1+sum(mobius(k)*((n-1)//k**2) for k in range(1,isqrt(n-1)+1)) # Chai Wah Wu, Jan 03 2024

Formula

a(n) = sum{k=0..n-1, moebius_mu(n-k-1) mod 2}.

a(n) = A013928(n+1) + A107078(n).

From Antti Karttunen, Oct 07 2016: (Start)

a(n) = 1 + A013928(n). [Cf. Charles R Greathouse IV's PARI-program.]

For all n >= 1, a(A005117(n)) = n. (End)

Extensions

New definition from Charles R Greathouse IV, Sep 22 2008