Las reglas de Golomb son conjuntos de enteros no negativos, de modo que no hay dos pares de enteros en el conjunto a la misma distancia.
Por ejemplo, [0, 1, 4, 6]
es una regla de Golomb porque todas las distancias entre dos enteros en este conjunto son únicas:
0, 1 -> distance 1
0, 4 -> distance 4
0, 6 -> distance 6
1, 4 -> distance 3
1, 6 -> distance 5
4, 6 -> distance 2
En aras de la simplicidad en este desafío (y dado que la traducción es trivial), imponemos que una regla de Golomb siempre contenga el número0
(lo que hace el ejemplo anterior).
Como este conjunto es largo 4
, decimos que es una regla de orden Golomb 4
. La mayor distancia en este conjunto (o elemento, ya 0
que siempre está en el conjunto) es 6
, por lo tanto, decimos que esta es una regla de Golomb de longitud 6
.
Tu tarea
Encuentre las reglas de orden de Golomb 50
para 100
(inclusive) que tengan el mismo tamaño longitudes como se puede encontrar. Las reglas que encuentre no necesitan ser óptimas (ver más abajo).
Óptima
Se N
dice que una regla de orden Golomb es óptima si no hay otra regla de orden Golomb N
que tenga una longitud menor.
Los gobernantes Golomb óptimos son conocidos por órdenes de menos de 28 , aunque encontrar y probar la optimización es cada vez más difícil a medida que aumenta el orden.
Por lo tanto, no se espera que encuentre la regla Golomb óptima para ninguna de las órdenes entre 50
y 100
(y aún menos se espera que pueda probar que son óptimas).
No hay límites de tiempo en la ejecución de su programa.
Base
La lista a continuación es la lista de longitudes de gobernantes Golomb desde ( 50
hasta 100
en orden) evaluados con una estrategia de búsqueda ingenua (Gracias a @PeterTaylor por esta lista):
[4850 5122 5242 5297 5750 5997 6373 6800 6924 7459 7546 7788 8219 8502 8729 8941 9881 10199 10586 10897 11288 11613 11875 12033 12930 13393 14046 14533 14900 15165 15687 15971 16618 17354 17931 18844 19070 19630 19669 20721 21947 22525 23290 23563 23880 24595 24767 25630 26036 26254 27218]
La suma de todas esas longitudes es 734078
.
Puntuación
Su puntuación será la suma de las longitudes de todos sus gobernantes Golomb entre 50
y 100
, dividido por la suma de las longitudes de los gobernantes entre Golomb 50
y 100
en la línea de base: 734078
.
En caso de que no haya encontrado una regla Golomb para un orden específico, calculará su puntaje de la misma manera, utilizando el doble de la longitud en la línea de base para ese orden específico.
La respuesta con la puntuación más baja gana.
En caso de empate, se comparan las longitudes del orden más grande donde las dos respuestas difieren, y gana la más corta. En caso de que ambas respuestas tengan la misma longitud para todos los pedidos, entonces la respuesta que se publicó primero gana.
fuente
n
esn(n-1)/2
, ya que esa es la cantidad de diferencias positivas que hay. Por lo tanto, el puntaje más pequeño posible en este desafío es147050/734078 > 0.2003193
.Respuestas:
C #, 259421/734078 ~ = 0.3534
Métodos
Finalmente encontré una explicación más o menos legible del método de campo proyectivo (método de Singer) en Construcciones de conjuntos Sidon generalizados , aunque todavía creo que se puede mejorar ligeramente. Resulta ser más similar al método de campo afín (método de Bose) que los otros documentos que leí se habían comunicado.
Tenga en cuenta que estos métodos entre ellos dan los valores más conocidos para cada longitud mayor de 16. Tomas Rokicki y Gil Dogon están ofreciendo una recompensa de $ 250 para cualquiera que los supere por longitudes de 36 a 40000. Por lo tanto, cualquiera que supere esta respuesta tendrá un precio monetario premio.
Código
El C # no es muy idiomático, pero lo necesito para compilar con una versión antigua de Mono. Además, a pesar de la comprobación de argumentos, este no es un código de calidad de producción. No estoy contento con los tipos, pero no creo que haya una buena solución para eso en C #. Tal vez en F # o C ++ con plantillas locas.
Resultados
Desafortunadamente, agregar las reglas me llevaría unos 15k caracteres más allá del límite de tamaño de la publicación, por lo que están en pastebin .
fuente
Python 3, puntaje 603001/734078 = 0.82144
Búsqueda ingenua combinada con la construcción Erdős – Turan:
Para números primos impares p esto proporciona una regla de golomb asintóticamente óptima.
fuente
p
y longitud aproximadamente2p^2
, mientras que existen reglas Golomb de ordenn
y longitud aproximadamenten^2
asintóticamente.2p^2
yp^2
.Mathematica, puntaje 276235/734078 <0.376302
La función
ruzsa
implementa una construcción de una regla de Golobm (también llamada conjunto Sidon) que se encuentra en Imre Z. Ruzsa. Resolver una ecuación lineal en un conjunto de enteros. I. Acta Arith., 65 (3): 259–282, 1993 . Dado cualquier primop
, esta construcción produce una regla Golomb conp-1
elementos contenidos en el módulo de enterosp(p-1)
(esa es una condición aún más fuerte que ser una regla Golomb en los propios números enteros).Otra ventaja de trabajar en el módulo de enteros
m
es que cualquier regla de Golomb puede rotarse (la misma constante agregada a todos los elementos del módulom
) y escalarse (todos los elementos multiplicados por la misma constante, siempre que esa constante sea relativamente primom
), y el resultado sigue siendo una regla Golomb; a veces, el entero más grande disminuye significativamente al hacerlo. Entonces, la funciónscaledRuzsa
prueba todos estos escalamientos y registra los resultados.manyRuzsaSets
contiene los resultados de hacer esta construcción y escala para todos los primeros 32 primos (elegidos un poco arbitrariamente, pero el 32º primo, 131, es bastante mayor que 100); Hay casi 57,000 gobernantes Golomb en este conjunto, lo que lleva unos buenos minutos para calcular.Por supuesto, los primeros
k
elementos de una regla Golomb forman una regla Golomb. Entonces, la funcióntryGolomb
analiza dicha regla hecha a partir de cualquiera de los conjuntos calculados anteriormente. La última líneaTable...
selecciona la mejor regla Golomb que pueda, de cada orden desde50
hasta100
, de todas las reglas de Golomb encontraron de esta manera.Las longitudes encontradas fueron:
Originalmente iba a combinar esto con otras dos construcciones, las de Singer y Bose; pero parece que la respuesta de Peter Taylor ya ha implementado esto, por lo que presumiblemente simplemente recuperaría esas longitudes.
fuente
m
puede rotar / escalar libremente. Mira el[0, 1, 4, 6]
mod 7. Si agrego 1 obtenemos[0, 1, 2, 5]
, que no es una regla de Golomb.[0, 1, 4, 6]
no es una regla de Golomb mod-7 porque1 – 0
es igual al0 – 6
módulo 7, por ejemplo.