OFFSET
1,1
COMMENTS
a(8) = 0 means there is NO prime satisfying the condition. a(n) is known for 1 <= n <= 2000.
LINKS
Jeremy F. Alm, Table of n, a(n) for n = 1..2000
Jeremy F. Alm and Jacob Manske, Sum-free cyclic multi-bases and constructions of Ramsey algebras, Discrete Applied Mathematics, (180), Jan 10 2015, pp. 204-212. (arXiv:1307.0889 [math.CO], 2013-2014.)
Jeremy F. Alm, 401 and beyond: improved bounds and algorithms for the Ramsey algebra search, Journal of Integer Sequences, Vol. 20 (2017), Article 17.8.4. (Also here: arXiv:1609.01817 [math.NT], 2016.)
Tomasz Kowalski, Representability of Ramsey Relation Algebras, Algebra Universalis, Volume 74, Issue 3-4, November 2015, pp. 265-275.
PROG
(Python)
import numpy as np
import itertools
from copy import copy
from sympy.ntheory.residue_ntheory import primitive_root
def psieve():
for n in [2, 3, 5, 7]:
yield n
D = {}
ps = psieve()
next(ps)
p = next(ps)
assert p == 3
psq = p*p
for i in itertools.count(9, 2):
if i in D:
step = D.pop(i)
elif i < psq:
yield i
continue
else:
assert i == psq
step = 2*p
p = next(ps)
psq = p*p
i += step
while i in D:
i += step
D[i] = step
def check_p_m_v6(p, m, g):
''' checks a prime p with primitive root g for m colors '''
X0 = np.array( [pow(g, i, p) for i in range(0, p-m, m) ] )
certificates = np.array([ pow(g, i, p) for i in range(m) ])
C_minus_X0 = ( ( certificates[:, np.newaxis] - X0 ) % p )
C_minus_X0_sets = [ set(L) for L in C_minus_X0 ]
for i in range(m):
Xi = {pow(g, x+i, p) for x in range(0, p-m, m)}
for j in range(i, m):
if bool(Xi.intersection(C_minus_X0_sets[j])) == bool(j == 0):
return False
return True
def main(mikelist):
''' Accepts a list of m's, checks all candidate primes until it finds one that works.
Will NOT terminate for m=8 or m=13 '''
lget = primitive_root ### GIVE FUNCTIONS LOCAL NAMES ###
lcheck = check_p_m_v6
with open("401output.csv", 'a') as file:
for mike in mikelist:
primes = psieve()
prime = next(primes)
while prime < 2*mike**2 - 4*mike:
prime = next(primes)
while True:
if (prime-1)/2 % mike == 0:
gen = lget(prime)
p_out = lcheck(prime, mike, gen)
if p_out == True:
print mike, prime, gen
file.write(str(mike) + ', ' + str(prime) + ', ' + str(gen) + '\n')
break
prime = next(primes)
mrange = range(2, 8) + range(9, 13) + range(14, 101) # a good place to start
main(mrange)
CROSSREFS
KEYWORD
nonn
AUTHOR
Jeremy F. Alm, Oct 13 2015
EXTENSIONS
More terms from Jeremy F. Alm, Sep 05 2016
STATUS
approved