¿Qué conjunto de$10$ - números de dígitos con$k$ factores principales tiene mayor cardinalidad?

Question

• Supongamos que$s_{1}$ son los números con 10 dígitos que tienen$1$ factor principal.
• Supongamos que$s_{2}$ son los números con 10 dígitos que tienen$2$ factores primos.
• Supongamos que$s_{n}$ son los números con 10 dígitos que tienen$n$ factores primos.

Se permite $0$% s. ¿Cuál de$s$ tendría el menor valor esperado de intentos para adivinar el número de dígito$10$ correcto?

Answer 1

Wolfram Alpha da el número de 10 dígitos de los números primos como 455,052,511. Cuando usted pide 2 factores primos, hacer repetidas factores que contar? Así que, ¿cuántos factores primos no $2^{31}*3=6442450944$?

Añadido: OEIS da el número de 10 dígitos semiprimes como 1493776443 yo no buscar un resultado para otros números de factores fácilmente.

Editado para permitir a los números con ceros a la izquierda en el 10 dígitos

Answer 2

No sé cómo hacer esto matemáticamente, pero usted puede hacerlo mediante programación: el uso de la Criba de Eratóstenes para generar factor de cuenta de 1 a $10^{10}-1$. Tenga en cuenta que $10^{10}$ es un poco más de $2^{33}$, de modo que usted no será capaz de almacenar, esta en la memoria en una computadora convencional (un byte por medio de entrada tendría 9.3 GB de memoria RAM para la matriz). Hay algún tiempo-la memoria de los equilibrios de aquí que pueda mantener fuera de la disco, y hay formas de paralelizar algo de esto, pero aún así no es algo que usted puede fácilmente averiguar en una mercancía equipo (a menos que exista un método mejor).

Me encontré con un programa en C para números de 10 dígitos, y se obtuvieron los siguientes cargos:

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

Esta tabla le da a la cuenta de cada una de las $s_i$ $1 \leq i \leq 33$ donde enteros entre 2 y $10^{10} - 1$. El primer multiplicidades son contados, como se ha especificado en un comentario.

Este corrió en unos 12 minutos en un x86 con 10 GB de RAM. Así que la respuesta a tu pregunta es que $s_3$ es más grande. Código publicado a continuación.

#include <stdio.h>
#include <stdlib.h>

#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]);
}

Answer 3

Hay alrededor de

$$\frac{10^{10}(\log\log 10^{10})^{k-1}}{(k - 1)!\log 10^{10}}$$ Números de 10 dígitos con k factores primos, permitiendo que los ceros a la izquierda, o $$\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)$$ sin ceros a la izquierda.

En base a esto usted esperaría que aquellos con 3 o 4 primeros factores a ser más probable. Con los dos y cinco años están muy lejos detrás, con los otros no, incluso de cerca.

Cuenta (con los principales 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)

De modo que los tres primeros factores ganar. Nota: la exacta cuenta suponga que desea contar repetidas factores primos más de una vez (las predicciones son básicamente el mismo, de cualquier manera). Si nos fijamos sólo en el número de los distintos factores primos los totales pueden variar, pero la 3 se mantiene en el primer lugar.