_{(a través del chat )}

La entrada OEIS A123321 enumera la secuencia de números que son el producto de siete primos distintos. Por brevedad, llamaremos a esto un número 7DP . Los primeros números y sus divisores correspondientes están a continuación:

510510 = 2 * 3 * 5 * 7 * 11 * 13 * 17
570570 = 2 * 3 * 5 * 7 * 11 * 13 * 19
690690 = 2 * 3 * 5 * 7 * 11 * 13 * 23
746130 = 2 * 3 * 5 * 7 * 11 * 17 * 19

El desafío aquí será encontrar el número 7DP más cercano, en términos de distancia absoluta, de una entrada dada.

Entrada

Un solo entero positivo n en cualquier formato conveniente .

Salida

El número 7DP más cercano a n , nuevamente en cualquier formato conveniente. Si dos números 7DP están empatados para el más cercano, puede generar uno o ambos.

Reglas

• Se puede suponer que los números encajan en el [int]tipo de datos predeterminado de su idioma (o equivalente).
• Un programa completo o una función son aceptables.
• Las lagunas estándar están prohibidas.
• Este es el código de golf , por lo que se aplican todas las reglas habituales de golf, y gana el código más corto.

Ejemplos

5 -> 510510
860782 -> 870870
1425060 -> 1438710 (or 1411410, or both)

Python, 89 86 85 bytes

f=lambda n,k=0:126^sum(1>>n%i<<7*(n/i%i<1)for i in range(2,n))and f(n+k,k%2*2+~k)or n

Para empezar, el algoritmo es O (aterrador) y la recursión realmente no ayuda, pero funciona bien siempre que n esté lo suficientemente cerca de un número de 7DP.

¡Gracias a @xnor por jugar golf 3 bytes!

Probarlo en repl.it .

Cómo funciona

Python no tiene funciones integradas de primalización o factorización, pero podemos identificar los números 7DP por la cantidad y la naturaleza de sus divisores.

Por el principio de multiplicación, el número de divisores de un número entero se puede calcular como el producto de los exponentes incrementados de su factorización prima. Por lo tanto, σ ₀ (n) ( función divisor ) es 2 ^m siempre que n sea ​​un número mDP.

σ ₀ (n) = 128 es, por lo tanto, una condición necesaria, pero no es suficiente; por ejemplo, σ ₀ (2 ¹²⁷ ) = 128 , pero 2 ¹²⁷ claramente no es un número 7DP. Sin embargo, si σ ₀ (n) = 128 y ningún cuadrado perfecto divide n uniformemente, entonces n es un número de 7DP.

Para la entrada n , el algoritmo consiste en inspeccionar los enteros n , n - 1 , n + 1 , n - 2 , n + 2 , etc. y devolver el primero que es un número 7DP.

Cuando se llama f con el argumento n , sucede lo siguiente:

• El código

  126^sum(1>>n%i<<7*(n/i%i<1)for i in range(2,n))

  prueba si n no es un número 7DP de la siguiente manera.

  Para todos los enteros i tal que 1 <i <n , 1>>n%i<<7*(n/i%i<1)se evalúa.

  • Si n es divisible por i pero no por i ² , se 1>>n%iobtiene 1 y se (n/i%i<1)obtiene 0 , lo que resulta en
    1 · 2 ^{7 · 0} = 1 .

  • Si n es divisible por i ² , 1>>n%iy (n/i%i<1)ambos producen 1 , lo que resulta en 1 · 2 ^{7 · 1} = 128 .

  • Si n no es divisible por i , se 1>>n%iobtiene 0 , lo que resulta en 0 · 2 ^{7 · x} = 0 .

  
  La suma de los números enteros resultantes será 2 ^m - 2 si n es un número MDP (sus 2 ^m divisores, excluyendo 1 y n ) y un mayor número de 127 si n tiene un factor cuadrado perfecto. Por lo tanto, la suma será 126 si y solo si n es un número 7DP.

• Para los números 7DP, la suma es 126 , por lo que XOR con 126 produce 0 , lo cual es falso. Por lo tanto, la o parte de la lambda se ejecuta yf devuelve el valor actual de n .

