4
$\begingroup$
  • Suppose $s_{1}$ are the numbers with 10-digits that have $1$ prime factor.
  • Suppose $s_{2}$ are the numbers with 10-digits that have $2$ prime factors.
  • Suppose $s_{n}$ are the numbers with 10-digits that have $n$ prime factors.

Leading $0$s are allowed. Which of $s$ would have the smallest expected value of tries to guess the right $10$ digit number?

  • 10
    Meta thread http://meta.math.stackexchange.com/questions/1688/how-many-ten-digit-primes-are-there (Please vote this comment up so that it will be visible.)2011-02-22

3 Answers 3

10

I don't know how to do this mathematically, but you can do it programmatically: use the Sieve of Eratosthenes to generate factor counts from 1 to $10^{10}-1$. Note that $10^{10}$ is a bit over $2^{33}$ so you won't be able to store this in memory on a conventional computer (one byte per entry means you'd need 9.3 GB of RAM just for the array). There are some time-memory trade-offs here that could keep you off the disk, and there are ways to parallelize some of this, but it's still not something you can easily figure out on a commodity computer (unless there is a better method).

I ran a C program for 10-digit numbers and obtained the following counts:

 01: 455052511 02: 1493776443 03: 2227121996 04: 2139236881 05: 1570678136 06: 977694273 07: 550454756 08: 291646797 09: 148930536 10: 74342563 11: 36585097 12: 17836903 13: 8641282 14: 4167745 15: 2002277 16: 959377 17: 458176 18: 218163 19: 103657 20: 49031 21: 23133 22: 10837 23: 5091 24: 2349 25: 1089 26: 499 27: 224 28: 102 29: 44 30: 19 31: 7 32: 3 33: 1 

This table gives the counts for each $s_i$ for $1 \leq i \leq 33$ where integers are between 2 and $10^{10} - 1$. Prime multiplicities are counted, as you specified in a comment.

This ran in about 12 minutes on an x86 using 10 GB of RAM. So the answer to your question is that $s_3$ is largest. Code posted below.

 #include  #include   #define MAX 10000000000       // sieve size #define PPOWER 255            // marker for prime powers  // allocate MAX bytes of memory unsigned char sieve[MAX];  // use # of factors as index, # of ints is value unsigned long tally[100];   // sieve[] is initialized to all 0's; then for each i, sieve[i] will contain // the number of prime factors (including multiplicity) for each i, except // sieve[p^j] for prime p, j >1 will contain the special marker PPOWER. // We do this to properly account for prime multiplicities.  main() {   unsigned long i, j;   int c;    for (i=2; i < MAX; i++) {      if (sieve[i] != PPOWER) {       // if composite, tally and continue       if (sieve[i] > 0) {         tally[sieve[i]]++;         continue;       }        // ok, i is prime; tally and mark all prime powers as PPOWER       // (takes some thought to see why we do this)       tally[1]++;       j = i*i;       c = 2;       while (j < MAX) {         sieve[j] = PPOWER;         tally[c]++;         j = j * i;         c++;       }     }      // now sieve as usual     for (j=i*2; j < MAX; j += i) {       if (sieve[j] != PPOWER)           sieve[j]++;     }   }    for (c=1; c < 100; c++)     if (tally[c]) printf("%.2d: %ld\n", c, tally[c]); }  
  • 0
    @hhh: I don't know what you're talking about?! I've run this code on a variety of machines and it's worked just fine for any power of 10 up to $10^{10}$.2011-03-02
7

There are about

$\frac{10^{10}(\log\log 10^{10})^{k-1}}{(k - 1)!\log 10^{10}}$ 10-digit numbers with k prime factors, allowing leading zeros, or $\frac{1}{(k - 1)!}\left( \frac{10^{10}(\log\log 10^{10})^{k-1}}{\log 10^{10}}-\frac{10^9(\log\log 10^9)^{k-1}}{\log 10^9} \right)$ without leading zeros.

Based on this you'd expect those with 3 or 4 prime factors to be most likely. The ones with two and five are pretty far behind, with the others not even close.

Counts (with leading 0s):

1 455052511 (predicted: 434294482) 2 1493776443 (predicted: 1362215689) 3 2227121996 (predicted: 2136374810) 4 2139236881 (predicted: 2233663566) 5 1570678136 (predicted: 1751537079) 6 977694273 (predicted: 1098780384) 

So those with three prime factors win. Note: the exact counts assume that you want to count repeated prime factors more than once (the predictions are basically the same either way). If you look at only the number of distinct prime factors the totals vary but 3 remains in first place.

  • 2
    I have some decent code for counting semiprimes in C using the PARI library, and that can be used to count 3- and 4-almost-primes as well. But in this case I just found them in Sloane's OEIS.2011-02-23
6

Wolfram Alpha gives the number of up to 10 digit primes as 455,052,511. When you ask for 2 prime factors, do repeated factors count? So how many prime factors does $2^{31}*3=6442450944$ have?

Added: OEIS gives the number of up to 10 digit semiprimes as 1493776443 I don't find a result for other numbers of factors easily.

Edited to allow numbers with leading zeros in the 10 digits

  • 0
    Edited to allow leading zeros in the numbers, as requested by hhh.2011-02-21