A358677 -id:A358677 - cp's OEIS frontend

A340316 Square array A(n,k), n>=1, k>=1, read by antidiagonals, where row n is the increasing list of all squarefree numbers with n primes.

2, 3, 6, 5, 10, 30, 7, 14, 42, 210, 11, 15, 66, 330, 2310, 13, 21, 70, 390, 2730, 30030, 17, 22, 78, 462, 3570, 39270, 510510, 19, 26, 102, 510, 3990, 43890, 570570, 9699690, 23, 33, 105, 546, 4290, 46410, 690690, 11741730, 223092870

Offset: 1

Peter Dolland, Jan 04 2021

This is a permutation of all squarefree numbers > 1.

			First six rows and columns:
      2     3     5     7    11    13
      6    10    14    15    21    22
     30    42    66    70    78   102
    210   330   390   462   510   546
   2310  2730  3570  3990  4290  4830
  30030 39270 43890 46410 51870 53130

Cf. A005117 (squarefree numbers), A072047 (number of prime factors), A340313 (indexing), A078840 (all natural numbers, not only squarefree).
Rows n=1..10: A000040, A006881, A007304, A046386, A046387, A067885, A123321, A123322, A115343, A281222.
Columns k=1..2: A002110, A306237.
Main diagonal gives A340467.
Cf. A358677.

a340316 n k = a340316_row n !! (k-1)
a340316_row n = [a005117_list !! k | k <- [0..], a072047_list !! k == n]

from math import prod, isqrt
from sympy import prime, primerange, integer_nthroot, primepi
def A340316_T(n,k):
    if n == 1: return prime(k)
    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)))
    def f(x): return int(k+x-sum(primepi(x//prod(c[1] for c in a))-a[-1][0] for a in g(x,0,1,1,n)))
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    return bisection(f) # Chai Wah Wu, Aug 31 2024

A(A072047(n), A340313(n)) = A005117(n) for n > 1.

A276176 Consider the race between primes, semiprimes, 3-almost primes, ... k-almost primes; sequence indicates when one overtakes another to give a new race leader.

Original entry on oeis.org

2, 26, 31, 34, 15526, 151165506068, 151165506073, 151165506089, 151165506093, 151165506295, 151165506410, 151165506518, 151165506526, 151165506658, 151165506665, 151165506711, 151165506819, 151165506970, 151165506994, 151165507256, 151165507259, 151165507265

Offset: 1

Jonathan Vos Post and Robert G. Wilson v, Oct 09 2016

A "k-almost prime" is a number which is the product of exactly k primes.
Let pi_k(n) be the number of k-almost primes less than or equal to n. In 1909, on page 211 of the Handbuch, Edmund G. H. Landau stated that pi_k(n) ~ (n/log n)*(log log n^(k-1))/(k-1)! for all k >= 0.
Because of this fact, eventually the semiprimes will outnumber the primes; they do starting at 34. Likewise the 3-almost primes will outnumber the semiprimes and they do starting at 15526.
The terms from a(6) = 151165506068 to a(170) = 151165607026 correspond to counts of 4-almost and 3-almost primes overtaking each other multiple times. - Giovanni Resta, Aug 17 2018

			a(1) = 2 since beginning with the natural numbers (A000027) the race is even with no group in the lead. But at 2, we encounter our first member (1 is unity and is not a member of any group here) which is a prime and therefore the primes take the lead with 2.
a(2) = 34 which is a semiprime. pi_1(34) = 11 and pi_2(34) = 12. This is the first time that the semiprimes overtake the primes.

Edmund Georg Hermann Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Band I, B. G. Teubner, Leipzig u. Berlin, or Chelsea Publishing, NY 1953, or Vol. 1, Teubner, Leipzig; third edition: Chelsea, New York 1974.

Giovanni Resta, Table of n, a(n) for n = 1..170
Edmund Georg Hermann Landau, Handbuch der Lehre von der Verteilung der Primzahlen, page 211, (4); University of Michigan Historical Math Collection.

Cf. A243906, A273381, A274123, A358677, A359242 (restricted to squarefree numbers).

k = 1; lst = {}; tf = 0; p1 = 0; p2 = 0; While[k < 100001, If[PrimeOmega@k == 1, p1++]; If[PrimeOmega@k == 2, p2++]; If[p1 > p2 && tf == 0, tf++; AppendTo[lst, k]]; If[p2 > p1 && tf == 1, tf--; AppendTo[lst, k]]; k++]; lst
(* cross check using *) AlmostPrimePi[k_Integer, n_] := Module[{a, i}, a[0] = 1; If[k == 1, PrimePi[n], Sum[PrimePi[n/Times @@ Prime[ Array[a, k - 1]]] - a[k - 1] + 1, Evaluate[ Sequence @@ Table[{a[i], a[i - 1], PrimePi[(n/Times @@ Prime[Array[a, i - 1]])^(1/(k - i + 1))]}, {i, k - 1}]] ]]]; (* Eric W. Weisstein, Feb 07 2006 *)
(* as an example *) AlmostPrimePi[2, 15526] => 3986 whereas AlmostPrimePi[3, 15526] => 3987.

It seems plausible that 0.8 * log(A284411(m) - 1) <= log(a(n)) <= log(A284411(m)) in the instances where the overtaking concerns m-almost-primes and (m-1)-almost-primes. - Peter Munn, Aug 03 2023

a(6)-a(22) from Giovanni Resta, Aug 17 2018

Name clarified by Peter Munn, Dec 31 2022

cp's OEIS Frontend

A340316 Square array A(n,k), n>=1, k>=1, read by antidiagonals, where row n is the increasing list of all squarefree numbers with n primes.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Haskell

Python

Formula

A276176 Consider the race between primes, semiprimes, 3-almost primes, ... k-almost primes; sequence indicates when one overtakes another to give a new race leader.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions