A263308 Smallest prime modulus p such that there exists a multiplicative-coset Ramsey algebra in n colors over Z/pZ, or 0 if no such prime exists.

2, 5, 13, 41, 71, 97, 491, 0, 523, 1181, 947, 769, 0, 1709, 1291, 1217, 4013, 2521, 1901, 2801, 1933, 3257, 3221, 4129, 3701, 4889, 5563, 8849, 6323, 5521, 6263, 5441, 8779, 7481, 7841, 10009, 13469, 12161, 8971, 14561, 13367, 19993, 14621, 12497, 14401, 14537, 20117, 18913, 22541, 22901, 19687, 29537

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

Sequence in context: A149867 A062704 A274909 * A288388 A339224 A247981

Adjacent sequences: A263305 A263306 A263307 * A263309 A263310 A263311

Keyword

nonn

Author

Jeremy F. Alm, Oct 13 2015

Extensions

More terms from Jeremy F. Alm, Sep 05 2016

Status

approved