A078840 -id:A078840 - cp's OEIS frontend

A116429 The number of n-almost primes less than or equal to 9^n, starting with a(0)=1.

1, 4, 26, 181, 1095, 6416, 35285, 187929, 973404, 4934952, 24628655, 121375817, 592337729, 2868086641, 13798982719, 66043675287, 314715355786, 1494166794434, 7071357084444, 33374079939405

Offset: 0

Robert G. Wilson v, Feb 10 2006

Cf. A078840, A078841, A078842, A116432, A078843, A116426, A078844, A116427, A078845, A116428, A116429, A116430, A078846, A116431.

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 *)
Table[ AlmostPrimePi[n, 9^n], {n, 13}]

almost_prime_count(N, k) = if(k==1, return(primepi(N))); (f(m, p, k, j=0) = my(c=0, s=sqrtnint(N\m, k)); if(k==2, forprime(q=p, s, c += primepi(N\(m*q))-j; j += 1), forprime(q=p, s, c += f(m*q, q, k-1, j); j += 1)); c); f(1, 2, k);
a(n) = if(n == 0, 1, almost_prime_count(9^n, n)); \\ Daniel Suteu, Jul 10 2023

a(14)-a(16) from Donovan Johnson, Oct 01 2010

a(16) corrected and a(17)-a(19) from Daniel Suteu, Jul 10 2023

A116431 The number of n-almost primes less than or equal to 12^n, starting with a(0)=1.

Original entry on oeis.org

1, 5, 48, 434, 3695, 29165, 218283, 1569995, 10950776, 74621972, 499495257, 3297443264, 21533211312, 139411685398, 896352197825, 5730605551626, 36465861350230

Offset: 0

Robert G. Wilson v, Feb 10 2006

Cf. A078840, A078841, A078842, A116432, A078843, A116426, A078844, A116427, A078845, A116428, A116429, A116430, A078846, A116431.

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 *)
Table[ AlmostPrimePi[n, 12^n], {n, 12}]

almost_prime_count(N, k) = if(k==1, return(primepi(N))); (f(m, p, k, j=0) = my(c=0, s=sqrtnint(N\m, k)); if(k==2, forprime(q=p, s, c += primepi(N\(m*q))-j; j += 1), forprime(q=p, s, c += f(m*q, q, k-1, j); j += 1)); c); f(1, 2, k);
a(n) = if(n == 0, 1, almost_prime_count(12^n, n)); \\ Daniel Suteu, Jul 10 2023

