A362318 Number of odd semiprimes between 2^(n-1) and 2^n.

0, 0, 0, 0, 2, 2, 7, 13, 27, 52, 104, 210, 398, 807, 1542, 3046, 5936, 11565, 22584, 44012, 86062, 167786, 327936, 640630, 1252327, 2448518, 4791344, 9378159, 18364095, 35979682, 70515477, 138275503, 271246674, 532304906, 1045047118, 2052464984, 4032502528

Offset

0,5

Comments

This is the number of odd integers with precisely n bits that are the product of two (possibly identical) prime factors.

Odd numbers with two prime factors are used as the modulus in the RSA algorithm. This sequence gives the number of "candidate" RSA moduli having precisely n bits. Note that many of these candidates would not be suitable for cryptographic applications because they are easily factored.

Links

Chai Wah Wu, Table of n, a(n) for n = 0..63 (using data in A120033 and A036378)

Formula

a(n) = A362042(n) - A362042(n-1) for n>=1.

a(n) = A120033(n-1) - A036378(n-2) for n > 1. - Chai Wah Wu, Apr 24 2023

Mathematica

a[n_] := Length@Select[Range[2^(n - 1) + 1, 2^n - 1, 2], Total[Last /@ FactorInteger[#]] ==2 &]Table[a[n], {n, 0, 25}]

Crossrefs

Cf. A036378, A046315, A120033, A362042.

Sequence in context: A366583 A366584 A019144 * A049953 A364313 A156435

Adjacent sequences: A362315 A362316 A362317 * A362319 A362320 A362321

Keyword

nonn

Author

Sidney Cadot, Apr 16 2023

Extensions

More terms from Chai Wah Wu, Apr 24 2023 (using data in A120033 and A036378)

Status

approved