cp's OEIS Frontend

A340313 The n-th squarefree number is the a(n)-th squarefree number having its number of primes.

%I A340313 #28 Aug 31 2024 12:30:57
%S A340313 1,1,2,3,1,4,2,5,6,3,4,7,8,5,6,9,7,10,1,11,8,9,10,12,11,12,13,2,14,13,
%T A340313 15,14,16,15,16,17,17,18,18,19,3,19,20,4,20,21,21,22,5,22,23,23,24,25,
%U A340313 26,24,27,28,29,30,25,26,6,27,7,31,28,29,8,32,30,9
%N A340313 The n-th squarefree number is the a(n)-th squarefree number having its number of primes.
%C A340313 The sequence gives the column index of A005117(n) in the array A340316 and may be understood as a complementary addition to A072047 giving the row index.
%H A340313 David A. Corneth, <a href="/A340313/b340313.txt">Table of n, a(n) for n = 1..10000</a>
%H A340313 Alois P. Heinz, <a href="/A340313/a340313.jpg">Plot of n, a(n) for n = 1..1000000</a>
%F A340313 a(n) = #{x|x <= n, A072047(x) = A072047(n)}.
%e A340313 {x|x <= 6, A072047(x) = A072047(6) = 1} = {2,3,4,6}, therefore a(6) = 4.
%e A340313 {x|x <= 28, A072047(x) = A072047(28) = 3} = {19,28}, therefore a(28) = 2.
%p A340313 with(numtheory):
%p A340313 b:= proc(n) option remember; local k; if n=1 then 1 else
%p A340313       for k from 1+b(n-1) while not issqrfree(k) do od; k fi
%p A340313     end:
%p A340313 p:= proc() 0 end:
%p A340313 a:= proc(n) option remember; local h; a(n-1);
%p A340313       h:= bigomega(b(n)); p(h):= p(h)+1;
%p A340313     end: a(0):=0:
%p A340313 seq(a(n), n=1..100);  # _Alois P. Heinz_, Jan 06 2021
%t A340313 b[n_] := b[n] = Module[{k}, If[n == 1, 1,
%t A340313      For[k = 1 + b[n - 1], !SquareFreeQ[k], k++]; k]];
%t A340313 p[_] = 0;
%t A340313 a[n_] := a[n] = Module[{h}, a[n - 1];
%t A340313      h = PrimeOmega[b[n]]; p[h] = p[h]+1];
%t A340313 a[0] = 0;
%t A340313 Table[a[n], {n, 1, 100}] (* _Jean-François Alcover_, Mar 28 2022, after _Alois P. Heinz_ *)
%o A340313 (Haskell)
%o A340313 a340313 n = a340313_list !! (n-1)
%o A340313 a340313_list = repetitions a072047_list
%o A340313     where
%o A340313     repetitions [] = []
%o A340313     repetitions (a:as) = 1 : h a as (repetitions as)
%o A340313     h _ [] _ = []
%o A340313     h b (c:cs) (r:rs) = (if c == b then succ else id) r : h b cs rs
%o A340313 (PARI) first(n) = {v = vector(5); n--; res = vector(n); t = 0; for(i = 2, oo, f = factor(i)[,2]; if(vecmax(f) == 1, if(#f > #v, v = concat(v, vector(#f - #v)) ); t++; v[#f]++; res[t] = v[#f]; if(t >= n, return(concat(1, res)) ) ) ) } \\ _David A. Corneth_, Jan 07 2021
%o A340313 (Python)
%o A340313 from math import isqrt, prod
%o A340313 from sympy import primerange, integer_nthroot, mobius, primenu, primepi
%o A340313 def A340313(n):
%o A340313     if n == 1: return 1
%o A340313     def g(x,a,b,c,m): yield from (((d,) for d in enumerate(primerange(b+1,isqrt(x//c)+1),a+1)) if m==2 else (((a2,b2),)+d for a2,b2 in enumerate(primerange(b+1,integer_nthroot(x//c,m)[0]+1),a+1) for d in g(x,a2,b2,c*b2,m-1)))
%o A340313     def f(x): return n+x-sum(mobius(k)*(x//k**2) for k in range(1, isqrt(x)+1))
%o A340313     def bisection(f,kmin=0,kmax=1):
%o A340313         while f(kmax) > kmax: kmax <<= 1
%o A340313         while kmax-kmin > 1:
%o A340313             kmid = kmax+kmin>>1
%o A340313             if f(kmid) <= kmid:
%o A340313                 kmax = kmid
%o A340313             else:
%o A340313                 kmin = kmid
%o A340313         return kmax
%o A340313     kmax = bisection(f)
%o A340313     return int(sum(primepi(kmax//prod(c[1] for c in a))-a[-1][0] for a in g(kmax,0,1,1,m)) if (m:=primenu(kmax)) > 1 else primepi(kmax)) # _Chai Wah Wu_, Aug 31 2024
%Y A340313 Cf. A001221, A001222, A005117 (squarefree numbers), A058933, A067003, A072047 (number of prime factors), A340316 (squarefree numbers array).
%K A340313 nonn
%O A340313 1,3
%A A340313 _Peter Dolland_, Jan 04 2021