• Si n no es un número 7DP, XOR devolverá un valor verdadero distinto de cero. Por lo tanto, se ejecuta la parte y de la lambda.

  f(n+k,k%2*2+~k)

  llama recursivamente f con valores actualizados de n (el siguiente número potencial de 7DP) yk (la diferencia entre el nuevo candidato y el siguiente).

  Si k es un entero par, no negativo, k%2*2produce 0 y ~kproduce - (k + 1) . La suma de ambos resultados es - (k + 1) , que es un entero impar impar que es 1 mayor en valor absoluto que k .

  Si k es un entero impar, negativo, k%2*2produce 2 y ~kproduce - (k + 1) . La suma de ambos resultados es 2 - (k + 1) = - (k - 1) , que es un número entero no negativo par que es 1 unidad mayor en valor absoluto que k .

  Esto significa que k toma los valores 0, -1, 2, -3, 4, ⋯ .

  Cuando se agregan acumulativamente a n ₀ (el valor inicial de n ), los enteros resultantes son

  • n ₀ + 0
  • ( n ₀ + 0) - 1 = n ₀ - 1
  • ( n ₀ - 1) + 2 = n ₀ + 1
  • ( n ₀ + 1) - 3 = n ₀ - 2
  • ( n ₀ - 2) + 4 = n ₀ + 2
  • etc.

  
  asegurándose de que el primer número 7DP que encontramos es lo más cercano a n ₀ como sea posible.

Brachylog , 44 40 16 bytes

