A088707 -id:A088707 - 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

A005385 Safe primes p: (p-1)/2 is also prime.

Original entry on oeis.org

5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907, 2027, 2039, 2063, 2099, 2207, 2447, 2459, 2579, 2819, 2879, 2903, 2963

Offset: 1

N. J. A. Sloane

Then (p-1)/2 is called a Sophie Germain prime: see A005384.
Or, primes of the form 2p+1 where p is prime.
Primes p such that denominator(Bernoulli(p-1) + 1/p) = 6. - Mohammed Bouayoun (bouyao(AT)wanadoo.fr), Feb 10 2004
Primes p such that p-1 is a semiprime. - Zak Seidov, Jul 01 2005
A156659(a(n)) = 1; A156875 gives numbers of safe primes <= n. - Reinhard Zumkeller, Feb 18 2009
From Daniel Forgues, Jul 31 2009: (Start)
A safe prime p is 7 or of the form 6k-1, k >= 1, i.e., p == 5 (mod 6).
A prime p of the form 6k+1, k >= 2, i.e., p = 1 (mod 6), cannot be a safe prime since (p-1)/2 is composite and divisible by 3. (End)
If k is the product of the n-th safe prime p and its corresponding Sophie Germain prime (p-1)/2, then a(n) = 2(k-phi(k))/3 + 1, where phi is Euler's totient function. - Wesley Ivan Hurt, Oct 03 2013
From Bob Selcoe, Apr 14 2014: (Start)
When the n-th prime is divided by all primes up to the (n-1)-th prime, safe primes (p) have remainders of 1 when divided by 2 and (p-1)/2 and no other primes. That is, p(mod j)=1 iff j={2,(p-1)/2}; p>j, {p,j}=>prime.  Explanation: Generally, x(mod y)=1 iff x=y'+1, where y' is the set of divisors of y, y'>1. Since safe primes (p) are of the form p(mod j)=1 iff p and j are prime, then j={j'}. That is, since j is prime, there are no divisors of j (greater than 1) other than j.  Therefore, no primes other than j exist which satisfy the equation p(mod j)=1.
Except primes of the form 2^n+1 (n>=0), all non-safe primes (p') will have at least one prime (p") greater than 2 and less than (p-1)/2 such that p'(mod p")=1. Explanation: Non-safe primes (p') are of the form p'(mod k)=1 where k is composite. This means prime divisors of k exist, and p" is the set of prime divisors of k (example p'=89: k=44; p"={2,11}).  The exception applies because p"={2} iff p'=2^n+1.
Refer to the rows in triangle A207409 for illustration and further explanation. (End)
Conjecture: there is a strengthening of the Bertrand postulate for n >= 24: the interval (n, 2*n) contains a safe prime. It has been tested by Peter J. C. Moses up to n = 10^7. - Vladimir Shevelev, Jul 06 2015
The six known safe primes p such that (p-1)/2 is a Fibonacci prime are in A263880. - Jonathan Sondow, Nov 04 2015
The only term in common with A005383 is 5. - Zak Seidov, Dec 31 2015
From the fourth entry onward, do these correspond to Smarandache's problem 34 (see A007931 link), specifically values which cannot be used (do not meet conditions) to confirm the conjecture? - Bill McEachen, Sep 29 2016
Primes p with the property that there is a prime q such that p+q^2 is a square. - Zak Seidov, Feb 16 2017
It is conjectured that there are infinitely many safe primes, and their estimated asymptotic density ~ 2C/(log n)^2 (where C = 0.66... is the twin prime constant A005597) converges to the actual value as far as we know. - M. F. Hasler, Jun 14 2021

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 870.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 1..10000
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
A. R. Ashrafi and F. Koorepazan-Moftakhar, Towards the Classification of Finite Simple Groups with exactly Three or Four Supercharacter Theories, arXiv preprint arXiv:1605.08971 [math.GR], 2016.
R. P. Boas & N. J. A. Sloane, Correspondence, 1974.
Siji Chen and Sheng Chen, Connectedness of digraphs from quadratic polynomials, Involve (2020) Vol. 13, No. 2, 357-360.
Benoit Cloitre, On the fractal behavior of primes, 2011.
L. H. Gallardo and O. Rahavandrainy, There are finitely many even perfect polynomials over F_p with p+1 irreducible divisors, Acta Mathematica Universitatis Comenianae, Vol. 83, No. 2, 2016, 261-275.
David Naccache, Double-Speed Safe Prime Generation, IACR, Report 2003/175, 2003.
Planetmath, Safe prime.
Michael J. Wiener, Safe Prime Generation with a Combined Sieve, IACR, Report 2003/186, 2003.
Wikipedia, Safe prime.

Cf. A007700, A023272, A023302, A023330, A057331, A005602, A207409, A263880.
Except for the initial term, this is identical to A079148.
Cf. A005384, A005383.
Subsequence of A088707.
Primes in A072055.

a005385 n = a005385_list !! (n-1)
a005385_list = filter ((== 1) . a010051 . (`div` 2)) a000040_list
-- Reinhard Zumkeller, Sep 18 2011

[p: p in PrimesUpTo(3000) | IsPrime((p-1) div 2)]; // Vincenzo Librandi, Jul 06 2015

with(numtheory); [ seq(safeprime(i),i=1..3000) ]: convert(%,set); convert(%,list); sort(%);
A005385_list := n->select(i->isprime(iquo(i,2)),select(i->isprime(i),[$1..n])): # Peter Luschny, Nov 08 2010

Select[Prime[Range[1000]],PrimeQ[(#-1)/2]&] (* Zak Seidov, Jan 26 2011 *)

g(n) = forprime(x=2,n,y=x+x+1;if(isprime(y),print1(y","))) \\ Cino Hilliard, Sep 12 2004

[x|x<-primes(10^3), bigomega(x-1)==2] \\ Altug Alkan, Nov 04 2015

from sympy import isprime, primerange
def aupto(limit):
  alst = []
  for p in primerange(1, limit+1):
    if isprime((p-1)//2): alst.append(p)
  return alst
print(aupto(2963)) # Michael S. Branicky, May 07 2021

a(n) = 2 * A005384(n) + 1.

More terms from Larry Reeves (larryr(AT)acm.org), Feb 15 2001

A109373 Semiprimes of the form semiprime + 1.

Original entry on oeis.org

10, 15, 22, 26, 34, 35, 39, 58, 86, 87, 94, 95, 119, 122, 123, 134, 142, 143, 146, 159, 178, 202, 203, 206, 214, 215, 218, 219, 254, 299, 302, 303, 327, 335, 362, 382, 394, 395, 446, 447, 454, 482, 502, 515, 527, 538, 543, 554, 566, 623, 634, 635, 695, 698

Offset: 1

Jonathan Vos Post, Aug 24 2005

			a(1) = 10 because (3*3+1)=(2*5) = 10.
a(2) = 15 because (2*7+1)=(3*5) = 15.
a(3) = 22 because (3*7+1)=(2*11) = 22.
a(4) = 26 because (5*5+1)=(2*13) = 26.
a(5) = 34 because (3*11+1)=(2*17) = 34.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Primes are in A000040. Semiprimes are in A001358.
Primes of the form semiprime + 1 are in A005385 (safe primes).
Semiprimes of the form semiprime + 1 are in this sequence.
3-almost primes of the form semiprime + 1 are in A109067.
4-almost primes of the form semiprime + 1 are in A109287.
5-almost primes of the form semiprime + 1 are in A109383.
Least n-almost prime of the form semiprime + 1 are in A128665.
Cf. A056809, A077065, A079148, A086005, A086006, A092307.
Subsequence of A088707; A064911.

a109373 n = a109373_list !! (n-1)
a109373_list = filter ((== 1) . a064911) a088707_list
-- Reinhard Zumkeller, Feb 20 2012

fQ[n_] := Plus @@ Last /@ FactorInteger[n] == 2; Select[ Range[ 700], fQ[ # - 1] && fQ[ # ] &] (* Robert G. Wilson v *)
With[{sps=Select[Range[700],PrimeOmega[#]==2&]},Transpose[Select[ Partition[ sps,2,1],#[[2]]-#[[1]]==1&]][[2]]] (* Harvey P. Dale, Sep 05 2012 *)

is(n)=bigomega(n)==2 && bigomega(n-1)==2 \\ Charles R Greathouse IV, Jan 31 2017

a(n) is in this sequence iff a(n) is in A001358 and (a(n)-1) is in A001358.

a(n) = A070552(n) + 1.

Extended by Ray Chandler and Robert G. Wilson v, Aug 25 2005

Edited by Ray Chandler, Mar 20 2007

cp's OEIS Frontend

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

A005385 Safe primes p: (p-1)/2 is also prime.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A109373 Semiprimes of the form semiprime + 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

Extensions

A268043 Numbers k such that k^3 - 1 and k^3 + 1 are both semiprimes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

A257533 Sum of the proper divisors of the n-th semiprime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A350500 Even numbers that are both the sum of a twin prime pair and the sum of 1 and a semiprime.

Views