Dado un entero positivo n , calcule el valor de la función Mertens M ( n ) donde
y μ ( k ) es la función de Möbius donde μ ( k ) = 1 si k tiene un número par de factores primos distintos, -1 si k tiene un número impar de factores primos distintos y 0 si los factores primos no son distintos.
- Este es el código de golf, así que cree el código más corto para una función o programa que calcule la función Mertens para un entero de entrada n > 0.
- Esta es la secuencia OEIS A002321 .
Casos de prueba
n M(n)
1 1
2 0
3 -1
4 -1
5 -2
6 -1
7 -2
8 -2
9 -2
10 -1
117 -5
5525 5
7044 -25
8888 4
10000 -23
Respuestas:
Jalea , 6 bytes
Pruébalo en línea! o verificar los casos de prueba más pequeños . (toma un tiempo)
Antecedentes
Esto usa la propiedad
de A002321 , que conduce a la siguiente fórmula recursiva.
Cómo funciona
fuente
Mathematica,
2220 bytesGracias a @miles por guardar 2 bytes.
Explicación
Genere una lista de 1 a entrada.
Encontrar
MoebiusMu
de cada númeroSuma el resultado.
fuente
Python 2,
4537 bytesPruébalo en Ideone .
Antecedentes
Esto usa la propiedad
de A002321 , que conduce a la siguiente fórmula recursiva.
Cómo funciona
Usamos la recursividad no solo para calcular M para los cocientes, sino también para calcular la suma de esas imágenes. Esto ahorra 8 bytes en la siguiente implementación directa.
Cuando se llama f con un solo argumento n , el argumento opcional k por defecto es 2 .
Si n = 1 ,
n<k
produce verdadero y f devuelve este valor. Este es nuestro caso base.Si n> 1 ,
n<k
inicialmente devuelve False yor
se ejecuta el siguiente código .f(n/k)
calcula recursivamente un término de la suma, que se resta del valor de retorno def(n,k+1)
. Este último incrementa k y recursivamente llama f , iterando así sobre los posibles valores de k . Una vez que n <k + 1 o n = 1 ,f(n,k+1)
devolverá 1 , finalizando la recursión.fuente
05AB1E ,
1615 bytesExplicación
Pruébalo en línea!
fuente
Brachylog ,
2220 bytesPruébalo en línea!
Explicación
fuente
Jalea , 9 bytes
Pruébalo en línea! o verificar todos los casos de prueba .
Cómo funciona
fuente
Haskell,
2927 bytesfuente
Jalea , 7 bytes
No muy eficiente Los determinantes son difíciles.
Pruébalo en línea! overificar los casos de prueba más pequeños . (toma un tiempo)
Antecedentes
Esto usa una fórmula de A002321 :
M (n) es el determinante de la matriz booleana A n × n , donde a i, j es 1 si j = 1 o i | j , y 0 de lo contrario.
Cómo funciona
fuente
PHP, 113 bytes
Por lo que sé, php carece de algo como la funcionalidad de números primos, por lo que esto es un poco molesto. Probablemente sea posible hacerlo mejor.
usar como:
fuente
Raqueta 103 bytes
Sin golf:
fuente
CJam (20 bytes)
Demostración en línea
Utiliza la fórmula de OEIS
y el operador de memorando de CJam
j
.Disección
fuente
JavaScript (ES6), 50 bytes
Puerto de la respuesta Python de @ Dennis.
fuente
Julia,
2625 bytesPruébalo en línea!
Antecedentes
Esto usa la propiedad
de A002321 , que conduce a la siguiente fórmula recursiva.
Cómo funciona
¡Redefinimos el operador unario ! para nuestros propósitos.
n÷(2:n)
calcula todos los cocientes requeridos, nuestro redefinido ! se asigna sobre ellos, y finalmente la suma de todas las llamadas recursivas se resta de 1 .Desafortunadamente,
no funciona ya que la suma diádica se ahogará en una colección vacía.
corrige esto, pero no guarda ningún byte y devuelve True para la entrada 1 .
fuente
C,
51 5047 bytesEditar: ¡Gracias a @Dennis por -3 bytes!
fuente
Scala, 53 bytes
Un puerto de la respuesta pythin de Dennis.
He llamado al método
?
, que es un token que no se adhiere a las letras.fuente
Pyth, 12 bytes
Define una función
y
que toma en eln
.Prueba de suite aquí. (Tenga en cuenta que lo que
y
sigue aquí es llamar a la función declarada).fuente
En realidad,
181716 bytesSugerencias de golf bienvenidas. Pruébalo en línea!
Ungolfing
fuente
PARI / GP, 24 bytes
fuente
J, 19 bytes
Calcula la función Mertens al
n
usar la suma de la función Möbius en el rango[1, n]
.Uso
Explicación
fuente