_{Tachado 44 sigue siendo regular 44; (}

:I=+.>0,.$pPdPl7

Ejemplo:

?- run_from_atom(':I=+.>0,.$pPdPl7',1425060,Z).
Z = 1438710 .

¿Podría ser que este lenguaje no siempre apesta? ¡Le gané a Jelly y MATL!

El caso de prueba con 5es el más largo y toma alrededor de 10 segundos en mi máquina.

Esto sería de 12 bytes si $pno se corrigiera (no necesitaríamos la >0,.parte)

Explicación

Brachylog utiliza la programación de lógica de restricción por defecto para toda la aritmética de enteros. Además, el etiquetado integrado =funciona en dominios posiblemente infinitos.

Se unifica sucesivamente una variable sin restricciones (es decir, en (-inf, inf)) como tal: 0, 1, -1, 2, -2, 3, ….

Por lo tanto, podemos obtener el número 7DP más cercano al buscar el primer número Iunificado en (-inf, inf)(usando el seguimiento automático), para el cual Input + Ies un número 7DP.

:I=                Label variables in [Input, I]. I has no constraints and Input is known
   +.              Unify Output with Input + I
     >0,           Output > 0 (wouldn't be needed if $p failed for numbers less than 1)
        .$pP       Unify P with the list of prime factors of Output
            dP     Check that P with duplicates removed is still P
              l7   Check that the length of P is 7

Jalea, 17 bytes

Pµạ³,
×⁹ÆRœc7Ç€ṂṪ

Funciona en teoría, pero lleva muchos años completarlo.

Aquí hay una versión que realmente funciona para las entradas dadas, pero teóricamente falla para entradas grandes:

Pµạ³,
50ÆRœc7Ç€ṂṪ

Pruébalo aquí. Esto genera todos los primos hasta 50, luego encuentra todas las 7 combinaciones de primos en esa lista y luego todos sus productos. Finalmente, simplemente encuentra el elemento más cercano de esa lista al argumento dado.

Por supuesto, una vez que nuestros 7DP contengan primos superiores a 50, esto fallará. La versión teórica genera todos los números primos hasta 256n para una entrada n , pero por lo demás funciona de la misma manera.

Prueba

Deje p(x)denotar el siguiente primo después x. Un límite superior (extremadamente suelto) para el producto 7DP más cercano a x es:

p(x) * p(p(x)) * p(p(p(x))) * ... * p(p(p(p(p(p(p(x)))))))

Por lo tanto, solo necesitamos verificar los números primos en [2… p (p (p (p (p (p (p (p (x))))))))]] . El postulado de Bertrand dice que p (x) ≤ 2x , por lo que es suficiente verificar todos los primos hasta 128x .

MATL , 21 17 16 14 13 bytes

¡Gracias a Dennis por una sugerencia que eliminó 4 bytes y otra que ahorró 1 byte más!

t17*Zq7XN!pYk

Esto funciona en teoría, pero se queda sin memoria para las entradas anteriores 6(compilador en línea).

Una versión más eficiente usa 21 bytes y calcula todos los casos de prueba en aproximadamente un segundo:

t3e4/k16+_YqZq7XN!pYk

Pruébalo en línea!

• Versión con memoria ineficiente
• Versión de memoria eficiente
• Versión de memoria eficiente, todos los casos de prueba

Explicación

Versión de memoria eficiente

Tome la entrada N = 860782como ejemplo. Es suficiente considerar primos hasta M = 29, que es el primer primo multiplicado por 2*3*5*7*11*13excede N . En este ejemplo 2*3*5*7*11*13*29 = 870870,. El próximo primo es 31. Cualquier producto que implica que el primer o mayor habrá por lo menos 2*3*5*7*11*13*31 = 930930, y por lo que está garantizado no ser la solución, porque excede 870870el cual supera N .

M se calcula como el primer primo mayor que max(N/(2*3*5*7*11*13), 16). La maxfunción se utiliza para garantizar que al menos 17se elija. Para guardar algunos bytes, el código reemplaza 2*3*5*7*11*13 = 30030por 30000y funciona maxpor adición. Estos cambios son válidos porque dan un valor mayor.

t      % Take input implicitly. Duplicate
3e4/k  % Divide input by 30000 and round down (rounding here is only needed
       % due to a bug in the "next prime" function)
16+    % Add 16
_Yq    % Next prime
Zq     % Prime numbers up to that value
7XN    % Combinations of those primes taken 7 at a time. Gives a 2D array
       % with each combination on a different row
!p     % Product of each row
Yk     % Output product that is closest to the input. Implicitly display

Versión con memoria ineficiente

Para reducir aún más el número de bytes, se puede eliminar la división; de hecho, es suficiente multiplicar por 17(gracias, @Dennis). Esto asegura que se incluya el próximo número primo (según el postulado de Bertrand ) y que el resultado sea al menos 17. Esto funciona en teoría, pero se queda sin memoria para entradas más grandes que aproximadamente 6.

En el código, la sección

3e4/k  % Divide input by 30000 and round down (rounding here is only needed
       % due to a bug in the "next prime" function)
16+    % Add 16
_Yq    % Next prime

es reemplazado por

17*    % Multiply by 17

Pyke, 32 bytes

#PDl 7q.ID}lRlqi*(#)DF-X,)R],She

Pruébalo aquí!

Tenga en cuenta que esto no funciona en línea, se agota el tiempo de espera. Esta versión solo busca 2 primos distintos y debería funcionar más rápido. Cuando hay 2 números de la misma distancia del objetivo, elige el más bajo.

Esto pasa por todos los números hasta que encuentra uno que es más grande que la entrada y es un 7DP. Para cada número, se deshace de él si no es un 7DP. Luego tiene una lista de 7DP hasta la entrada con una que es más grande. Luego elige el que está más cerca de la entrada.

Julia, 59 bytes

!n=sort(map(prod,combinations(17n|>primes,7))-n,by=abs)[]+n

Esto es muy ineficiente, pero funciona para el primer caso de prueba en la práctica y para los demás en teoría.

Con el costo de 5 bytes más, para un total de 64 bytes , la eficiencia se puede mejorar dramáticamente.

!n=sort(map(prod,combinations(n>>14+17|>primes,7))-n,by=abs)[]+n

Pruébalo en línea!

Antecedentes

Como se menciona en la respuesta de @ LuisMendo , el conjunto de números primos que tenemos que considerar para el número 7DP más cercano es bastante pequeño. Es suficiente que el conjunto contenga un número 7DP que sea mayor que la entrada n , que será verdadero si y solo si contiene un primo p ≥ 17 tal que 30300p = 2 · 3 · 5 · 7 · 11 · 13 · p ≥ n .

En On, el intervalo que contiene al menos un número primo prueba que el intervalo [x, 1.5x) contiene al menos un número primo siempre que x ≥ 8 . Desde 30030/16384 ≈ 1,83 , que significa que debe haber un primer p en (n / 30030, n / 16384) cuando n> 8 · 30300 = 242400 .

Finalmente, cuando n <510510 , p = 17 es claramente suficiente, por lo que solo necesitamos considerar primos hasta n / 16384 + 17 .

A costa de la eficiencia, podemos considerar primos de hasta 17n . Esto funciona cuando n = 1 y es mucho mayor que n / 16384 + 17 para valores mayores de n .

Cómo funciona

17n|>primesy n>>14+17|>primes(el desplazamiento de bits es equivalente a dividir por 2 ¹⁴ = 16384 ) calcular los rangos primos mencionados en el párrafo anterior. Luego, combinations(...,7)calcula todas las matrices de siete números primos diferentes en ese rango, y asignaprod sobre esos calcula sus productos, es decir, los números 7DP de los cuales elegiremos la respuesta.

Luego, -nresta n prom cada número 7DP, luego sort(...,by=abs)clasifica esas diferencias por sus valores absolutos. Finalmente, seleccionamos la primera diferencia con []y calculamos el número 7DP correspondiente agregando n con +n.

Pyth, 30 bytes

L&{IPbq7lPby#.W!syMH,hhZa0teZ,

Pruébalo en línea!

Banco de pruebas.

(5 tarda demasiado en correr)

Explicación

L&{IPbq7lPby#.W!syMH,hhZa0teZ,

L&{IPbq7lPb     Defines a function y, whose argument is b:
 &                  Return if both the following are true:
  {IPb                  the prime factorization contains no duplicate; and:
      q7lPb             the number of prime factors is 7

           y#.W!syMH,hhZa0teZ,   The main programme. Input as Q.
                             ,QQ Implicit arguments, yield [Q,Q].
             .W                  While
               !syMH                   both numbers do not satisfy y:
                    ,hhZ             increment the first number
                          teZ        and decrement the second number
                        a0           while making it non-negative.

Mathematica 136 80 75 bytes

Este es un enfoque directo, trabajando desde afuera n.

nes un producto primo distinto de 7 si el número de factores primos es 7 ( PrimeNu@#==7) y ninguno de estos factores aparece más de una vez ( SquareFreeQ@#&).

g@n_:=(k=1;While[!(PrimeNu@#==7&&SquareFreeQ@#&)⌊z=n-⌊k/2](-1)^k⌋,k++];z)

Mi presentación anterior (136 bytes) encontró el primer producto de 7 primos distintos arriba ny, si existe, el primer producto de 7 primos distintos abajo n. Entonces simplemente determinó cuál estaba más cerca n. Si los productos eran equidistantes, devolvería ambos.

La versión actual verifica n-1, n + 1, n-2, n + 2 ... hasta que alcanza el primer producto 7-prime-prime. Esta versión más eficiente adopta el enfoque que tomó Dennis.

El avance clave se usó ⌊k/2](-1)^k⌋para devolver la serie, 0, 1, -1, 2, -2 ... El cero se usa para verificar si nes un producto de 7 primos distintos. Por esta razón, Floor(es decir, ⌊...⌋) se usa en lugar de Ceiling.

g[5]
g[860782]
g[1425060]

510510

870870

1438710

05AB1E , 10 bytes

°Åp7.ÆPs.x

Pruébalo en línea!

Intenta todas las combinaciones de 7 de los primeros 10 ** primos de entrada. Se queda sin memoria para entradas mayores de 1.

Considerablemente más eficiente versión de 14 bytes:

5°/7+Åp7.ÆPs.x

Pruébalo en línea!

Utiliza los primeros primos (input / 100000 + 7).