login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 4
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 11 14:58 EDT 2021. Contains 343791 sequences. (Running on oeis4.)