from math import isqrt, prod
from sympy import primerange, integer_nthroot, primepi
def A116431(n):
    if n<=1: return 4*n+1
    def g(x,a,b,c,m): yield from (((d,) for d in enumerate(primerange(b,isqrt(x//c)+1),a)) if m==2 else (((a2,b2),)+d for a2,b2 in enumerate(primerange(b,integer_nthroot(x//c,m)[0]+1),a) for d in g(x,a2,b2,c*b2,m-1)))
    return int(sum(primepi(12**n//prod(c[1] for c in a))-a[-1][0] for a in g(12**n,0,1,1,n))) # Chai Wah Wu, Sep 28 2024

a(13)-a(14) from Donovan Johnson, Oct 01 2010

a(15)-a(16) from Daniel Suteu, Jul 10 2023

A116432 The number of n-almost primes less than or equal to e^n, starting with a(0)=1.

Original entry on oeis.org

1, 1, 2, 4, 5, 7, 12, 18, 24, 37, 54, 74, 107, 159, 218, 315, 450, 634, 888, 1269, 1782, 2496, 3520, 4933, 6899, 9681, 13555, 18888, 26407, 36855, 51352, 71526, 99654, 138608, 192708, 267833, 372107, 516420, 716816, 994191, 1378195, 1909694

Offset: 0

Robert G. Wilson v, Feb 10 2006

nonn

Cf. A078840, A078841, A078842, A116432, A078843, A116426, A078844, A116427, A078845, A116428, A116429, A116430, A078846, A116431.

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 *)
Table[ AlmostPrimePi[n, E^n], {n, 42}]

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.

Original entry on oeis.org

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.

A122943 Odd numbers n ordered by n/2^BigOmega(n), where BigOmega(n) is the number of prime divisors of n with repetition.

Original entry on oeis.org

1, 3, 9, 5, 27, 7, 15, 81, 21, 11, 45, 25, 13, 243, 63, 33, 135, 17, 35, 75, 19, 39, 729, 23, 189, 49, 99, 405, 51, 105, 55, 225, 57, 29, 117, 31, 125, 65, 2187, 69, 567, 147, 37, 297, 1215, 153, 77, 315, 41, 165, 675, 85, 171, 43, 87, 175, 351, 91, 93, 375, 47, 95, 195

Offset: 1

Franklin T. Adams-Watters, Oct 24 2006

nonn

This is the limit of the sequence of largest odd factors of the k-almost primes as k -> infinity.
The location of 3^k in this sequence is A078843(k).
Removing 1 and prime numbers from this sequence gives A374074. - Friedjof Tellkamp, Nov 27 2024

T. D. Noe, Table of n, a(n) for n = 1..1065
Almost primes, sequences related to

Cf. A001222, A101695, A078841, A078840, A000265, A007814, A374074.

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}]]]]] (* from Eric Weisstein, Feb 07 2006 *); AlmostPrime[k_, n_] := Block[{e = Floor[ Log[2, n] + k], a, b}, a = 2^e; Do[b = 2^p; While[ AlmostPrimePi[k, a] < n, a = a + b]; a = a - b/2, {p, e, 0, -1}]; a + b/2]; f[n_] := Block[{ kap = AlmostPrime[20, n]}, kap / 2^IntegerExponent[ kap, 2]]; Array[f, 64] (* or *)
f[n_] := n/2^PrimeOmega[n]; Take[2 Ordering[ Table[ f[ 2n - 1], {n, 1100}]] - 1, 63] (* Robert G. Wilson v, Feb 08 2011 *)
f[n_] := n/2^PrimeOmega[n]; nn=9; t = Select[Table[{f[2 n - 1], 2 n - 1}, {n, 3^nn/2 + 1}], #[[1]] <= f[3^nn] &]; Transpose[Sort[t]][[2]]

A101695(n) = a(n) * 2^(n - BigOmega(a(n))). a(n) = A101695(n) / 2^A007814(A101695(n)) = A000265(A101695(n)).

A207790 Permutation of positive numbers. See comments.

Original entry on oeis.org

1, 2, 4, 3, 8, 5, 6, 7, 16, 11, 9, 13, 12, 17, 10, 19, 32, 23, 14, 29, 18, 31, 15, 37, 24, 41, 21, 43, 20, 47, 22, 53, 64, 59, 25, 61, 27, 67, 26, 71, 36, 73, 33, 79, 28, 83, 34, 89, 48, 97, 35, 101, 30, 103, 38, 107, 40, 109, 39, 113, 42, 127, 46, 131, 128, 137, 49, 139, 44, 149, 51, 151

Offset: 1

Vladimir Shevelev and Peter J. C. Moses, Feb 20 2012

nonn

a(1)=1; on places 2,4,6,8,... we put primes (A000040); on places 3,7,11,15,... we put products of two primes (A001358); on places 5,13,21,29,... we put products of three primes (A014612); on places 9,25,41,57,... we put products of four primes (A014613); on places 17,49,81,... we put products of five primes (A014614); etc.
Primes with the index not exceeding n have density 1/2, semiprimes have density 1/4, etc.
By our system, here and in  A207800, A207801, A207802 we used the order: a(1)=1; the first appearance  of a new kind of numbers in places of the form 2^k+1, k=0,1,2,..., with  period of the appearance 2^{k+1}.

Ivan Neretin, Table of n, a(n) for n = 1..8192

Cf. A057114.

mx = 72; a = Array[1 &, mx]; cnt = mx - 1; offs = Table[2^(i - 1) + 1, {i, 1, mx}]; n = 1; While[cnt > 0, n++; idx = PrimeOmega[n]; pos = offs[[idx]]; If[pos > mx, Continue[]]; offs[[idx]] += 2^idx; a[[pos]] = n; cnt--]; a (* Ivan Neretin, May 06 2015 *)

For n>1, a(n) = A078840(A249725(n-1)). - Ivan Neretin, Apr 30 2016

A109636 Let T(n,k) be the n-th k-almost prime. Then a(n) = T(n,k) such that k is minimal and for all m>0, T(n,k+m) >= 2^m * T(n,k).

Original entry on oeis.org

2, 3, 9, 10, 27, 28, 30, 81, 84, 88, 90, 100, 104, 243, 252, 264, 270, 272, 280, 300, 304, 312, 729, 736, 756, 784, 792, 810, 816, 840, 880, 900, 912, 928, 936, 992, 1000, 1040, 2187, 2208, 2268, 2352, 2368, 2376, 2430, 2448, 2464, 2520, 2624

Offset: 1

Yury V. Shlapak (shlapak(AT)imp.kiev.ua), Aug 04 2005

nonn

If one writes the k-almost primes in rows (one row for each k), one observes that there exists a P_{k_0}(n) such that P_{k_0+1}(n) = 2P_{k_0}(n) and for each k>=k_0, P_{k+1}(n)=2P_{k}(n). Then a(n) = P_{k_0}(n). In other words in the columns the values double from row k_0 on. - Peter Pein (petsie(AT)dordos.net), Mar 16 2007

Chai Wah Wu, Table of n, a(n) for n = 1..10000
Wikipedia, k-almost prime numbers.

Cf. A000040, A001358, A014612, A014613, A014614, A078840.

a[n_] := Module[{p = Prime[Range[n]], pal}, pal = Transpose /@ Partition[NestList[Take[Union[Flatten[Outer[Times, #1, p]]], Length[#1]] &, p, n], 2, 1]; Complement @@ Transpose[Cases[pal, {k_, kk_} /; kk == 2*k, {2}]]] ; a[50] (* Peter Pein, Nov 10 2007 *)

from itertools import count
# uses function A078840_T from A078840
def A109636(n):
    a = A078840_T(1,n)
    for k in count(2):
        b = A078840_T(k,n)
        if b==(a<<1):
            return a
        a = b # Chai Wah Wu, Mar 30 2025

Edited by Max Alekseyev, Mar 16 2007
More terms from Peter Pein, Mar 16 2007
Definition corrected by Chai Wah Wu, Mar 30 2025

A209934 a(n) is the first value to occur consecutively in the sequence b_n defined by p_2k(b_n(k)) = p_k(n)^2, k=1,2,3,..., where p_k(n) is the n-th k-almost prime.

Original entry on oeis.org

1, 3, 8, 12, 23, 26, 32, 66, 68, 78, 83, 106, 116, 169, 181, 201, 210, 216, 234, 273, 282, 296, 427, 436, 501, 504, 513, 538, 547, 583, 655, 688, 711, 738, 751, 851, 866, 947, 1065, 1088, 1155, 1274, 1277, 1285, 1350, 1369, 1389, 1456, 1594, 1615, 1702, 1734

Offset: 1

Daniel Tisdale, Mar 15 2012

nonn

A k-almost prime has exactly k prime factors, repetitions included.
Conjecture: Each sequence b_n repeats indefinitely. (Example: for n=3, b_n = 9, 8, 8, 8, 8, 8, ....  It looks like b_3(k) is 8 for all k > 1.)
The conjecture follows from the formula that uses A078843 below (and the strict monotonicity of A078843). However the first repeated value is not for every n the value that repeats indefinitely. For example a(8) = b_8(2) = b_8(3) = 66, but b_8(k) = 64 for k >= 4. - Peter Munn, Aug 05 2019

			for k = 1, 2, 3, 4, 5, 6, ...:
p_k(3) = 5, 9, 18, 36, 72, 144, ... (the 3rd k-almost prime);
p_k(3)^2 = 25, 81, 324, 1296, 5184, 20736, ...;
b_3(k) = 9, 8, 8, 8, 8, 8, ... (index in the 2k-almost primes);
so since b_3(3) = b_3(2) = 8, a(3) = 8.

Cf. A058933, A078840, A078843, A091538.

get_p(m,k) = {local(i,n);i=0;n=1;while(iA209934(n) = {local(m,k,k_old);m=3;k_old=get_k(2,get_p(1,n)^2);k=get_k(4,get_p(2,n)^2);while(kMichael B. Porter, Mar 20 2012

From Peter Munn, Aug 05 2019: (Start)
b_n(k) = A058933(A078840(k,n)^2).
a(n) = b_n(min {k : b_n(k) = b_n(k+1)}).
If n < A078843(k+1) and b_n(k) < A078843(2k+1) then b_n(i) = b_n(k) for i >= k.
(End)

Edited, correcting the subscripting, by Peter Munn, Aug 04 2019

A385315 Smallest number k such that both k^n - 1 and k^n + 1 have n prime factors, counted with repetitions.

Original entry on oeis.org

4, 12, 66, 920, 26, 132, 79, 17958, 53, 693, 4181, 122160, 29791, 32318, 971

Offset: 1

Jean-Marc Rebert, Aug 12 2025

			a(1) = 4, because 4^1 - 1 = 3 and 4^1 + 1 = 5, and no lesser number has this property.
See the Links section for more examples.

Jean-Marc Rebert, Factorizations of k^n-1 and k^n+1

Cf. A001222, A001358, A014612, A078840, A385591, A368162, A368163.

a(n) = my(k=2, kn=k^n); while ((bigomega(kn-1)!=n) || (bigomega(kn+1)!=n), k++;kn=k^n); k; \\ Michel Marcus, Aug 18 2025

a(n) >= max(A368162(n), A368163(n)). - Daniel Suteu, Sep 02 2025

A131175 Table, read by rows, of coefficients of characteristic polynomials of almost prime matrices.

Original entry on oeis.org

1, -2, 1, -8, 1, -26, -4, 1, -66, -36, 1, -174, -196, 1, -398, -676, 1, -878, -3044, 1, -2174, -6852, -192, 1, -4862, -18628, -704, 1, -10494, -45508, -1216, 1, -22014, -141252, -6336, 1, -47614, -315332, -10432, 1, -100862, -858052, -55488, 1, -225278, -1878980, -245952

Offset: 1

Jonathan Vos Post, Sep 24 2007

Because the first column of A is a column vector of powers of 2, the determinant (for n>1) is always 0. Hence the rank is always (for n>1) less than n. A[n.n] = n-th n-almost prime A101695. The second column of the table is the negative of the trace of the matrices.

			A_1 = [2], with determinant = 2 and characteristic polynomial = x-2, with coefficients (1, -2) so a(a) = 1 and a(2) = -2.
A_2 =
[2.3]
[4.6]
with determinant = 0, polynomial x^2 - 8x, so the coefficients are (1, -8), hence a(3) = 1 and a(4) = -8.
A_3 =
[2..3..5]
[4..6..9]
[8.12.18]
with determinant = 0, polynomial = x^3 - 26x^2, -4x, so coefficients are (1, -26, -4), hence a(5) = 1, a(6) = -26, a(7) = -4.

Cf. A000040, A001358, A014612, A014613, A014614, A101695.

A078840 := proc(n,m) local p,k ; k := 1 ; p := 2^n ; while k < m do p := p+1 ; while numtheory[bigomega](p) <> n do p := p+1 ; od; k := k+1 ; od: RETURN(p) ; end: A131175 := proc(nrow,showall) local A,row,col,pol,T,a ; A := linalg[matrix](nrow,nrow) ; for row from 1 to nrow do for col from 1 to nrow do if row = col then A[row,col] := x-A078840(row,col) ; else A[row,col] := -A078840(row,col) ; fi ; od: od: pol := linalg[det](A) ; T := [] ; for col from nrow to 0 by -1 do a := coeftayl(pol,x=0,col) ; if a <> 0 or showall then T := [op(T),a] ; fi ; od; RETURN(T) ; end: for n from 1 to 15 do print(op(A131175(n,false))) ; od: # R. J. Mathar, Oct 26 2007

Row n of the table consists of the coefficients of x^n, x^n-1, ... of the characteristic polynomial of the n X n matrix A whose first row is the first n primes (1-almost primes) (A000040), 2nd row is the first n semiprimes (2-almost primes) A001358, 3rd row is the first n 3-almost primes A014612.

Corrected and extended by R. J. Mathar, Oct 26 2007

cp's OEIS Frontend

A116429 The number of n-almost primes less than or equal to 9^n, starting with a(0)=1.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI

Extensions

A116431 The number of n-almost primes less than or equal to 12^n, starting with a(0)=1.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

A116432 The number of n-almost primes less than or equal to e^n, starting with a(0)=1.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

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

A122943 Odd numbers n ordered by n/2^BigOmega(n), where BigOmega(n) is the number of prime divisors of n with repetition.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A207790 Permutation of positive numbers. See comments.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A109636 Let T(n,k) be the n-th k-almost prime. Then a(n) = T(n,k) such that k is minimal and for all m>0, T(n,k+m) >= 2^m * T(n,k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Extensions

A209934 a(n) is the first value to occur consecutively in the sequence b_n defined by p_2k(b_n(k)) = p_k(n)^2, k=1,2,3,..., where p_k(n) is the n-th k-almost prime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

Extensions