enésimo número que tiene n número de factores primos distintos

10

Cree la función, programa o expresión más corta que calcule A073329 , es decir, a(n)es el enésimo número que tiene n factores primos distintos. La entrada es el número de elementos en la secuencia a devolver. 0 < n. No me preocupa la precisión entera. Solo quiero el algoritmo. Para los idiomas que no admiten enteros arbitrariamente grandes, solo pretendemos que lo hacen.

Puede encontrar casos de prueba siguiendo el enlace a OEIS que se encuentra arriba.

ACTUALIZAR:

Permítame dejar en claro que necesita devolver una secuencia entera de su programa, función o expresión. En otras palabras, f(x)debe calcular a(n)para todos nde 1 a x. Dado x8, su función debería retornar 2, 10, 60, 420, 4290, 53130, 903210, 17687670como una matriz o alguna otra estructura de datos apropiada.

Gregory Higley
fuente
Límites / límites?
2011
No estoy realmente preocupado por los límites y límites, pero si es importante para usted, realice el algoritmo asumiendo que la entrada no será más de 8, y simularemos que funciona para números más altos. Como dije, estoy interesado en el algoritmo matemático abstracto, no en los detalles de las limitaciones de enteros de un lenguaje en particular.
Gregory Higley
1
Tal vez sea más abierto, cuando decimos: en output a(1), ... a(n)lugar de devolver algo, como una serie de ...
usuario desconocido

Respuestas:

2

Python, 144 caracteres

R=range
P=[x for x in R(2,99)if all(x%i for i in R(2,x))]
for a in R(input()):
 x=n=0
 while n<=a:n+=sum(x%p==0for p in P)==a+1;x+=1
 print x-1

Se tarda unos 2 minutos en completarse para x = 8.

Keith Randall
fuente
2

Java, 170 caracteres en una línea

int a(int n) {
    int a = 2, t = a, m = 1, i = 1;
    Set s = new HashSet();
    while (i++ > 0) {
        if (t % i == 0) {
            s.add(i);
            t /= i;
            if (t == 1) {
                if (s.size() == n) {
                    if (n == m) {
                        break;
                    }
                    m++;
                }
                t = ++a;
                s.clear();
            }
            i = 1;
        }
    }
    return a;
}

Actualización, +77 caracteres IOL

int[] f(int n) {
    int[] f = new int[n];
    for (int i = 0; i < n; i++) {
        f[i] = a(i+1);
    }
    return f;
}
cubanacan
fuente
Esto es realmente incorrecto, pero cercano, aunque creo que quizás debería aclarar mi pregunta. Deberías devolver una secuencia entera. Por ejemplo, si la entrada 8, debe devolver los primeros 8 elementos en la secuencia A073329.
Gregory Higley
@Gregory mira la actualización
cubanacan
Lo siento, te voté en contra, debido a mi propio malentendido de la tarea, que se aclaró después de leer el enlace OEIS. Si realiza una edición menor de su publicación, puedo revocar mi voto negativo.
usuario desconocido
@user debido a mi propio malentendido de su comentario, aclare su solicitud, por favor
cubanacan
Entendí mal la pregunta y pensé que todos los factores deben ser números primos distintos, por lo que 2 * 3 * 5 * 2 sería una respuesta incorrecta. Así que rechacé su respuesta por ser falsa. Entonces descubrí lo comprensibles que son los "primos distintos" y quise corregir mi voto, pero no se me permite cambiar mi voto, solo es posible en los primeros minutos. Pero si edita su respuesta, puedo cambiar mi voto. Así que te pido que edites solo un poco.
usuario desconocido
2

Java (sin golf)

public class M {

    public static void main(String[] a) {
        final int N = 100000000;
        int[] p = new int[N];
        for(int f = 2; f * f < N; f++) {
            if(p[f] == 0)
                for(int k = f; k < N; k += f)
                    p[k]++;
        }
        for(int i = 1; i <= 8; i++) {
            int c = 0, j;
            for(j = 1; j < N && c < i; j++)
                if(p[j] == i)
                    c++;
            if(c == i)
                System.out.println(i + " = " + --j);
        }
    }
}

Utiliza un algoritmo de tamiz. Es muy rapido. (6 segundos) Funcionará con precisión por hasta 8, probablemente fallará por algo más alto.

st0le
fuente
1

JavaScript, 149 caracteres

function(n){function f(x){for(r=[],o=x,z=2;z<=o;x%z?++z:(x/=z,r.indexOf(z)+1?0:r.push(z)));return r}for(c=0,i=1;c<n;)f(++i).length==n?c++:0;return i}

Siente que no responde n> = 6, así que no he probado cuánto tiempo lleva (mi navegador muestra una notificación de script colgado cada 10 segundos más o menos, por lo tanto, no puedo cronometrarlo con precisión y no quiero colgarlo por completo si marca "no mostrar esto de nuevo" ...)

Editar: para devolver la matriz es de 200 caracteres (+51) :

function(n){function F(){function f(x){for(r=[],o=x,z=2;z<=o;x%z?++z:(x/=z,r.indexOf(z)+1?0:r.push(z)));return r}for(c=0,i=1;c<n;)F(++i).length==n?c++:0;return i}for(a=[];n>0;n--)a.push(f());return a}
Ry-
fuente
0

J, 32 bytes

({"0 1~i.@#)(]/.~#@~.@q:)

Pero como estoy respondiendo mi propia pregunta tan tarde, dejaremos esta respuesta como curiosidad.

Gregory Higley
fuente