A064911 -id:A064911 - cp's OEIS frontend

A001358 Semiprimes (or biprimes): products of two primes.

4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95, 106, 111, 115, 118, 119, 121, 122, 123, 129, 133, 134, 141, 142, 143, 145, 146, 155, 158, 159, 161, 166, 169, 177, 178, 183, 185, 187

Offset: 1

N. J. A. Sloane, R. K. Guy

Numbers of the form p*q where p and q are primes, not necessarily distinct.
These numbers are sometimes called semiprimes or 2-almost primes.
Numbers n such that Omega(n) = 2 where Omega(n) = A001222(n) is the sum of the exponents in the prime decomposition of n.
Complement of A100959; A064911(a(n)) = 1. - Reinhard Zumkeller, Nov 22 2004
The graph of this sequence appears to be a straight line with slope 4. However, the asymptotic formula shows that the linearity is an illusion and in fact a(n)/n ~ log(n)/log(log(n)) goes to infinity. See also the graph of A066265 = number of semiprimes < 10^n.
For numbers between 33 and 15495, semiprimes are more plentiful than any other k-almost prime. See A125149.
Numbers that are divisible by exactly 2 prime powers (not including 1). - Jason Kimberley, Oct 02 2011
The (disjoint) union of A006881 and A001248. - Jason Kimberley, Nov 11 2015
An equivalent definition of this sequence is a'(n) = smallest composite number which is not divided by any smaller composite number a'(1),...,a'(n-1). - Meir-Simchah Panzer, Jun 22 2016
The above characterization can be simplified to "Composite numbers not divisible by a smaller term." This shows that this is the equivalent of primes computed via Eratosthenes's sieve, but starting with the set of composite numbers (i.e., complement of 1 union primes) instead of all positive integers > 1. It's easy to see that iterating the method (using Eratosthenes's sieve each time on the remaining numbers, complement of the previously computed set) yields numbers with bigomega = k for k = 0, 1, 2, 3, ..., i.e., {1}, A000040, this, A014612, etc. - M. F. Hasler, Apr 24 2019
For all n except n = 2, a(n) is a deficient number. - Amrit Awasthi, Sep 10 2024
It is reasonable to assume that the "comforting numbers" which John T. Williams found in Chapter 3 of Milne's book "The House at Pooh Corner" are these semiprimes. Winnie-the-Pooh wonders whether he has 14 or 15 honey pots and concludes: "It's sort of comforting." To arrange a semiprime number of honey pots in a rectangular way, let's say on a shelf, with the larger divisor parallel to the wall, there is only one solution and this is for a simple mind like Winnie-the-Pooh comforting. - Ruediger Jehn, Dec 12 2024

			From _Gus Wiseman_, May 27 2021: (Start)
The sequence of terms together with their prime factors begins:
   4 = 2*2     46 = 2*23     91 = 7*13    141 = 3*47
   6 = 2*3     49 = 7*7      93 = 3*31    142 = 2*71
   9 = 3*3     51 = 3*17     94 = 2*47    143 = 11*13
  10 = 2*5     55 = 5*11     95 = 5*19    145 = 5*29
  14 = 2*7     57 = 3*19    106 = 2*53    146 = 2*73
  15 = 3*5     58 = 2*29    111 = 3*37    155 = 5*31
  21 = 3*7     62 = 2*31    115 = 5*23    158 = 2*79
  22 = 2*11    65 = 5*13    118 = 2*59    159 = 3*53
  25 = 5*5     69 = 3*23    119 = 7*17    161 = 7*23
  26 = 2*13    74 = 2*37    121 = 11*11   166 = 2*83
  33 = 3*11    77 = 7*11    122 = 2*61    169 = 13*13
  34 = 2*17    82 = 2*41    123 = 3*41    177 = 3*59
  35 = 5*7     85 = 5*17    129 = 3*43    178 = 2*89
  38 = 2*19    86 = 2*43    133 = 7*19    183 = 3*61
  39 = 3*13    87 = 3*29    134 = 2*67    185 = 5*37
(End)

Archimedeans Problems Drive, Eureka, 17 (1954), 8.
Raymond Ayoub, An Introduction to the Analytic Theory of Numbers, Amer. Math. Soc., 1963; Chapter II, Problem 60.
Edmund Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Vol. 1, Teubner, Leipzig; third edition: Chelsea, New York (1974). See p. 211.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
John T. Williams, Pooh and the Philosophers, Dutton Books, 1995.

N. J. A. Sloane, Table of n, a(n) for n = 1..20000 (first 10000 terms from T. D. Noe)
Dragos Crisan and Radek Erban, On the counting function of semiprimes, INTEGERS, Vol. 21 (2021), #A122.
Daniel A. Goldston, Sidney W. Graham, János Pintz and Cem Y. Yildirim, Small gaps between primes or almost primes, Transactions of the American Mathematical Society, Vol. 361, No. 10 (2009), pp. 5285-5330, arXiv preprint, arXiv:math/0506067 [math.NT], 2005.
Richard K. Guy, Letters to N. J. A. Sloane, June-August 1968
Sh. T. Ishmukhametov and F. F. Sharifullina, On distribution of semiprime numbers, Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 2014, No. 8, pp. 53-59. English translation, Russian Mathematics, Vol. 58, No. 8 (2014), pp. 43-48, alternative link.
Donovan Johnson, Jonathan Vos Post, and Robert G. Wilson v, Selected n and a(n). (2.5 MB)
Dixon Jones, Quickie 593, Mathematics Magazine, Vol. 47, No. 3, May 1974, p. 167.
Edmund Landau, Handbuch der Lehre von der Verteilung der Primzahlen, vol. 1 and vol. 2, Leipzig, Berlin, B. G. Teubner, 1909. See Vol. 1, p. 211.
Xianmeng Meng, On sums of three integers with a fixed number of prime factors, Journal of Number Theory, Vol. 114, No. 1 (2005), pp. 37-65.
Michael Penn, What makes a number "good"?, YouTube video, 2022.
Carlos Rivera, Conjecture 108: On the counting function of semiprimes, The Prime Puzzles & Problems Connection.
Eric Weisstein's World of Mathematics, Semiprime.
Eric Weisstein's World of Mathematics, Almost Prime.
Wikipedia, Almost prime.
Robert G. Wilson v, Subsequences at various powers of 10.
Index to sequences related to sums of cubes
Index entries for "core" sequences

Cf. A064911 (characteristic function).
Cf. A048623, A048639, A000040 (primes), A014612 (products of 3 primes), A014613, A014614, A072000 ("pi" for semiprimes), A065516 (first differences).
Cf. A077554, A077555, A002024, A072966, A100592, A014673, A068318, A061299, A087718, A089994, A089995, A096916, A096932, A106550, A106554, A108541, A108542, A126663, A131284, A138510, A138511, A072931, A088183, A171963, A237040 (semiprimes of form n^3 + 1).
Sequences listing r-almost primes, that is, the n such that A001222(n) = r: A000040 (r=1), this sequence (r=2), A014612 (r=3), A014613 (r=4), A014614 (r=5), A046306 (r=6), A046308 (r=7), A046310 (r=8), A046312 (r=9), A046314 (r=10), A069272 (r=11), A069273 (r=12), A069274 (r=13), A069275 (r=14), A069276 (r=15), A069277 (r=16), A069278 (r=17), A069279 (r=18), A069280 (r=19), A069281 (r=20).
These are the Heinz numbers of length-2 partitions, counted by A004526.
The squarefree case is A006881 with odd/even terms A046388/A100484 (except 4).
Including primes gives A037143.
The odd/even terms are A046315/A100484.
Partial sums are A062198.
The prime factors are A084126/A084127.
Grouping by greater factor gives A087112.
The product/sum/difference of prime indices is A087794/A176504/A176506.
Positions of even/odd terms are A115392/A289182.
The terms with relatively prime/divisible prime indices are A300912/A318990.
Factorizations using these terms are counted by A320655.
The prime indices are A338898/A338912/A338913.
Grouping by weight (sum of prime indices) gives A338904, with row sums A024697.
The terms with even/odd weight are A338906/A338907.
The terms with odd/even prime indices are A338910/A338911.
The least/greatest term of weight n is A339114/A339115.
Cf. A014342, A098350, A112141, A320732, A332765, A339003/A339004, A339116.

a001358 n = a001358_list !! (n-1)
a001358_list = filter ((== 2) . a001222) [1..]

[n: n in [2..200] | &+[d[2]: d in Factorization(n)] eq 2]; // Bruno Berselli, Sep 09 2015

A001358 := proc(n) option remember; local a; if n = 1 then 4; else for a from procname(n-1)+1 do if numtheory[bigomega](a) = 2 then return a; end if; end do: end if; end proc:
seq(A001358(n), n=1..120) ; # R. J. Mathar, Aug 12 2010

Select[Range[200], Plus@@Last/@FactorInteger[#] == 2 &] (* Zak Seidov, Jun 14 2005 *)
Select[Range[200], PrimeOmega[#]==2&] (* Harvey P. Dale, Jul 17 2011 *)

select( isA001358(n)={bigomega(n)==2}, [1..199]) \\ M. F. Hasler, Apr 09 2008; added select() Apr 24 2019

list(lim)=my(v=List(),t);forprime(p=2, sqrt(lim), t=p;forprime(q=p, lim\t, listput(v,t*q))); vecsort(Vec(v)) \\ Charles R Greathouse IV, Sep 11 2011

A1358=List(4); A001358(n)={while(#A1358M. F. Hasler, Apr 24 2019

from sympy import factorint
def ok(n): return sum(factorint(n).values()) == 2
print([k for k in range(1, 190) if ok(k)]) # Michael S. Branicky, Apr 30 2022

from math import isqrt
from sympy import primepi, prime
def A001358(n):
    def f(x): return int(n+x-sum(primepi(x//prime(k))-k+1 for k in range(1, primepi(isqrt(x))+1)))
    m, k = n, f(n)
    while m != k:
        m, k = k, f(k)
    return m # Chai Wah Wu, Jul 23 2024

a(n) ~ n*log(n)/log(log(n)) as n -> infinity [Landau, p. 211], [Ayoub].
Recurrence: a(1) = 4; for n > 1, a(n) = smallest composite number which is not a multiple of any of the previous terms. - Amarnath Murthy, Nov 10 2002
A174956(a(n)) = n. - Reinhard Zumkeller, Apr 03 2010
a(n) = A088707(n) - 1. - Reinhard Zumkeller, Feb 20 2012
Sum_{n>=1} 1/a(n)^s = (1/2)*(P(s)^2 + P(2*s)), where P is the prime zeta function. - Enrique Pérez Herrero, Jun 24 2012
sigma(a(n)) + phi(a(n)) - mu(a(n)) = 2*a(n) + 1. mu(a(n)) = ceiling(sqrt(a(n))) - floor(sqrt(a(n))). - Wesley Ivan Hurt, May 21 2013
mu(a(n)) = -Omega(a(n)) + omega(a(n)) + 1, where mu is the Moebius function (A008683), Omega is the count of prime factors with repetition, and omega is the count of distinct prime factors. - Alonso del Arte, May 09 2014
a(n) = A078840(2,n). - R. J. Mathar, Jan 30 2019
A100484 UNION A046315. - R. J. Mathar, Apr 19 2023
Conjecture: a(n)/n ~ (log(n)/log(log(n)))*(1-(M/log(log(n)))) as n -> oo, where M is the Mertens's constant (A077761). - Alain Rocchelli, Feb 02 2025

More terms from James Sellers, Aug 22 2000

A045917 From Goldbach problem: number of decompositions of 2n into unordered sums of two primes.

Original entry on oeis.org

0, 1, 1, 1, 2, 1, 2, 2, 2, 2, 3, 3, 3, 2, 3, 2, 4, 4, 2, 3, 4, 3, 4, 5, 4, 3, 5, 3, 4, 6, 3, 5, 6, 2, 5, 6, 5, 5, 7, 4, 5, 8, 5, 4, 9, 4, 5, 7, 3, 6, 8, 5, 6, 8, 6, 7, 10, 6, 6, 12, 4, 5, 10, 3, 7, 9, 6, 5, 8, 7, 8, 11, 6, 5, 12, 4, 8, 11, 5, 8, 10, 5, 6, 13, 9, 6, 11, 7, 7, 14, 6, 8, 13, 5, 8, 11, 7, 9

Offset: 1

Felice Russo

Note that A002375 (which differs only at the n = 2 term) is the main entry for this sequence.
The graph of this sequence is called Goldbach's comet. - David W. Wilson, Mar 19 2012
This is the row length sequence of A182138, A184995 and A198292. - Jason Kimberley, Oct 03 2012
The Goldbach conjecture states that a(n) > 0 for n >= 2. - Wolfdieter Lang, May 14 2016
With the second Maple program, the command G(2n) yields all the unordered pairs of prime numbers having sum 2n; caveat: a pair {a,a} is listed as {a}. Example: G(26) yields {{13}, {3,23}, {7,19}}. The command G(100000) yields 810 pairs very fast. - Emeric Deutsch, Jan 03 2017
Conjecture: Let p denote any prime in any decomposition of 2n. 4 and 6 are the only numbers n such that 2n + p is prime for every p. - Ivan N. Ianakiev, Apr 06 2017
Conjecture: For all m >= 0, there exists at least one possible value of n such that a(n) = m. - Ahmad J. Masad, Jan 06 2018
The previous conjecture is related to the sequence A053033. - Ahmad J. Masad, Dec 09 2019
Conjecture: For each k >= 0, there exists a minimum sufficiently large number r that depends on k such that for each n >= r, a(n) > k. - Ahmad J. Masad, Jan 08 2020
Conjecture: If the previous conjecture is true, then for each m >= 0, the number of terms that are equal to (m+1) is larger than the number of terms that are equal to m. - Ahmad J. Masad, Jan 08 2020
Also, the number of equidistant prime pairs in Goldbach's Prime Triangle for integers n > 2. An equidistant prime pair is a pair of not necessarily different prime numbers (p1, p2) that have the same distance d >= 0 from an integer n, i.e., so that p1 = n - d and p2 = n + d. - Jörg Winkelmann, Mar 05 2025

Calvin C. Clawson, "Mathematical Mysteries, the beauty and magic of numbers," Perseus Books, Cambridge, MA, 1996, Chapter 12, pages 236-257.
H. Halberstam and H. E. Richert, 1974, "Sieve methods", Academic press, London, New York, San Francisco.

H. J. Smith, Table of n, a(n) for n = 1..20000
M. Herkommer, Goldbach Conjecture Research.
Eric Weisstein's World of Mathematics, Goldbach Partition.
Wikipedia, Goldbach's conjecture.
G. Xiao, WIMS server, Goldbach
Index entries for sequences related to Goldbach conjecture
J. Winkelmann, Goldbach's Prime Triangle — A Recreational Math Journey with an Introduction to Equidistant Primes.

Cf. A002375 (the main entry for this sequence (which differs only at the n=2 term)).
Cf. A023036 (first appearance of n), A000954 (last (assumed) appearance of n).
Cf. also A000040, A182138, A184995, A185297, A187129, A010051, A198292, A035026, A224708, A224709.
Cf. A064911, A105020.

a045917 n = sum $ map (a010051 . (2 * n -)) $ takeWhile (<= n) a000040_list
-- Reinhard Zumkeller, Sep 02 2013

[#RestrictedPartitions(2*n,2,Set(PrimesInInterval(1,2*n))):n in [1..100]]; // Marius A. Burtea, Jan 23 2020

A045917 := proc(n)
    local a,i ;
    a := 0 ;
    for i from 1 to n do
        if isprime(i) and isprime(2*n-i) then
            a := a+1 ;
        end if;
    end do:
    a ;
end proc: # R. J. Mathar, Jul 01 2013
# second Maple program:
G := proc (n) local g, j: g := {}: for j from 2 to (1/2)*n do if isprime(j) and isprime(n-j) then g := `union`(g, {{n-j, j}}) end if end do: g end proc: seq(nops(G(2*n)), n = 1 .. 98); # Emeric Deutsch, Jan 03 2017

f[n_] := Length[Select[2n - Prime[Range[PrimePi[n]]], PrimeQ]]; Table[ f[n], {n, 100}] (* Paul Abbott, Jan 11 2005 *)
nn = 10^2; ps = Boole[PrimeQ[Range[1,2*nn,2]]]; Join[{0,1}, Table[Sum[ps[[i]] ps[[n-i+1]], {i, Ceiling[n/2]}], {n, 3, nn}]] (* T. D. Noe, Apr 13 2011 *)

a(n)=my(s);forprime(p=2,n,s+=isprime(2*n-p));s \\ Charles R Greathouse IV, Mar 27 2012

from sympy import isprime
def A045917(n):
    x = 0
    for i in range(2,n+1):
        if isprime(i) and isprime(2*n-i):
            x += 1
    return x # Chai Wah Wu, Feb 24 2015

From Halberstam and Richert: a(n) < (8+0(1))*c(n)*n/log(n)^2 where c(n) = Product_{p>2} (1 - 1/(p-1)^2)*Product_{p|n, p>2} (p-1)/(p-2). It is conjectured that the factor 8 can be replaced by 2. - Benoit Cloitre, May 16 2002
a(n) = ceiling(A035026(n) / 2) = (A035026(n) + A010051(n)) / 2.
a(n) = Sum_{i=2..n} floor(2/Omega(i*(2*n-i))). - Wesley Ivan Hurt, Jan 24 2013
a(n) = A224709(n) + (primepi(2n-2) - primepi(n-1)) + primepi(n) + 1 - n. - Anthony Browne, May 03 2016
a(n) = A224708(2n) - A224708(2n+1) + A010051(n). - Anthony Browne, Jun 26 2016
a(n) = Sum_{k=n*(n-1)/2+2..n*(n+1)/2} A064911(A105020(k-1)). - Wesley Ivan Hurt, Sep 11 2021
a(n) = omega(A362641(n)) = omega(A362640(n)). - Wesley Ivan Hurt, Apr 28 2023

A000430 Primes and squares of primes.

Original entry on oeis.org

2, 3, 4, 5, 7, 9, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 149, 151, 157, 163, 167, 169, 173, 179, 181, 191, 193, 197, 199, 211, 223

Offset: 1

R. Muller

Also numbers n such that the product of proper divisors is < n.
See A050216 for lengths of blocks of consecutive primes. - Reinhard Zumkeller, Sep 23 2011
Numbers q > 1 such that d(q) < 4. Numbers k such that the number of ways of writing k = m + t is equal to the number of ways of writing k = r*s, where m|t and r|s. - Juri-Stepan Gerasimov, Oct 14 2017
Called multiplicatively deficient numbers by Chau (2004). - Amiram Eldar, Jun 29 2022

F. Smarandache, Definitions solved and unsolved problems, conjectures and theorems in number theory and geometry, edited by M. Perez, Xiquan Publishing House 2000
F. Smarandache, Sequences of Numbers Involved in Unsolved Problems, Hexis, Phoenix, 2006.

T. D. Noe, Table of n, a(n) for n = 1..1000
William Chau, The tau, sigma, rho functions, and some related numbers, Pi Mu Epsilon Journal, Vol. 11, No. 10 (Spring 2004), pp. 519-534; entire issue.
F. Smarandache, Sequences of Numbers Involved in Unsolved Problems.

Union of A000040 and A001248.

Cf. A007422, A010051, A010055, A032741, A046951, A050216, A056595, A058080, A064911, A084110, A084114, A293575.

a000430 n = a000430_list !! (n-1)
a000430_list = m a000040_list a001248_list where
   m (x:xs) (y:ys) | x < y = x : m xs (y:ys)
                   | x > y = y : m (x:xs) ys
-- Reinhard Zumkeller, Sep 23 2011

nn = 223; t = Union[Prime[Range[PrimePi[nn]]], Prime[Range[PrimePi[Sqrt[nn]]]]^2] (* T. D. Noe, Apr 11 2011 *)
Module[{upto=250,prs},prs=Prime[Range[PrimePi[upto]]];Select[Join[ prs,prs^2], #<=upto&]]//Sort (* Harvey P. Dale, Oct 08 2016 *)

is(n)=isprime(n) || (issquare(n,&n) && isprime(n)) \\ Charles R Greathouse IV, Sep 04 2013

from math import isqrt
from sympy import primepi
def A000430(n):
    def f(x): return n+x-primepi(x)-primepi(isqrt(x))
    m, k = n, f(n)
    while m != k:
        m, k = k, f(k)
    return int(m) # Chai Wah Wu, Aug 09 2024

A084114(a(n)) = 0, see also A084110. - Reinhard Zumkeller, May 12 2003
A109810(a(n)) = 2. - Reinhard Zumkeller, May 24 2010
A010051(a(n)) + A010055(a(n))*A064911(a(n)) = 1;
A056595(a(n)) = 1. - Reinhard Zumkeller, Aug 15 2011
A032741(a(n)) = A046951(a(n)); A293575(a(n)) = 0. - Juri-Stepan Gerasimov, Oct 14 2017
The number of terms not exceeding x is N(x) ~ (x + 2*sqrt(x))/log(x) (Chau, 2004). - Amiram Eldar, Jun 29 2022

A086971 Number of semiprime divisors of n.

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 2, 0, 1, 1, 1, 0, 2, 0, 2, 1, 1, 0, 2, 1, 1, 1, 2, 0, 3, 0, 1, 1, 1, 1, 3, 0, 1, 1, 2, 0, 3, 0, 2, 2, 1, 0, 2, 1, 2, 1, 2, 0, 2, 1, 2, 1, 1, 0, 4, 0, 1, 2, 1, 1, 3, 0, 2, 1, 3, 0, 3, 0, 1, 2, 2, 1, 3, 0, 2, 1, 1, 0, 4, 1, 1, 1, 2, 0, 4, 1, 2, 1, 1, 1, 2, 0, 2, 2, 3, 0, 3

Offset: 1

Reinhard Zumkeller, Sep 22 2003

nonn

Inverse Moebius transform of A064911. - Jonathan Vos Post, Dec 08 2004

G. H. Hardy and E. M. Wright, Section 17.10 in An Introduction to the Theory of Numbers, 5th ed., Oxford, England: Clarendon Press, 1979.

T. D. Noe, Table of n, a(n) for n = 1..10000
E. A. Bender and J. R. Goldman, On the Applications of Mobius Inversion in Combinatorial Analysis, Amer. Math. Monthly 82, (1975), 789-803.
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, arXiv:math/0205301 [math.CO], 2002; Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210.
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
N. J. A. Sloane, Transforms.
Eric Weisstein's World of Mathematics, Semiprime.
Eric Weisstein's World of Mathematics, Divisor Function.
Eric Weisstein's World of Mathematics, Moebius Transform.

Cf. A001358, A064911, A001221, A000005, A000010, A004018, A007913, A056170, A079275, A001222, A220264 (least inverse).

a086971 = sum . map a064911 . a027750_row
-- Reinhard Zumkeller, Dec 14 2012

a:= proc(n) local l, m; l:=ifactors(n)[2]; m:=nops(l);
       m*(m-1)/2 +add(`if`(i[2]>1, 1, 0), i=l)
    end:
seq(a(n), n=1..120);  # Alois P. Heinz, Jul 18 2013

semiPrimeQ[n_] := PrimeOmega@ n == 2; f[n_] := Length@ Select[Divisors@ n, semiPrimeQ@# &]; Array[f, 105] (* Zak Seidov, Mar 31 2011 and modified by Robert G. Wilson v, Dec 08 2012 *)
a[n_] := Count[e = FactorInteger[n][[;; , 2]], ?(# > 1 &)] + (o = Length[e])*(o - 1)/2; Array[a, 100] (* _Amiram Eldar, Jun 30 2022 *)

/* The following definitions of a(n) are equivalent. */
a(n) = sumdiv(n,d,bigomega(d)==2)
a(n) = f=factor(n); j=matsize(f)[1]; sum(m=1,j,f[m,2]>=2) + binomial(j,2)
a(n) = f=factor(n); j=omega(n); sum(m=1,j,f[m,2]>=2) + binomial(j,2)
a(n) = omega(n/core(n)) + binomial(omega(n),2)
/* Rick L. Shepherd, Mar 06 2006 */

a(n) = A106404(n) + A106405(n). - Reinhard Zumkeller, May 02 2005
a(n) = omega(n/core(n)) + binomial(omega(n),2) = A001221(n/A007913(n)) + binomial(A001221(n),2) = A056170(n) + A079275(n). - Rick L. Shepherd, Mar 06 2006
From Reinhard Zumkeller, Dec 14 2012: (Start)
a(n) = Sum_{k=1..A000005(n)} A064911(A027750(n,k)).
a(A220264(n)) = n and a(m) <> n for m < A220264(n); a(A008578(n)) = 0; a(A002808(n)) > 0; for n > 1: a(A102466(n)) <= 1 and a(A102467(n)) > 1; A066247(n) = A057427(a(n)). (End)
G.f.: Sum_{k = p*q, p prime, q prime} x^k/(1 - x^k). - Ilya Gutkovskiy, Jan 25 2017

Entry revised by N. J. A. Sloane, Mar 28 2006

A072000 Number of semiprimes (A001358) <= n.

Original entry on oeis.org

0, 0, 0, 1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 5, 6, 6, 6, 6, 6, 6, 7, 8, 8, 8, 9, 10, 10, 10, 10, 10, 10, 10, 11, 12, 13, 13, 13, 14, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 17, 17, 18, 18, 18, 18, 19, 19, 20, 21, 21, 21, 21, 22, 22, 22, 23, 23, 23, 23, 24, 24, 24, 24, 24, 25, 25, 25, 26

Offset: 1

Benoit Cloitre, Jun 19 2002

Number of k <= n such that bigomega(k) = 2.

A. Hildebrand, On the number of prime factors of an integer, in Ramanujan Revisited (Urbana-Champaign, Ill., 1987), pp. 167-185, Academic Press, Boston, MA, 1988.
E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, vol. 1, Teubner, Leipzig, 1909; third edition : Chelsea, New York (1974).
G. Tenenbaum, Introduction à la théorie analytique et probabiliste des nombres, p. 203, Publications de l'Institut Cartan, 1990.

Daniel Forgues, Table of n, a(n) for n = 1..40882
Dragos Crisan and Radek Erban, On the counting function of semiprimes, arXiv:2006.16491 [math.NT], 2020.
E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, vol. 1 and vol. 2, Leipzig, Berlin, B. G. Teubner, 1909.
Eric Weisstein's World of Mathematics, Semiprime

Cf. A000720, A001358, A066265, A064911.

A072000 := proc(n) local sp,t ; sp := 0 ; for t from 1 to n do if numtheory[bigomega](t) = 2 then sp := sp+1 ; fi ; od ; sp ; end proc: # R. J. Mathar, Jun 10 2007

semiPrimePi[n_] := Sum[ PrimePi[n/Prime@i] -i + 1, {i, PrimePi@Sqrt@n}]; Array[semiPrimePi, 78] (* Robert G. Wilson v, Jan 03 2006 *)
(* If version >= 7 *) a[n_] := Select[Range[n], PrimeOmega[#] == 2 &] // Length; Table[a[n], {n, 1, 77}] (* Jean-François Alcover, Jun 29 2013 *)
Accumulate[Table[If[PrimeOmega[n]==2,1,0],{n,100}]] (* Harvey P. Dale, Jun 14 2014 *)

for(n=1,100,print1(sum(i=1,n,if(bigomega(i)-2,0,1)),","))

a(n)=my(s=0,i=0); forprime(p=2, sqrt(n), s+=primepi(n\p); i++); s - i * (i-1)/2 \\ Charles R Greathouse IV, Apr 21 2011

from math import isqrt
from sympy import primepi, prime
def A072000(n): return int(sum(primepi(n//prime(k))-k+1 for k in range(1,primepi(isqrt(n))+1))) # Chai Wah Wu, Jul 23 2024

Let PrimePi(x) denote the number of primes <= x (cf. A000720). Then 2*a(n) = Sum_{ primes p <= n/2 } PrimePi(n/p) + PrimePi(sqrt(n)). [Landau, p. 211]
Let PrimePi(x) denote the number of primes <= x (cf. A000720). Then a(n) = Sum_{i=1..PrimePi(sqrt(n))} (PrimePi(n/prime(i)) - i + 1). - Robert G. Wilson v, Feb 07 2006
a(n) = card { x <= n : bigomega(x) = 2 }.
Asymptotically a(n) ~ n*log(log(n))/log(n). [Landau, p. 211]
Let A be a positive integer. Then card { x <= n : bigomega(x) = A } ~ (n/log(n))*log(log(n))^(A-1)/(A-1)! [Landau, p. 211]
a(n) = A072613(n) + A056811(n). - R. J. Mathar, Jun 10 2007
a(n) = Sum_{i=1..n} A064911(i). - Jonathan Vos Post, Dec 30 2007
a(n)*A064911(n) = A174956(n). - Reinhard Zumkeller, Apr 03 2010

Edited by Robert G. Wilson v, Feb 15 2006

A100959 Non-semiprimes.

Original entry on oeis.org

1, 2, 3, 5, 7, 8, 11, 12, 13, 16, 17, 18, 19, 20, 23, 24, 27, 28, 29, 30, 31, 32, 36, 37, 40, 41, 42, 43, 44, 45, 47, 48, 50, 52, 53, 54, 56, 59, 60, 61, 63, 64, 66, 67, 68, 70, 71, 72, 73, 75, 76, 78, 79, 80, 81, 83, 84, 88, 89, 90, 92, 96, 97, 98, 99, 100, 101, 102, 103, 104

Offset: 1

Reinhard Zumkeller, Nov 24 2004

A001222(a(n)) <> 2; a(n) <> A020639(a(n)) * A006530(a(n)); complement of A001358; A064911(a(n)) = 0.

A174956(a(n)) = 0. - Reinhard Zumkeller, Apr 03 2010

Donald Alan Morrison, Table of n, a(n) for n = 1..10000
Donald Alan Morrison, Sage program
Eric Weisstein's World of Mathematics, Semiprime

Select[Range[120], ! PrimeOmega[#] == 2 &] (* Vincenzo Librandi, Jun 14 2014 *)

isok(n) = (bigomega(n) != 2) \\ Michel Marcus, Aug 01 2013

from math import isqrt
from sympy import prime, primepi
def A100959(n):
    def f(x): return n+int(sum(primepi(x//prime(k))-k+1 for k in range(1,primepi(isqrt(x))+1)))
    m, k = n, f(n)
    while m != k:
        m, k = k, f(k)
    return m # Chai Wah Wu, Jul 23 2024

a(n) = n + O(n log log n/log n). - Charles R Greathouse IV, Dec 29 2024

A070552 Semiprimes k such that k+1 is also a semiprime.

Original entry on oeis.org

9, 14, 21, 25, 33, 34, 38, 57, 85, 86, 93, 94, 118, 121, 122, 133, 141, 142, 145, 158, 177, 201, 202, 205, 213, 214, 217, 218, 253, 298, 301, 302, 326, 334, 361, 381, 393, 394, 445, 446, 453, 481, 501, 514, 526, 537, 542, 553, 565, 622, 633, 634, 694, 697

Offset: 1

Sharon Sela (sharonsela(AT)hotmail.com), May 03 2002

nonn

A064911(a(n))*A064911(a(n)+1) = 1. - Reinhard Zumkeller, Dec 03 2009

D. W. Wilson, Table of n, a(n) for n = 1..10000

Cf. A001358, A007674, A039832, A100484.

IsSemiprime:=func< n | &+[k[2]: k in Factorization(n)] eq 2 >; [ n: n in [4..700] | IsSemiprime(n) and IsSemiprime(n+1) ]; // Vincenzo Librandi, Jan 22 2016

f[n_]:=Last/@FactorInteger[n]=={1,1}||Last/@FactorInteger[n]=={2};lst={};Do[If[f[n]&&f[n+1],AppendTo[lst,n]],{n,7!}];lst (* Vladimir Joseph Stephan Orlovsky, Feb 25 2010 *)
Flatten[Position[Partition[Table[If[PrimeOmega[n]==2,1,0],{n,700}],2,1],{1,1}]] (* Harvey P. Dale, Feb 04 2015 *)
Select[Range[700], PrimeOmega[#] == PrimeOmega[# + 1] == 2 &] (* Vincenzo Librandi, Jan 22 2016 *)

forprime(p=3,1e3,if(bigomega(2*p-1)==2,print1(2*p-1", "));if(bigomega(2*p+1)==2,print1(2*p", "))) \\ Charles R Greathouse IV, Nov 09 2011

is(n)=if(n%2, isprime((n+1)/2) && bigomega(n)==2, isprime(n/2) && bigomega(n+1)==2) \\ Charles R Greathouse IV, Sep 08 2015

from sympy import factorint
def is_semiprime(n): return sum(e for e in factorint(n).values()) == 2
def ok(n): return is_semiprime(n) and is_semiprime(n+1)
print(list(filter(ok, range(698)))) # Michael S. Branicky, Sep 14 2021

a(n) >> n log n since either n or n+1 is in A100484. - Charles R Greathouse IV, Jul 21 2015

a(n) = A109373(n) - 1. - Zak Seidov Dec 19 2018

More terms from Vladeta Jovovic, May 03 2002

A101048 Number of partitions of n into semiprimes (a(0) = 1 by convention).

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 2, 0, 2, 1, 3, 2, 3, 1, 5, 3, 5, 4, 7, 4, 9, 7, 10, 8, 13, 10, 17, 13, 18, 17, 25, 21, 29, 25, 34, 34, 43, 37, 51, 49, 61, 59, 73, 69, 89, 87, 103, 103, 124, 122, 148, 149, 172, 176, 206, 208, 244, 248, 281, 293, 337, 344, 391, 405, 456, 479, 537, 553

Offset: 0

Reinhard Zumkeller, Nov 28 2004

nonn

Semiprime analog of A000607. a(n) <= A002095(n). - Jonathan Vos Post, Oct 01 2007

Das, Robles, Zaharescu, & Zeindler give an asymptotic formula, see Links. - Charles R Greathouse IV, Jan 20 2023

			a(12) = #{6 + 6, 4 + 4 + 4} = #{2 * (2*3), 3 * (2*2)} = 2.

Alois P. Heinz, Table of n, a(n) for n = 0..10000 (first 1001 terms from T. D. Noe)
Madhuparna Das, Nicolas Robles, Alexandru Zaharescu, and Dirk Zeindler, Partitions into semiprimes, arXiv preprint (2022). arXiv:2212.12489 [math.NT]

Cf. A000041, A000607, A101049, A001358, A064911, A002095.
Cf. A112020, A112021.
Cf. A002100.
Row sums of A344447.

a101048 = p a001358_list where
   p _          0 = 1
   p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m
-- Reinhard Zumkeller, Mar 21 2014

g:=1/product(product(1-x^(ithprime(i)*ithprime(j)),i=1..j),j=1..30): gser:=series(g,x=0,75): seq(coeff(gser,x,n),n=1..71); # Emeric Deutsch, Apr 04 2006
# second Maple program:
h:= proc(n) option remember; `if`(n=0, 0,
     `if`(numtheory[bigomega](n)=2, n, h(n-1)))
    end:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
     `if`(i>n, 0, b(n-i, h(min(n-i, i))))+b(n, h(i-1))))
    end:
a:= n-> b(n, h(n)):
seq(a(n), n=0..100);  # Alois P. Heinz, May 19 2021

terms = 100; CoefficientList[1/Product[1 - x^(Prime[i] Prime[j]), {i, 1, PrimePi[Ceiling[terms/2]]}, {j, 1, i}] + O[x]^terms, x] (* Jean-François Alcover, Aug 01 2018 *)

issemi(n)=if(n<4, return(0)); forprime(p=2,97, if(n%p==0, return(isprime(n/p)))); bigomega(n)==2
allsemi(v)=for(i=1,#v, if(!issemi(v[i]), return(0))); 1
a(n)=my(s); if(n<4, return(n==0)); forpart(k=n, if(allsemi(k), s++),[4,n]); s \\ Charles R Greathouse IV, Jan 20 2023

G.f.: 1/product(product(1-x^(p(i)p(j)), i = 1..j),j = 1..infinity), p(k) is the k-th prime. - Emeric Deutsch, Apr 04 2006

a(0) set to 1 by N. J. A. Sloane, Nov 23 2007

A066265 a(n) = number of semiprimes < 10^n.

Original entry on oeis.org

0, 3, 34, 299, 2625, 23378, 210035, 1904324, 17427258, 160788536, 1493776443, 13959990342, 131126017178, 1237088048653, 11715902308080, 111329817298881, 1061057292827269, 10139482913717352, 97123037685177087, 932300026230174178, 8966605849641219022, 86389956293761485464, 833671466551239927908, 8056846659984852885191

Offset: 0

Patrick De Geest, Dec 10 2001

nonn

Apart from the first nonzero term the sequence is identical to A036352. - Hugo Pfoertner, Jul 22 2003

			Below 10 there are three semiprimes: 4 (2*2), 6 (2*3) and 9 (3*3).

Eric Weisstein's World of Mathematics, Semiprime
Index entries for sequences related to numbers of primes in various ranges

Cf. A001358, A064911, A072000, A036352 (identical starting from a(2)), A220262, A292785.

f[n_] := Sum[ PrimePi[(10^n - 1)/Prime[i]], {i, PrimePi[ Sqrt[10^n]]}] - Binomial[ PrimePi[ Sqrt[10^n]], 2]; Do[ Print[ f[n]], {n, 0, 14}] (* Robert G. Wilson v, May 16 2005 *)
SemiPrimePi[n_] := Sum[ PrimePi[n/Prime@ i] - i + 1, {i, PrimePi@ Sqrt@ n}]; Array[ SemiPrimePi[10^# - 1] &, 14, 0] (* Robert G. Wilson v, Jan 21 2015 *)

a(n)=my(s);forprime(p=2,sqrt(10^n),s+=primepi((10^n-1)\p)); s-binomial(primepi(sqrt(10^n)),2) \\ Charles R Greathouse IV, Apr 23 2012

use Math::Prime::Util qw/:all/; use integer; sub countsp { my($k,$sum,$pc)=($[0]-1,0,1); prime_precalc(60_000_000); forprimes { $sum += prime_count($k/$) + 1 - $pc++; } int(sqrt($k)); $sum; } foreach my $n (0..16) { say "$n: ", countsp(10**$n); } # Dana Jacobsen, May 11 2014

from math import isqrt
from sympy import primepi, primerange
def A066265(n): return int((-(t:=primepi(s:=isqrt(m:=10**n)))*(t-1)>>1)+sum(primepi(m//k) for k in primerange(1, s+1))) if n>1 else 3*n # Chai Wah Wu, Aug 16 2024

(1/2)*( pi(10^(n/2)) + Sum_{i=1..pi(10^n)} pi( (10^n-1)/P_i) ) = Sum_{i=1..pi(sqrt(10^n))} pi( (10^n-1)/P_i ) - binomial( pi(sqrt(10^n)), 2). - Robert G. Wilson v, May 16 2005

More terms from Hugo Pfoertner, Jul 22 2003
a(14) from Robert G. Wilson v, May 16 2005
a(15)-a(16) from Donovan Johnson, Mar 18 2010
a(17)-a(18) from Dana Jacobsen, May 11 2014
a(19)-a(21) from Henri Lifchitz, Jul 04 2015
a(22)-a(23) from Henri Lifchitz, Nov 09 2024

cp's OEIS Frontend

A181522 Number of subsets of {1,2,...,n} whose sum is semiprime (cf. A001358, A064911).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

A001358 Semiprimes (or biprimes): products of two primes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Formula

Extensions

A045917 From Goldbach problem: number of decompositions of 2n into unordered sums of two primes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Formula

A000430 Primes and squares of primes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Formula

A086971 Number of semiprime divisors of n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A072000 Number of semiprimes (A001358) <= n.

Views

Author

Keywords