Small Ramsey Numbers

Question

Background: the Ramsey number \$R(r,s)\$ gives the minimum number of vertices \$v\$ in the complete graph \$K_v\$ such that a red/blue edge coloring of \$K_v\$ has at least one red \$K_r\$ or one blue \$K_s\$. Bounds for larger \$r, s\$ are very difficult to establish.

Your task is to output the number \$R(r,s)\$ for \$1 \le r,s \le 5\$.

Input

Two integers \$r, s\$ with \$1 \le r \le 5\$ and \$1 \le s \le 5 \$.

Output

\$R(r,s)\$ as given in this table:

  s   1    2    3    4      5
r +--------------------------
1 |   1    1    1    1      1
2 |   1    2    3    4      5
3 |   1    3    6    9     14
4 |   1    4    9   18     25
5 |   1    5   14   25  43-48

Note that \$r\$ and \$s\$ are interchangeable: \$R(r,s) = R(s,r)\$.

For \$R(5,5)\$ you may output any integer between \$43\$ and \$48\$, inclusive. At the time of this question being posted these are the best known bounds.

Answer 1

JavaScript (ES6), 51 49 bytes

Takes input in currying syntax (r)(s).

r=>s=>--r*--s+[9,1,,13,2,,3,27,6][r<2|s<2||r*s%9]

Try it online!

How?

As a first approximation, we use the formula:

$$(r-1)(s-1)$$

 0  0  0  0  0
 0  1  2  3  4
 0  2  4  6  8
 0  3  6  9 12
 0  4  8 12 16

If we have \$\min(r,s)<3\$, we simply add \$1\$:

 1  1  1  1  1
 1  2  3  4  5
 1  3  -  -  -
 1  4  -  -  -
 1  5  -  -  -

Otherwise, we add a value picked from a lookup table whose key \$k\$ is defined by:

$$k=(r-1)(s-1)\bmod9$$

 k:                    table[k]:           (r-1)(s-1):         output:
 -  -  -  -  -         -  -  -  -  -       -  -  -  -  -       -  -  -  -  -
 -  -  -  -  -         -  -  -  -  -       -  -  -  -  -       -  -  -  -  -
 -  -  4  6  8   -->   -  -  2  3  6   +   -  -  4  6  8   =   -  -  6  9 14
 -  -  6  0  3         -  -  3  9 13       -  -  6  9 12       -  -  9 18 25
 -  -  8  3  7         -  -  6 13 27       -  -  8 12 16       -  - 14 25 43

Answer 2

JavaScript (Node.js), 56 55 bytes

f=(x,y)=>x<2|y<2||f(x,y-1)+f(x-1,y)-(x*y==12)-7*(x+y>8)

Try it online! I noticed that the table resembles Pascal's triangle but with correction factors. Edit: Saved 1 byte thanks to @sundar.

Answer 3

Jelly,  17  16 bytes

’ScḢƊ_:¥9“ ı?0‘y

Try it online! Or see a test-suite.

Replace the 0 with +, ,, -, ., or / to set \$R(5,5)\$ equal to \$43\$, \$44\$, \$45\$, \$46\$, or \$47\$ respectively (rather than the \$48\$ here).

How?

Since \$R(r,s)\leq R(r-1,s)+R(r,s-1)\$ we may find that:

$$R(r,s)\leq \binom{r+s-2}{r-1}$$

This is ’ScḢƊ and would produce:

 1  1  1  1  1
 1  2  3  4  5
 1  3  6 10 15
 1  4 10 20 35
 1  5 15 35 70

If we subtract one for each time nine goes into the result we align three more with our goal (this is achieved with _:¥9):

 1  1  1  1  1
 1  2  3  4  5
 1  3  6  9 14
 1  4  9 18 32
 1  5 14 32 63

The remaining two incorrect values, \$32\$ and \$63\$ may then be translated using Jelly's y atom and code-page indices with “ ı?0‘y.

’ScḢƊ_:¥9“ ı?0‘y - Link: list of integers [r, s]
’                - decrement              [r-1, s-1]
    Ɗ            - last 3 links as a monad i.e. f([r-1, s-1]):
 S               -   sum                  r-1+s-1 = r+s-2
   Ḣ             -   head                 r-1
  c              -   binomial             r+s-2 choose r-1
        9        - literal nine
       ¥         - last 2 links as a dyad i.e. f(r+s-2 choose r-1, 9):
      :          -   integer division     (r+s-2 choose r-1)//9
     _           -   subtract             (r+s-2 choose r-1)-((r+s-2 choose r-1)//9)
         “ ı?0‘  - code-page index list   [32,25,63,48]
               y - translate              change 32->25 and 63->48

Answer 4

Python 2, 62 bytes

def f(c):M=max(c);u=M<5;print[48,25-u*7,3*M+~u-u,M,1][-min(c)]

Try it online!

---

Python 2, 63 bytes

def f(c):M=max(c);print[48,M%2*7+18,3*~-M+2*(M>4),M,1][-min(c)]

Try it online!

This is ridiculous, I will soon regret having posted this... But eh, ¯\_(ツ)_/¯. Shaved off 1 byte thanks to our kind Jonathan Allan :). Will probably be outgolfed by about 20 bytes shortly though...

Answer 5

Julia 0.6, 71 61 59 57 bytes

A->((r,s)=sort(A);r<3?s^~-r:3r+(s^2-4s+3)*((r==s)+r-2)-3)

Try it online!

Ungolfed (well, a bit more readable):

