Indagamos por todo internet para así tenerte la respuesta para tu dilema, en caso de alguna inquietud puedes dejarnos tu pregunta y responderemos con gusto, porque estamos para ayudarte.
Solución:
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 sigo pensando que se puede mejorar un poco. Resulta ser más similar al método de campo afín (método de Bose) que los otros artículos que leí habían comunicado.
Esto supone el conocimiento de campos finitos. Considere que $ q = p ^ a $ es una potencia principal, y sea $ F (q) $ nuestro campo base.
El método de campo afín funciona sobre $ F (q ^ 2) $. Tome un generador $ g_2 $ de $ F (q ^ 2) $ y un elemento distinto de cero $ k $ de $ F (q) $ y considere el conjunto $$ a: g_2 ^ a – k g_2 in F_q $$ Esos valores forman una regla de Golomb modular mod $ q ^ 2 – 1 $. Se pueden obtener más reglas multiplicando módulo $ q ^ 2 – 1 $ por cualquier número que sea coprime con el módulo.
El método de campo proyectivo funciona sobre $ F (q ^ 3) $. Tome un generador $ g_3 $ de $ F (q ^ 3) $ y un elemento distinto de cero $ k $ de $ F (q) $ y considere el conjunto $$ 0 cup a: g_3 ^ a – k g_3 in F_q $$ Esos valores forman una regla de Golomb modular mod $ q ^ 2 + q + 1 $. Se pueden obtener más reglas mediante la multiplicación modular de la misma manera que para el método de campo afín.
Tenga en cuenta que estos métodos entre ellos dan los valores más conocidos para cada longitud superior a 16. Tomas Rokicki y Gil Dogon están ofreciendo una recompensa de $ 250 a cualquiera que los supere en longitudes de 36 a 40000. Por lo tanto, cualquiera que supere esta respuesta se encontrará con una premio.
Código
El C # no es muy idiomático, pero lo necesito para compilarlo con una versión antigua de Mono. Además, a pesar de la verificació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 solución realmente buena para eso en C #. Quizás en F # o C ++ con plantillas locas.
using System;
using System.Collections.Generic;
using System.Linq;
namespace Sandbox
class Program
static void Main(string[] args)
var winners = ComputeRulerRange(50, 100);
int total = 0;
for (int i = 50; i <= 100; i++)
Console.WriteLine("0:t1", i, winners[i][i - 1]);
total += winners[i][i - 1];
Console.WriteLine("t0", total);
static IDictionary ComputeRulerRange(int min, int max)
var best = new Dictionary();
var naive = Naive(max);
for (int i = min; i <= max; i++) best[i] = naive.Take(i).ToArray();
var finiteFields = FiniteFields(max * 11 / 10).OrderBy(x => x.Size).ToArray();
// The projective plane method generates rulers of length p^a + 1 for prime powers p^a.
// We can then look at subrulers for a reasonable range, say down to two prime powers below.
for (int ppi = 0; ppi < finiteFields.Length; ppi++)
// Range under consideration
var field = finiteFields[ppi];
int q = field.Size;
int subFrom = Math.Max(min, ppi >= 2 ? finiteFields[ppi - 2].Size : 1);
int subTo = Math.Min(max, q + 1);
if (subTo < subFrom) continue;
int m = q * q + q + 1;
foreach (var ruler in ProjectiveRulers(field))
for (int sub = subFrom; sub <= subTo; sub++)
var subruler = BestSubruler(ruler, sub, m);
if (subruler[sub - 1] < best[sub][sub - 1]) best[sub] = subruler;
// Similarly for the affine plane method, which generates rulers of length p^a for prime powers p^a
for (int ppi = 0; ppi < finiteFields.Length; ppi++)
// Range under consideration
var field = finiteFields[ppi];
int q = field.Size;
int subFrom = Math.Max(min, ppi >= 2 ? finiteFields[ppi - 2].Size : 1);
int subTo = Math.Min(max, q);
if (subTo < subFrom) continue;
int m = q * q - 1;
foreach (var ruler in AffineRulers(field))
for (int sub = subFrom; sub <= subTo; sub++)
var subruler = BestSubruler(ruler, sub, m);
if (subruler[sub - 1] < best[sub][sub - 1]) best[sub] = subruler;
return best;
static int[] BestSubruler(int[] ruler, int sub, int m)
int[] expand = new int[ruler.Length + sub - 1];
for (int i = 0; i < ruler.Length; i++) expand[i] = ruler[i];
for (int i = 0; i < sub - 1; i++) expand[ruler.Length + i] = ruler[i] + m;
int best = m, bestIdx = -1;
for (int i = 0; i < ruler.Length; i++)
if (expand[i + sub - 1] - expand[i] < best)
best = expand[i + sub - 1] - expand[i];
bestIdx = i;
return expand.Skip(bestIdx).Take(sub).Select(x => x - ruler[bestIdx]).ToArray();
static IEnumerable ProjectiveRulers(FiniteField field)
var q = field.Size;
var fq3 = PowerField.Create(field, 3);
var m = q * q + q + 1;
var g = fq3.Generators.First();
// Define the set T = 0 union a in [q^3-1] : g^a - kg in F(q) for 0 != k in F(q)
// This could alternatively be T = 0 union log_g(b - kg) : b in F(q) for 0 != k in F(q)
// Then T % (q^2 + q + 1) gives a Golomb ruler.
// For a given generator we seem to get the same ruler for every k.
var t_k = new HashSet();
t_k.Add(0);
var ga = fq3.One;
for (int a = 1; a < fq3.Size; a++)
ga = ga * g;
if (fq3.Convert(ga + g) < q) t_k.Add(a % m);
// TODO: optimise by detecting duplicates
for (int s = 1; s < m; s++)
if (Gcd(s, m) == 1) yield return t_k.Select(x => x * s % m).OrderBy(x => x).ToArray();
static IEnumerable AffineRulers(FiniteField field)
var q = field.Size;
var fq2 = PowerField.Create(field, 2);
var m = q * q - 1;
var g = fq2.Generators.First();
// Define the set T = 0 union a in [q^2-1] : g^a - kg in F(q) for 0 != k in F(q)
// Then T % (q^2 - 1) gives a Golomb ruler.
var t_k = new HashSet();
var ga = fq2.One;
for (int a = 1; a < fq2.Size; a++)
ga = ga * g;
if (fq2.Convert(ga + g) < q) t_k.Add(a % m);
// TODO: optimise by detecting duplicates
for (int s = 1; s < m; s++)
if (Gcd(s, m) == 1) yield return t_k.Select(x => x * s % m).OrderBy(x => x).ToArray();
static int Gcd(int a, int b)
while (a != 0)
var t = b % a;
b = a;
a = t;
return b;
static int[] Naive(int size)
if (size == 0) return new int[0];
if (size == 1) return new int[] 0 ;
int[] ruler = new int[size];
var diffs = new HashSet();
int i = 1, c = 1;
while (true)
bool valid = true;
for (int j = 0; j < i; j++)
if (diffs.Contains(c - ruler[j])) valid = false; break;
if (valid)
for (int j = 0; j < i; j++) diffs.Add(c - ruler[j]);
ruler[i++] = c;
if (i == size) return ruler;
c++;
static IEnumerable FiniteFields(int max)
bool[] isComposite = new bool[max + 1];
for (int p = 2; p < isComposite.Length; p++)
if (!isComposite[p])
FiniteField baseField = new PrimeField(p); yield return baseField;
for (int pp = p * p, pow = 2; pp < max; pp *= p, pow++) yield return PowerField.Create(baseField, pow);
for (int pq = p * p; pq <= max; pq += p) isComposite[pq] = true;
public abstract class FiniteField
private Lazy _Zero;
private Lazy _One;
public FiniteFieldElement Zero get return _Zero.Value;
public FiniteFieldElement One get return _One.Value;
public IEnumerable Generators
get
for (int _g = 1; _g < Size; _g++)
int pow = 0;
FiniteFieldElement g = Convert(_g), gpow = One;
while (true)
pow++;
gpow = gpow * g;
if (gpow == One) break;
if (pow > Size)
throw new Exception("Is this really a field? " + this);
if (pow == Size - 1) yield return g;
public abstract int Size get;
internal abstract FiniteFieldElement Convert(int i);
internal abstract int Convert(FiniteFieldElement f);
internal abstract bool Eq(FiniteFieldElement a, FiniteFieldElement b);
internal abstract FiniteFieldElement Negate(FiniteFieldElement a);
internal abstract FiniteFieldElement Add(FiniteFieldElement a, FiniteFieldElement b);
internal abstract FiniteFieldElement Mul(FiniteFieldElement a, FiniteFieldElement b);
protected FiniteField()
_Zero = new Lazy(() => Convert(0));
_One = new Lazy(() => Convert(1));
public abstract class FiniteFieldElement
internal abstract FiniteField Field get;
public static FiniteFieldElement operator -(FiniteFieldElement a)
return a.Field.Negate(a);
public static FiniteFieldElement operator +(FiniteFieldElement a, FiniteFieldElement b)
if (a.Field != b.Field) throw new ArgumentOutOfRangeException("b");
return a.Field.Add(a, b);
public static FiniteFieldElement operator *(FiniteFieldElement a, FiniteFieldElement b)
if (a.Field != b.Field) throw new ArgumentOutOfRangeException("b");
return a.Field.Mul(a, b);
public static bool operator ==(FiniteFieldElement a, FiniteFieldElement b)
if (Equals(a, null)) return Equals(b, null);
else if (Equals(b, null)) return false;
if (a.Field != b.Field) throw new ArgumentOutOfRangeException("b");
return a.Field.Eq(a, b);
public static bool operator !=(FiniteFieldElement a, FiniteFieldElement b) return !(a == b);
public override bool Equals(object obj)
return (obj is FiniteFieldElement) && (obj as FiniteFieldElement).Field == Field && this == (obj as FiniteFieldElement);
public override int GetHashCode() return Field.Convert(this).GetHashCode();
public override string ToString() return Field.Convert(this).ToString();
public class PrimeField : FiniteField
private readonly int _Prime;
private readonly PrimeFieldElement[] _Featherweight;
internal int Prime get return _Prime;
public override int Size get return _Prime;
public PrimeField(int prime)
if (prime < 2) throw new ArgumentOutOfRangeException("prime");
// TODO A primality test would be nice...
_Prime = prime;
_Featherweight = new PrimeFieldElement[Math.Min(prime, 256)];
internal override FiniteFieldElement Convert(int i) i >= _Prime) throw new ArgumentOutOfRangeException("i");
if (i >= _Featherweight.Length) return new PrimeFieldElement(this, i);
if (Equals(_Featherweight[i], null)) _Featherweight[i] = new PrimeFieldElement(this, i);
return _Featherweight[i];
internal override int Convert(FiniteFieldElement f)
if (f == null) throw new ArgumentNullException("f");
if (f.Field != this) throw new ArgumentOutOfRangeException("f");
return (f as PrimeFieldElement).Value;
internal override bool Eq(FiniteFieldElement a, FiniteFieldElement b)
if (a.Field != this) throw new ArgumentOutOfRangeException("a");
if (b.Field != this) throw new ArgumentOutOfRangeException("b");
return (a as PrimeFieldElement).Value == (b as PrimeFieldElement).Value;
internal override FiniteFieldElement Negate(FiniteFieldElement a)
if (a.Field != this) throw new ArgumentOutOfRangeException("a");
var fa = a as PrimeFieldElement;
return fa.Value == 0 ? fa : Convert(_Prime - fa.Value);
internal override FiniteFieldElement Add(FiniteFieldElement a, FiniteFieldElement b)
if (a.Field != this) throw new ArgumentOutOfRangeException("a");
if (b.Field != this) throw new ArgumentOutOfRangeException("b");
return Convert(((a as PrimeFieldElement).Value + (b as PrimeFieldElement).Value) % _Prime);
internal override FiniteFieldElement Mul(FiniteFieldElement a, FiniteFieldElement b)
if (a.Field != this) throw new ArgumentOutOfRangeException("a");
if (b.Field != this) throw new ArgumentOutOfRangeException("b");
return Convert(((a as PrimeFieldElement).Value * (b as PrimeFieldElement).Value) % _Prime);
public override string ToString() return string.Format("F(0)", _Prime);
internal class PrimeFieldElement : FiniteFieldElement
private readonly PrimeField _Field;
private readonly int _Value;
internal override FiniteField Field get return _Field;
internal int Value get return _Value;
internal PrimeFieldElement(PrimeField field, int val)
if (field == null) throw new ArgumentNullException("field");
if (val < 0
public class PowerField : FiniteField
private readonly FiniteField _BaseField;
private readonly FiniteFieldElement[] _Polynomial;
internal FiniteField BaseField get return _BaseField;
internal int Power get return _Polynomial.Length;
public override int Size get return (int)Math.Pow(_BaseField.Size, Power);
public PowerField(FiniteField baseField, FiniteFieldElement[] polynomial)
if (baseField == null) throw new ArgumentNullException("baseField");
if (polynomial == null) throw new ArgumentNullException("polynomial");
if (polynomial.Length < 2) throw new ArgumentOutOfRangeException("polynomial");
for (int i = 0; i < polynomial.Length; i++) if (polynomial[i].Field != baseField) throw new ArgumentOutOfRangeException("polynomial[" + i + "]");
// TODO Check that the polynomial is irreducible over the base field.
_BaseField = baseField;
_Polynomial = polynomial.ToArray();
internal override FiniteFieldElement Convert(int i) i >= Size) throw new ArgumentOutOfRangeException("i");
var vec = new FiniteFieldElement[Power];
for (int j = 0; j < vec.Length; j++)
vec[j] = BaseField.Convert(i % BaseField.Size);
i /= BaseField.Size;
return new PowerFieldElement(this, vec);
internal override int Convert(FiniteFieldElement f)
if (f == null) throw new ArgumentNullException("f");
if (f.Field != this) throw new ArgumentOutOfRangeException("f");
var pf = f as PowerFieldElement;
int i = 0;
for (int j = Power - 1; j >= 0; j--) i = i * BaseField.Size + BaseField.Convert(pf.Value[j]);
return i;
internal override bool Eq(FiniteFieldElement a, FiniteFieldElement b)
if (a.Field != this) throw new ArgumentOutOfRangeException("a");
if (b.Field != this) throw new ArgumentOutOfRangeException("b");
var fa = a as PowerFieldElement;
var fb = b as PowerFieldElement;
for (int i = 0; i < Power; i++) if (fa.Value[i] != fb.Value[i]) return false;
return true;
internal override FiniteFieldElement Negate(FiniteFieldElement a)
if (a.Field != this) throw new ArgumentOutOfRangeException("a");
return new PowerFieldElement(this, (a as PowerFieldElement).Value.Select(x => -x).ToArray());
internal override FiniteFieldElement Add(FiniteFieldElement a, FiniteFieldElement b)
if (a.Field != this) throw new ArgumentOutOfRangeException("a");
if (b.Field != this) throw new ArgumentOutOfRangeException("b");
var fa = a as PowerFieldElement;
var fb = b as PowerFieldElement;
var vec = new FiniteFieldElement[Power];
for (int i = 0; i < Power; i++) vec[i] = fa.Value[i] + fb.Value[i];
return new PowerFieldElement(this, vec);
internal override FiniteFieldElement Mul(FiniteFieldElement a, FiniteFieldElement b)
if (a.Field != this) throw new ArgumentOutOfRangeException("a");
if (b.Field != this) throw new ArgumentOutOfRangeException("b");
var fa = a as PowerFieldElement;
var fb = b as PowerFieldElement;
// We consider fa and fb as polynomials of a variable x and multiply modulo (x^Power - _Polynomial).
// But to keep things simple we want to manage the cascading modulo.
var vec = Enumerable.Repeat(BaseField.Zero, Power).ToArray();
var fa_xi = fa.Value.ToArray();
for (int i = 0; i < Power; i++)
for (int j = 0; j < Power; j++) vec[j] += fb.Value[i] * fa_xi[j];
if (i < Power - 1) ShiftLeft(fa_xi);
return new PowerFieldElement(this, vec);
private void ShiftLeft(FiniteFieldElement[] vec)
FiniteFieldElement head = vec[vec.Length - 1];
for (int i = vec.Length - 1; i > 0; i--) vec[i] = vec[i - 1] + head * _Polynomial[i];
vec[0] = head * _Polynomial[0];
public static FiniteField Create(FiniteField baseField, int power)
if (baseField == null) throw new ArgumentNullException("baseField");
if (power < 2) throw new ArgumentOutOfRangeException("power");
// Since the field is cyclic, there is only one finite field of a given prime power order (up to isomorphism).
// For most practical purposes that means that we can pick any arbitrary monic irreducible polynomial.
// We can abuse PowerField to do polynomial multiplication in the base field.
var fakeField = new PowerField(baseField, Enumerable.Repeat(baseField.Zero, power).ToArray());
var excluded = new HashSet();
for (int lpow = 1; lpow <= power / 2; lpow++)
int upow = power - lpow;
// Consider all products of a monic polynomial of order lpow with a monic polynomial of order upow.
int xl = (int)Math.Pow(baseField.Size, lpow);
int xu = (int)Math.Pow(baseField.Size, upow);
for (int i = xl; i < 2 * xl; i++)
var pi = fakeField.Convert(i);
for (int j = xu; j < 2 * xu; j++)
var pj = fakeField.Convert(j);
excluded.Add(-(pi * pj));
for (int p = baseField.Size; true; p++)
var pp = fakeField.Convert(p) as PowerFieldElement;
if (!excluded.Contains(pp)) return new PowerField(baseField, pp.Value.ToArray());
public override string ToString()
var sb = new System.Text.StringBuilder();
sb.AppendFormat("GF(0) with primitive polynomial x^1 ", Size, Power);
for (int i = Power - 1; i >= 0; i--) sb.AppendFormat("+ 0x^1", _Polynomial[i], i);
sb.AppendFormat(" over base field ");
sb.Append(_BaseField);
return sb.ToString();
internal class PowerFieldElement : FiniteFieldElement
private readonly PowerField _Field;
private readonly FiniteFieldElement[] _Vector; // The version of Mono I have doesn't include IReadOnlyList
internal override FiniteField Field get return _Field;
internal FiniteFieldElement[] Value get return _Vector;
internal PowerFieldElement(PowerField field, params FiniteFieldElement[] vector)
if (field == null) throw new ArgumentNullException("field");
if (vector == null) throw new ArgumentNullException("vector");
if (vector.Length != field.Power) throw new ArgumentOutOfRangeException("vector");
for (int i = 0; i < vector.Length; i++) if (vector[i].Field != field.BaseField) throw new ArgumentOutOfRangeException("vector[" + i + "]");
_Field = field;
_Vector = vector.ToArray();
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.
Python 3, puntuación 603001/734078 = 0,82144
Búsqueda ingenua combinada con la construcción de Erdős-Turan:
$$ 2pk + (k ^ 2 bmod p), , k in [0, p-1]$$
Para primos impares pag esto da una regla de golomb asintóticamente óptima.
def isprime(n):
if n < 2: return False
if n % 2 == 0: return n == 2
k = 3
while k*k <= n:
if n % k == 0: return False
k += 2
return True
rulers = []
ruler = []
d = set()
n = 0
while len(ruler) <= 100:
order = len(ruler) + 1
if order > 2 and isprime(order):
ruler = [2*order*k + k*k%order for k in range(order)]
d = a-b for a in ruler for b in ruler if a > b
n = max(ruler) + 1
rulers.append(tuple(ruler))
continue
nd = set(n-e for e in ruler)
if not d & nd:
ruler.append(n)
d |= nd
rulers.append(tuple(ruler))
n += 1
isuniq = lambda l: len(l) == len(set(l))
isruler = lambda l: isuniq([a-b for a in l for b in l if a > b])
assert all(isruler(r) for r in rulers)
rulers = list(sorted([r for r in rulers if 50 <= len(r) <= 100], key=len))
print(sum(max(r) for r in rulers))
Mathematica, puntuación 276235/734078 <0.376302
ruzsa[p_, i_] := Module[g = PrimitiveRoot[p],
Table[ChineseRemainder[t, i PowerMod[g, t, p], p - 1, p], t, 1, p - 1] ]
reducedResidues[m_] := Select[[email protected], CoprimeQ[m, #] &]
rotate[set_, m_] := Mod[set - #, m] & /@ set
scaledRuzsa[p_] := Union @@ Table[ [email protected][a b, p (p - 1)],
a, reducedResidues[p (p - 1)], b, rotate[ruzsa[p, 1], p (p - 1)]]
manyRuzsaSets = Join @@ Table[scaledRuzsa[Prime[n]], n, 32];
tryGolomb[set_, k_] := If[Length[set] < k, Nothing, Take[set, k]]
Table[[email protected][tryGolomb[#, k] & /@ manyRuzsaSets, Max], k, 50, 100]
La función ruzsa implementa una construcción de una regla de Golobm (también llamada un conjunto de Sidón) que se encuentra en Imre Z. Ruzsa. Resolver una ecuación lineal en un conjunto de números enteros. I. Acta Arith., 65 (3): 259–282, 1993. Dada cualquier prima p, esta construcción produce una regla de Golomb con p-1 elementos contenidos en el módulo de enteros p(p-1) (esa es una condición aún más fuerte que ser un gobernante de Golomb en los números enteros).
Otra ventaja de trabajar en el módulo de enteros m es que cualquier regla de Golomb se puede rotar (la misma constante agregada a todos los elementos módulo m), y escalado (todos los elementos multiplicados por la misma constante, siempre que esa constante sea relativamente prima de m), y el resultado sigue siendo un gobernante de Golomb; a veces, el número entero más grande se reduce significativamente al hacerlo. Entonces la función scaledRuzsa prueba todas estas escalas y registra los resultados. manyRuzsaSets contiene los resultados de hacer esta construcción y escalar para los primeros 32 primos (elegidos un poco arbitrariamente, pero el 32º primo, 131, es bastante mayor que 100); hay cerca de 57.000 reglas de Golomb en este conjunto, lo que lleva varios minutos calcular.
Por supuesto, el primero k Los elementos de un gobernante Golomb forman ellos mismos un gobernante Golomb. Entonces la función tryGolomb mira una regla de este tipo hecha a partir de cualquiera de los conjuntos calculados anteriormente. La ultima linea Table... selecciona la mejor regla de Golomb que puede, de cada orden de 50 para 100, de todos los gobernantes de Golomb encontrados de esta manera.
Las longitudes encontradas fueron:
2241, 2325, 2399, 2578, 2640, 2762, 2833, 2961, 3071, 3151, 3194, 3480, 3533, 3612, 3775, 3917, 4038, 4150, 4237, 4368, 4481, 4563, 4729, 4974, 5111, 5155, 5297, 5504, 5583, 5707, 5839, 6077, 6229, 6480, 6611, 6672, 6913, 6946, 7025, 7694, 7757, 7812, 7969, 8139, 8346, 8407, 8678, 8693, 9028, 9215, 9336
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.
Calificaciones y reseñas
Al final de todo puedes encontrar las notas de otros usuarios, tú igualmente tienes la opción de insertar el tuyo si te apetece.