CJam (69 bytes)
]qi:X,{1e|,:):N{N\f{1$%!*}W$.*:+}%1$W%.*:+N,/+}/W\+_1,*X=\_W%.*:+-Y/z
Demostración en línea
Explicación
La idea básica es implementar la función de generación descrita en OEIS. La entrada es un caso especial desagradable, pero los ajustes finales que hice terminaron produciendo para ese caso, por lo que la (para el valor absoluto) lo arregla. Ese es el truco más raro aquí.0 0- 1z
.*:+se repite tres veces y parece que podría guardar un byte si se extrae como {.*:+}:F~. Sin embargo, esto rompe con el caso especial , porque no ejecuta el bucle externo en absoluto.0
Utilizamos la función de generación auxiliar para A000081 , cuyos términos tienen la recurrencia
a[0] = 0
a[1] = 1
For n >= 1, a[n+1] = (sum_{k=1}^n a[n-k+1] * sum_{d|k} d * a[d]) / n
Estoy seguro de que algunos idiomas tienen incorporados para la transformación inversa de Möbius , pero CJam no; el mejor método que he encontrado es la construcción de una matriz de asignación a y luego hacer una multiplicación punto a punto con uso . Tenga en cuenta que aquí es conveniente haber creado inicio en el índice 1, porque queremos evitar la división por cero al configurar los pesos. Tenga en cuenta también que si las dos matrices suministradas a la operación puntual no tienen la misma longitud, entonces los valores de la más larga no se modifican: por lo tanto, debemos tomar los primeros términos de o hacer que la matriz de pesos suba a∑d∣kd×a[d]dk % d == 0 ? d : 0a.*akan. Este último parece más corto. Entonces, esta transformación inversa de Möbius explicaN\f{1$%!*}W$.*:+
Si llamamos al resultado de la transformación inversa de Möbius M, ahora tenemos
a[n+1]=1n∑k=1na[n−k+1]×M[k]
El numerador es obviamente un término de una convolución, por lo que podemos manejarlo invirtiendo una copia de o y luego tomando una multiplicación puntual y sumando. Nuevamente, nuestro índice varía de a , y además queremos emparejar índices que sumen , por lo que nuevamente es conveniente indexar desde 1 en lugar de 0. Ahora hemos contabilizadoaM1nn+1a
qi:X,{ ,:):N{N\f{1$%!*}W$.*:+}%1$W%.*:+N,/+}/
El punto de la función de generación auxiliar viene dado por la sección de fórmula de A000055:
G.f.: A(x) = 1 + T(x) - T^2(x)/2 + T(x^2)/2,
where T(x) = x + x^2 + 2*x^3 + ... is the g.f. for A000081.
En términos de , esto significa que la salida que buscamos esa
[x=0]+a[x]+12(a[x/2]−∑i=0na[i]×a[n−i])
donde para con impar obtenemos 0. La forma más corta que he encontrado para hacerlo es inflar con ceros ( ) y luego tomar el elemento X ( ).a[x/2]x1,*X=
Tenga en cuenta que la suma es otra convolución, pero esta vez es conveniente indexar desde 0. La solución obvia es 0\+, pero aquí hay una pequeña optimización agradable. Como , dos términos de la convolución están garantizados como cero. Podríamos tomar esto como una oportunidad para indexar desde 1, pero el caso especial pone feo. Si por el contrario lo hacemos , la convolución nos da y después de la resta y la división por hemos manejado la plazo fuera de la suma también.a[0]=0X=0W\+−2a[x]+∑ni=0a[i]×a[n−i]2a[x]
Entonces hemos explicado
qi:X,{ ,:):N{N\f{1$%!*}W$.*:+}%1$W%.*:+N,/+}/W\+_1,*X=\_W%.*:+-Y/
Los detalles restantes se refieren al caso especial. Originalmente seguí la recurrencia más estrictamente comenzando 1]e iterando desde conN=1
1]qi:X,1>{ ... }/
El resultado cuando es que calculamos como : un término más de lo que necesitamos. La inflación y la convolución terminan dando un resultado de . (Quizás mejor de lo que merecemos, es lo que deberíamos tener, porque no hemos hecho nada sobre el término ). Así que lo arreglamos para tres caracteres, ya sea como final o usando la técnica estándar de "respaldo" como .X=0a[-1 1]0[x=0]X!+1e|
Para obtener la longitud "correcta" de debemos evitar suministrar ese inicial y, en su lugar, producirlo desde el bucle principal con . Un completamente sencilloa1N=0
]qi:X,{ ... /+}/
obviamente da división por cero. Pero si lo intentamos
]qi:X,{1e| ... /+}/
entonces funciona Obtenemos
e# Stack: [] 0
1e| e# Stack: [] 1
,:):N e# Stack: [] [1]
{ e# We only execute this loop once
N\f{1$%!*} e# 1 divides 1, so stack: [] [1]
W$.* e# Remember: if the two arrays supplied to the pointwise operation
e# are not the same length then the values from the longer one are
e# left untouched. Stack: [] [1]
:+ e# Fold over a singleton. Stack: [] 1
}% e# And that was a map, so stack: [] [1]
1$W%.*:+ e# Another [1] [] .*:+, giving the same result: 1
N,/ e# 1 / 1 = 1
+ e# And we append 1 to a giving [1]
que produce exactamente el valor que requerimos.
Ahora, si ese bucle principal nunca se ejecuta, así que después de hackear un en la parte inferior obtenemos . Terminamos computando , lo cual no es correcto. Pero mientras que corregir a tomó tres caracteres, corregir a solo toma uno: da el valor absoluto.X=0−1[-1]01-11(−1−12(−1×−1))=−101−11z