function f_(A)
  (r, s) = sort(A)

  if r < 3
    result = s^(r-1)
  else
    result = 3*r + 
               (s^2 - 4*s + 3) * ((r == s) + r - 2) -
               3
  end

  return result
end

What does it do?

Takes input as array A containing r and s. Unpacks the array into r and s with the smaller number as r, using (r,s)=sort(A).

If r is 1, output should be 1. If r is 2, output should be whatever s is.
\$ s^{r - 1} \$ will be \$ s^0 = 1 \$ for r=1, and \$ s^1 = s \$ for r = 2.
So, r<3?s^(r-1) or shorter, r<3?s^~-r

For the others, I started with noticing that the output is:

• for r = 3, \$ 2\times3 + [0, 3, 8] \$ (for s = 3, 4, 5 respectively).
• for r = 4, \$ 2\times4 + \ \ [10, 17] \$ (for s = 4, 5 respectively)
• for r = 5, \$ 2\times5 + \ \ \ \ \ [35] \$ (for s = 5)

(I initially worked with f(5,5)=45 for convenience.)

This looked like a potentially usable pattern - they all have 2r in common, 17 is 8*2+1, 35 is 17*2+1, 10 is 3*3+1. I started with extracting the base value from [0, 3, 8], as [0 3 8][s-2] (this later became the shorter (s^2-4s+3)).

Attempting to get correct values for r = 3, 4, and 5 with this went through many stages, including

2r+[0 3 8][s-2]*(r>3?3-s+r:1)+(r-3)^3+(r>4?1:0)

and

2r+(v=[0 3 8][s-2])+(r-3)*(v+1)+(r==s)v

Expanding the latter and simplifying it led to the posted code.

Answer 6

x86, 49 37 bytes

Not very optimized, just exploiting the properties of the first three rows of the table. While I was writing this I realized the code is basically a jump table so a jump table could save many bytes. Input in eax and ebx, output in eax.

-12 by combining cases of r >= 3 into a lookup table (originally just r >= 4) and using Peter Cordes's suggestion of cmp/jae/jne with the flags still set so that r1,r2,r3 are distinguished by only one cmp! Also indexing into the table smartly using a constant offset.

start:
        cmp     %ebx, %eax
        jbe     r1
        xchg    %eax, %ebx              # ensure r <= s

r1:
        cmp     $2, %al             
        jae     r2                      # if r == 1: ret r
        ret

r2:     
        jne     r3                      # if r == 2: ret s 
        mov     %ebx, %eax
        ret

r3:
        mov     table-6(%ebx,%eax),%al  # use r+s-6 as index
        sub     %al, %bl                # temp = s - table_val
        cmp     $-10, %bl               # equal if s == 4, table_val == 14
        jne     exit
        add     $4, %al                 # ret 18 instead of 14 

exit:
        ret                        

table:
        .byte   6, 9, 14, 25, 43

Hexdump

00000507  39 d8 76 01 93 3c 02 73  01 c3 75 03 89 d8 c3 8a  |9.v..<.s..u.....|
00000517  84 03 21 05 00 00 28 c3  80 fb f6 75 02 04 04 c3  |..!...(....u....|
00000527  06 09 0e 19 2b                                    |....+|

Answer 7

Python 2, 70 bytes

f=lambda R,S:R<=S and[1,S,[6,9,14][S-3],[18,25][S&1],45][R-1]or f(S,R)

Try it online!

Answer 8

MATL, 25 21 bytes

+2-lGqXnt8/k-t20/k6*-

Try it on MATL Online

Attempt to port Jonathan Allan's Jelly answer to MATL.

+2-lGqXn - same as that answer: compute \$ \binom{r+s-2}{r-1} \$

t8/k - duplicate that, divide by 8 and floor

- - subtract that from previous result (We subtract how many times 8 goes in the number, instead of 9 in the Jelly answer. The result is the same for all but the 35 and 70, which here give 31 and 62.)

t20/k - duplicate that result too, divide that by 20 and floor (gives 0 for already correct results, 1 for 31, 3 for 62)

6* - multiply that by 6

- - subtract that from the result (31 - 6 = 25, 62 - 18 = 44)

---

Older:

+t2-lGqXntb9<Q3w^/k-t20>+

Try it on MATL Online

Answer 9

Python 3, 74 bytes

lambda *a:[[1]*5,[2,3,4,5],[6,9,14],[18,25],[43]][min(a)-1][max(a)-min(a)]

Try it online!

Answer 10

Proton, 52 bytes

Near-port of my Python answer.

c=>[48,(M=max(c))%2*7+18,3*M-(M>4?1:3),M,1][-min(c)]

Try it online!

Answer 11

Java 8, 62 bytes

(r,s)->--r*--s+new int[]{9,1,0,13,2,0,3,27,6}[r<2|s<2?1:r*s%9]

Lambda function, port of Arnauld's JavaScript answer. Try it online here.

Java, 83 bytes

int f(int x,int y){return x<2|y<2?1:f(x,y-1)+f(x-1,y)-(x*y==12?1:0)-7*(x+y>8?1:0);}

Recursive function, port of Neil's JavaScript answer. Try it online here.

Answer 12

C (gcc), 57 bytes

f(x,y){x=x<2|y<2?:f(x,y-1)+f(x-1,y)-(x*y==12)-7*(x+y>8);}

Recursive function, port of Neil's JavaScript answer. Try it online here.

C (gcc), 63 bytes

f(r,s){r=--r*--s+(int[]){9,1,0,13,2,0,3,27,6}[r<2|s<2?:r*s%9];}

Port of Arnauld's JavaScript answer. Try it online here.