cp's OEIS Frontend

A356683 a(n) is the smallest positive k such that the count of squarefree numbers <= k that have n prime factors is equal to the count of squarefree numbers <= k that have n-1 prime factors (and the count is positive).

%I A356683 #51 Jan 31 2025 17:23:48
%S A356683 2,39,1279786,8377774397163159586
%N A356683 a(n) is the smallest positive k such that the count of squarefree numbers <= k that have n prime factors is equal to the count of squarefree numbers <= k that have n-1 prime factors (and the count is positive).
%e A356683 The first two squarefree numbers are 1 and 2; 1 has 0 prime factors and 2 has 1 prime factor, so a(1)=2.
%e A356683 At k=39, in the interval [1..k], there are 12 squarefree numbers with 1 prime factor (i.e., 12 primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37), and 12 squarefree numbers with 2 prime factors (i.e., 6, 10, 14, 15, 21, 22, 26, 33, 34, 35, 38, 39). k=39 is the smallest such positive number for which these two counts are the same (and are positive), so a(2)=39.
%e A356683 At k=1279786, the interval [1..k] includes 265549 squarefree numbers with 2 prime factors and the same number of squarefree numbers with 3 prime factors, and there is no smaller positive number k that has this property (where the counts are positive), so a(3)=1279786. There are 75 numbers with this property, the last one being 1281378.
%e A356683 At k=8377774397163159586, the interval [1..k] includes 1356557942402075858 squarefree numbers with 3 prime factors and the same number of squarefree numbers with 4 prime factors, and there is no smaller positive number k that has this property (where the counts are positive), so a(4)=8377774397163159586. There are 14 numbers with this property, the last one being 8377774397163162544. - _Henri Lifchitz_, Jan 31 2025
%o A356683 (PARI) a(n) = my(nbm = 0, nbn = 0); for (k=1, oo, if (issquarefree(k), my(o=omega(k)); if (o==n, nbn++); if (o==n-1, nbm++); if (nbm && (nbn==nbm), return(k)))); \\ _Michel Marcus_, Nov 25 2022
%o A356683 (Python)
%o A356683 from itertools import count
%o A356683 from math import prod, isqrt
%o A356683 from sympy import primerange, integer_nthroot, primepi
%o A356683 def A356683(n):
%o A356683     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 A356683     def f(k,n): return sum(primepi(k//prod(c[1] for c in a))-a[-1][0] for a in g(k,0,1,1,n)) if n>1 else primepi(k)
%o A356683     return 2 if n==1 else next(k for k in count(1) if (x:=f(k,n-1))>0 and x==f(k,n)) # _Chai Wah Wu_, Aug 31 2024
%Y A356683 Cf. A005117, A072047.
%Y A356683 Cf. 1 to 5 distinct primes: A000040, A006881, A007304, A046386, A046387.
%Y A356683 Cf. 6 to 10 distinct primes: A067885, A123321, A123322, A115343, A281222.
%Y A356683 Cf. A340316.
%K A356683 nonn,bref,hard,more
%O A356683 1,1
%A A356683 _Jon E. Schoenfield_, Nov 22 2022
%E A356683 a(4) from _Henri Lifchitz_, Jan 31 2025