\documentclass[12pt]{article} \usepackage{e-jc} \specs{P29}{20(4)}{2013} \usepackage{amsmath} \usepackage{amssymb} \usepackage{longtable} \usepackage{amsthm} \usepackage{hyperref} %\usepackage{algorithm} %\usepackage{algpseudocode} \theoremstyle{definition} \newtheorem{defn}{Definition} \newtheorem{conj}{Conjecture} \newtheorem{coro}{Corollary} \newtheorem{lemma}{Lemma} \newtheorem{theorem}{Theorem} \newtheorem{exmp}{Example} \newtheorem{ques}{Question} \newtheorem{obs}{Observation} \renewcommand{\geq}{\geqslant} \newcommand{\set}[1]{\left\{#1\right\}} \newcommand{\parens}[1]{\left(#1\right)} \newcommand{\arr}[1]{\left[#1\right]} \renewcommand{\leq}{\leqslant} \newcommand{\ang}[1]{\big\langle#1\big\rangle} \newcommand{\smallfloor}[1]{\lfloor#1\rfloor} \newcommand{\floor}[1]{\Big\lfloor#1\Big\rfloor} \newcommand{\ceil}[1]{\Big\lceil#1\Big\rceil} \newcommand{\ignore}[1]{\relax\ignorespaces} \title{\bf Unique Sequences Containing No $\boldsymbol{k}$-Term Arithmetic Progressions} \author{Tanbir Ahmed\\ \small Department of Computer Science and Software Engineering\\[-0.8ex] \small Concordia University, Montr\'eal, Canada\\ \small \texttt{ta\_ahmed@cs.concordia.ca}\\ \and Janusz Dybizba\'nski\\ \small Institute of Informatics\\[-0.8ex] \small University of Gda\'nsk, Poland\\ \small \texttt{jdybiz@inf.ug.edu.pl}\\ \and Hunter Snevily\footnote{Hunter Snevily has passed away on November 11, 2013 after his long struggle with Parkinson's disease. We have lost a good friend and colleague. He will be greatly missed and remembered. }\\ \small Department of Mathematics\\[-0.8ex] \small University of Idaho - Moscow, Idaho, USA\\ \small \texttt{snevily@uidaho.edu}\\ } \date{\dateline{Dec 22, 2012}{Dec 5, 2013}{Dec 17, 2013}\\ \small Mathematics Subject Classifications: 11B25} \begin{document} \maketitle \raggedbottom \begin{abstract} In this paper, we are concerned with calculating $r(k,n)$, the length of the longest $k$-Ap free subsequences in $1,2,\ldots,n$. We prove the basic inequality $r(k,n) \leq n- \smallfloor{m/2}$, where $n=m(k-1) + r$ and $rn^{1-c/\log\log{n}},$$ which was further improved by Behrend \cite{behrend} to $$r(3,n)>n^{1-c/\sqrt{\log{n}}}.$$ Recently, Elkin \cite{elkin} has further improved this lower bound by a factor of $\Theta(\sqrt{\log{n}})$. The first non-trivial upper bound was due to Roth \cite{roth} who proved $$r(3,n) \smallfloor{(x-1)/(j-1)}$, then (similar as $(i)$) $$c_j(k,n;x) = c_{k-j+1}(k,n;n-x+1).$$ \end{itemize} \end{itemize} %From Observation \ref{obs-1}, $c_1(n,k;x) = c_k(n,k;n-x+1)$. \ignore{ For other values of $j$, if $\smallfloor{(n-x)/(k-j)}\leq \smallfloor{(x-1)/(j-1)}$, then taking $x'=n-x+1$ and $j'=k-j+1$, $$c_j(k,n;x) = \floor{{(n-x)\over(k-j)}} = \floor{{(n-x+1)-1\over (k-j+1)-1}}= \floor{{(x'-1) \over (j'-1)}} = c_{j'}(k,n;x').$$ The last equality follows from the fact that $$\floor{{(x'-1) \over (j'-1)}} \leq \floor{{(x-1)\over(j-1)}}=\floor{{(n-x')\over(k-j')}}.$$ Similarly, if $\smallfloor{(n-x)/(k-j)} > \smallfloor{(x-1)/(j-1)}$, then $$c_j(k,n;x) = c_{k-j+1}(k,n;n-x+1).$$ } Therefore, $c(k,n;x)$ with $x=1,2,\ldots,n$ is symmetric. \end{proof} \end{obs} \begin{lemma}\label{lemma-1} Given positive integers $k$ and $n$, let $2\leq j\leq k-1$, $n=m(k-1)+r$ with $0\leq r\leq k-2$. Then $c_j(k,n;x)$ equals \begin{itemize} \item [$(a)$] $\smallfloor{(x-1)/(j-1)}$ if $x=1,2,\ldots,m(j-1)$, \item [$(b)$] $\smallfloor{(n-x)/(k-j)}$ if $x=n-m(k-j)+1,n-m(k-j)+2,\ldots,n$, \item [$(c)$] $m$ otherwise, that is, for $x=m(j-1)+1,\ldots,n-m(k-j)$. \end{itemize} \begin{proof} \begin{itemize} \item [$(a)$] Take $y\leq m(j-1)$ and assume $$c_j(k,n;y)=\smallfloor{(n-y)/(k-j)},$$ that is, $\smallfloor{(n-y)/(k-j)}<\smallfloor{(y-1)/(j-1)}$. Since $y\leq m(j-1)$, we have $(y-1)\leq m(j-1)-1$, and hence $$\floor{{y-1\over j-1}} \leq m-1.$$ %Now we have, $\smallfloor{(y-1)/(j-1)} \leq m-1$, and Again, since $y\leq m(j-1)$, we have %\begin{eqnarray*} %y \leq m(j-1) % & & $$n-y \geq n-m(j-1) = m(k-j)+r,$$ % &\Rightarrow & \floor{{n-y\over k-j}} \geq m. %\end{eqnarray*} which implies $$\floor{{n-y\over k-j}} \geq m.$$ Now, we have the following contradiction $$m \leq \floor{{n-y\over k-j}} < \floor{{y-1\over j-1}} \leq m-1.$$ \item [$(b)$] Take $y\geq n-m(k-j)+1$ and assume $$c_j(k,n;y)=\smallfloor{(y-1)/(j-1)},$$ that is, $\smallfloor{(n-y)/(k-j)}>\smallfloor{(y-1)/(j-1)}$. Similar reasoning as (a) leads to a contradiction. \item [$(c)$] Here, $n-m(k-j)$ can be written as $m(j-1)+r$ and $m(j-1)+1$ can be written as $n-m(k-j)-(r-1)$. There are exactly $r$ elements in $m(j-1)+1,\ldots,n-m(k-j)$, and for any $x$ in this range, $$c_j(k,n;x) = \smallfloor{(x-1)/(j-1)} = \smallfloor{(n-x)/(k-j)} = m.$$ \end{itemize} \end{proof} \end{lemma} \begin{lemma}\label{lemma-2} Given positive integers $k$ and $n$, let $n=m(k-1)+r$ with $0\leq r\leq k-2$. Denote a sequence $a,a,\ldots,a$ with $a$ repeated $b$ times as $a^b$, and consider $a^0$ to be an empty sequence. Then for $1\leq j\leq k$, the sequence $c_j(k,n;x)$ with $1\leq x\leq n$ has the form $$0^{j-1}1^{j-1}\cdots(m-1)^{j-1}m^r(m-1)^{k-j}(m-2)^{k-j}\cdots 0^{k-j}.$$ \begin{proof} Using Observation \ref{obs-1}, we have for $j=1$: $$c_1(k,n;x) = \floor{{n-x \over k-1}} = \floor{m+{r-x\over k-1}} = m+\floor{{r-x\over k-1}},$$ and more specifically, \begin{eqnarray*} c_1(k,n;x) &=& \left\{ \begin{array}{ll} m, & \text{for $x=1,2,\ldots,r$};\\ (m-1), & \text{for $x=r+1,r+2,\ldots,r+(k-1)$};\\ (m-2), & \text{for $x=r+(k-1)+1,r+(k-1)+2,\ldots,r+2(k-1)$};\\ & \vdots, \\ 1, & \text{for $x=r+(m-2)(k-1)+1,\ldots,n-(k-1)$};\\ 0, & \text{for $x=r+(m-1)(k-1)+1,\ldots,n$}. \end{array} \right. \end{eqnarray*} Hence, the sequence $c_1(k,n;x)$ with $x=1,2,\ldots,n$ is $$m^r(m-1)^{k-1}(m-2)^{k-1}\cdots{1}^{k-1}{0}^{k-1}.$$ Similarly, for $j=k$, we have $$c_k(k,n;x) = \floor{{x-1\over k-1}},$$ and more specifically, \begin{eqnarray*} c_k(k,n;x) &=& \left\{ \begin{array}{ll} 0, & \text{for $x=1,2,\ldots,k-1$};\\ 1, & \text{for $x=(k-1)+1,(k-1)+2,\ldots,2(k-1)$};\\ 2, & \text{for $x=2(k-1)+1,2(k-1)+2,\ldots,3(k-1)$};\\ & \vdots, \\ (m-2), & \text{for $x=(m-2)(k-1)+1,\ldots,(m-1)(k-1)$};\\ (m-1), & \text{for $x=(m-1)(k-1)+1,\ldots,m(k-1)$};\\ m, & \text{for $x=m(k-1)+1,\ldots,n$}. \end{array} \right. \end{eqnarray*} and hence the sequence $c_k(k,n;x)$ with $x=1,2,\ldots,n$ is $$0^{k-1}1^{k-1}\cdots(m-2)^{k-1}(m-1)^{k-1}m^r.$$ For $2\leq j\leq k-1$, by Lemma \ref{lemma-1}, we have \footnotesize \begin{longtable}{c|c}%\caption{Row-structure for $c(k,n)$}\\ \hline $x$ & $c_j(k,n;x)$\\ \hline $1,2,\ldots,j-1$ & $\smallfloor{(x-1)/(j-1)}=0$\\ $(j-1)+1,(j-1)+2,\ldots,2(j-1)$ & $\smallfloor{(x-1)/(j-1)}=1$\\ %$2(j-1)+1,2(j-1)+2,\ldots,3(j-1)$ & $\smallfloor{(x-1)/(j-1)}=2$\\ $\vdots$ & $\vdots$ \\ $(m-2)(j-1)+1,(m-2)(j-1)+2,\ldots,(m-1)(j-1)$ & $\smallfloor{(x-1)/(j-1)}=m-2$\\ $(m-1)(j-1)+1,(m-1)(j-1)+2,\ldots,m(j-1)$ & $\smallfloor{(x-1)/(j-1)}=m-1$\\ \hline $m(j-1)+1,m(j-1)+2,\ldots,n-m(k-j)$ & $m$\\ \hline $n-m(k-j)+1,\ldots,n-(m-1)(k-j)$ & $\smallfloor{(n-x)/(k-j)}=m-1$\\ $n-(m-1)(k-j)+1,\ldots,n-(m-2)(k-j)$ & $\smallfloor{(n-x)/(k-j)}=m-2$\\ $\vdots$ & $\vdots$ \\ $n-2(k-j)+1,n-2(k-j)+2,\ldots,n-(k-j)$ & $\smallfloor{(n-x)/(k-j)}=1$\\ $n-(k-j)+1,n-(k-j)+2,\ldots,n$ & $\smallfloor{(n-x)/(k-j)}=0$\\ \hline \end{longtable} \normalsize Hence, we get the sequence $c_j(k,n;x)$ for $x=1,2,\ldots,n$ as $$0^{j-1}1^{j-1}\cdots(m-1)^{j-1}m^r(m-1)^{k-j}(m-2)^{k-j}\cdots 0^{k-j}.$$ \end{proof} \end{lemma} \begin{coro}\label{coro-1a} Given positive integers $k$ and $n$, let $m=\smallfloor{n/(k-1)}$ and $n=m(k-1)+r$. Then $$c(k,n) = {m\choose 2}(k-1)+mr.$$ \begin{proof} From the definition of $c_1(k,n;x)$ in Lemma \ref{lemma-2}, for $1\leq x\leq n$, we have, \begin{eqnarray*} c(k,n) & = & \sum_{x=1}^{n-k+1}c_1(k,n;x)\\ &=& \sum_{x=1}^rc_1(k,n;x)+ \left[\sum_{x=r+1}^{r+(k-1)}c_1(k,n;x)+\right. \\ && \left.\sum_{x=r+(k-1)+1}^{r+2(k-1)}c_1(k,n;x)+\cdots+ \sum_{x=r+(m-2)(k-1)+1}^{n-k+1=n-(k-1)=r+(m-1)(k-1)}c_1(k,n;x)\right]\\ & = & mr + [(m-1)+(m-2)+\cdots+2+1](k-1)\\ & = & {m\choose 2}(k-1)+mr. \end{eqnarray*} \end{proof} \end{coro} \begin{coro}\label{coro-2a} Given positive integers $k$ and $n$, let $n=m(k-1)+r$ with $r k-1$}. \end{array} \right. \end{eqnarray*} Hence, $$r(k,n) \leq n - \smallfloor{m/2}.$$ \end{proof} \end{theorem} \begin{conj}\label{conj-periodic} For every positive integer $k\geq 3$ and positive integer $n$, %the maximum value of $c(k,n;x)$ over $x=1,2,\ldots,n$ $c_{max}(k,n)$ is eventually periodic. \end{conj} For example, for $k=5$, the length of the period is $24$ and the periodic increase in the value of $c_{max}(k,n)$ is $20$, as indicated in the following table: %\newpage \footnotesize \begin{longtable}{c|c||c|c||c|c||c|c||c|c||c} \hline $n$ & $c_{max}(5,n)$ & $n$ & $c_{max}(5,n)$ & $n$ & $c_{max}(5,n)$ & $n$ & $c_{max}(5,n)$ & $n$ & $c_{max}(5,n)$ \\ \hline 25 & 20 & 49 & 40 & 73 & 60 & 97 & 80 & 121 & 100 & $\cdots$ \\ 26 & 20 & 50 & 40 & 74 & 60 & 98 & 80 & 122 & 100 & $\cdots$ \\ 27 & 20 & 51 & 40 & 75 & 60 & 99 & 80 & 123 & 100 & $\cdots$ \\ 28 & 21 & 52 & 41 & 76 & 61 & 100 & 81 & 124 & 101 & $\cdots$ \\ 29 & 22 & 53 & 42 & 77 & 62 & 101 & 82 & 125 & 102 & $\cdots$ \\ 30 & 22 & 54 & 42 & 78 & 62 & 102 & 82 & 126 & 102 & $\cdots$ \\ $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ &$\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ \\ 47 & 37 & 71 & 57 & 95 & 77 & 119 & 97 & 143 & 117 & $\cdots$ \\ 48 & 37 & 72 & 57 & 96 & 77 & 120 & 97 & 144 & 117 & $\cdots$ \\ \hline \end{longtable} \normalsize %\begin{lemma} %For $i\geq 2$ and $1\leq j\leq 24$, $$c_{max}(5,24i+j) = c_{max}(5, (i-1)24+j)+20.$$ %\end{lemma} \begin{conj}\label{conj-column-sum} Given an odd positive integer $k$, the size of the largest subset $U$ of $\set{1,2,\ldots,n}$ for any positive integer $n$, with each $x\in U$ having the same $c(k,n;x)$, is bounded from above by a constant $f(k)\leq k^2$. \end{conj} The implications of Conjecture \ref{conj-column-sum} being true is as follows: Let $w = c_{max}(k,n)$ and consider the largest $\ell$ such that $$g(k,\ell,w)=f(k)\parens{w+(w-1)+\cdots+\parens{w-(\ell-1)}}$$ has the property $c(k,n)-g(k,\ell,w)\geq f(k)\ell(\ell-1)/2$. Then \begin{eqnarray*} r(k,n) &\leq & n - \ceil{{c(k,n)\over w}} \leq n - \ceil{{g(k,\ell,w)+f(k)\ell(\ell-1)/2\over w}} \\ &=& n - f(k)\ell. \end{eqnarray*} See Appendix \ref{app-1} for data supporting Conjectures \ref{conj-periodic} and \ref{conj-column-sum}. \section{Unimodality lemmas} A sequence is called \emph{unimodal} if it is first increasing and then decreasing. In this section, we prove some lemmas on sequences regarding $c(k,n;x)$ for $k\geq 3$. \begin{lemma} Given positive integers $k$ and $n$, for any $j\in\set{2,3,\ldots,k-1}$, the sequence $c_j(k,n;x)$ with $x=1,2,\ldots,n$ is unimodal. \begin{proof} Follows directly from Lemma \ref{lemma-2}. \end{proof} \end{lemma} \begin{lemma} The sequence $c(3,n;i)$ with $i=1,2,\ldots,n$ is unimodal. \begin{proof} From Observation \ref{obs-1}, $$ c_j(3,n; x) = \left\{ \begin{array}{ll} \smallfloor{(n-x)/2}, & \text{if $j=1$};\\ x-1, & \text{if $j=2$ and $x\leq\smallfloor{n/2}$};\\ n-x, & \text{if $j=2$ and $x>\smallfloor{n/2}$};\\ \smallfloor{(x-1)/2}, & \text{if $j=3$}.\\ \end{array} \right. $$ By Observation \ref{obs-2}, $c(3,n;i)$ equals $c(3,n;n-i+1)$ for $i=1,2,\ldots,\smallfloor{n/2}$. Now, we consider the following two cases: \begin{enumerate} \item ($n=2m$). For $i=1,2,\ldots,m-1$, we have $$c_2(3,n; i+1) = c_2(3,n;i)+1,$$ and also for $i=1,2,\ldots,m$, \begin{eqnarray*} c_1(3,n;i) + c_3(3,n;i) & = & \floor{{2m-i \over 2}} +\floor{{i-1\over 2}} = \floor{m-{i\over 2}}+\floor{{i\over 2}-{1\over 2}}. \end{eqnarray*} If $i=2j$ ($j\geq 1$), then \begin{eqnarray*} c_1(3,n;i) + c_3(3,n;i) & = & (m-j)+\floor{j-{1\over 2}} = (m-j) + (j-1) = m-1. \end{eqnarray*} If $i=2j+1$ ($j\geq 0$), then \begin{eqnarray*} c_1(3,n;i) + c_3(3,n;i) & = & \floor{m-j-{1\over 2}}+\floor{{(2j+1)-1\over 2}} \\ & = & (m-j-1) + j = m-1. \end{eqnarray*} Therefore, for $i=1,2,\ldots,m-1$, $$c(3,n;i+1)= (m-1)+c_2(3,n;i)+1 = c(3,n;i)+1.$$ \item ($n=2m+1$). For $i=1,2,\ldots,m$, we have $$c_2(3,n; i+1) = c_2(3,n;i)+1,$$ and also \begin{eqnarray*} c_1(3,n;i) + c_3(3,n;i) & = & \floor{{2m+1-i \over 2}} +\floor{{i-1\over 2}} = \floor{m+{1\over 2}-{i\over 2}}+\floor{{i\over 2}-{1\over 2}}. \end{eqnarray*} If $i=2j$ ($j\geq 1$), then \begin{eqnarray*} c_1(3,n;i) + c_3(3,n;i) & = & \floor{m+{1\over 2}-j}+\floor{j-{1\over 2}} = (m-j) + (j-1) = m-1. \end{eqnarray*} If $i=2j+1$ ($j\geq 0$), then \begin{eqnarray*} c_1(3,n;i) + c_3(3,n;i) & = & \floor{m+{1\over 2}-j-{1\over 2}}+\floor{{(2j+1)-1\over 2}} \\ & = & (m-j) + j = m. \end{eqnarray*} Therefore, for $i=1,2,\ldots,m$, \begin{itemize} \item If $i$ is odd, then \begin{eqnarray*} c(3,n;i+1) & = & c_1(3,n;i+1)+c_2(3,n;i+1)+c_3(3,n;i+1) \\ & = & c_2(3,n;i)+1 +(m-1) = c_2(3,n;i)+m \\ & = & c_2(3,n;i)+c_1(3,n;i)+c_3(3,n;i) = c(3,n;i). \end{eqnarray*} \item If $i$ is even, then \begin{eqnarray*} c(3,n;i+1) & = & c_1(3,n;i+1)+c_2(3,n;i+1)+c_3(3,n;i+1)\\ & = & c_2(3,n;i)+1 +m = c_2(3,n;i)+(m-1)+2 \\ & = & c_2(3,n;i)+c_1(3,n;i)+c_3(3,n;i)+2 = c(3,n;i)+2. \end{eqnarray*} \end{itemize} \end{enumerate} Hence, $c(3,n;i)$ with $i=1,2,\ldots,n$ is unimodal. \end{proof} \end{lemma} \begin{lemma} For $k\geq 4$, there are infinitely many $n$ such that the sequence $c(k,n;i)$ with $i=1,2,\ldots,n$ is unimodal. \begin{proof} We show that $c(k, n; i)$ for $1\leq i\leq n$ with $n=lcm\set{1,2,\ldots,k-1}\cdot{m}$ (where $m\geq 1$) is unimodal. Since $n$ is even, $n/2$ is an integer. By Observation \ref{obs-2}, the sequence $c(k, n; i)$ with $1\leq i\leq n$ is symmetric. So assume $i\leq n/2$. Let $lcm\set{1,2,\ldots,k-1}$ be equal to $h_r\cdot r$ with $2\leq r\leq k-1$, and $i\equiv s\pmod{k-1}$ with $t=\smallfloor{i/(k-1)}$. Now, \begin{eqnarray*} c_1(k,n;i) & = & \floor{{(n-i)\over(k-1)}} = \floor{mh_{k-1}-{i \over (k-1)}} = \floor{mh_{k-1}-t-{s\over k-1}}\\ c_1(k,n;i+1) & = & \floor{{(n-i-1)\over(k-1)}} = \floor{mh_{k-1}-{i+1 \over (k-1)}} = \floor{mh_{k-1}-t-{s+1\over k-1}} \end{eqnarray*} Therefore, $$ c_1(k,n;i+1) = \left\{ \begin{array}{ll} c_1(k,n;i)-1, & \text{if $s=0$;}\\ c_1(k,n;i), & \text{otherwise}. \end{array} \right. $$ Similarly, $$ c_k(k,n;i+1) = \left\{ \begin{array}{ll} c_k(k,n;i)+1, & \text{if $s=0$;}\\ c_k(k,n;i), & \text{otherwise}. \end{array} \right. $$ Hence, $c_1(k,n;i)+c_k(k,n;i)$ remains constant for $1\leq i\leq n$. Again, for $1\leq i \leq n/2$, we have $$i-1 \leq n-i.$$ For $2\leq j\leq k-1$, we want to show $$c_j(k,n;i+1)+c_{k-j+1}(k,n;i+1)\geq c_j(k,n;i)+c_{k-j+1}(k,n;i).$$ Assume $j>\smallfloor{k/2}$. This implies $k-j\leq j-1$. Since $i-1 \leq n-i$, we have $$\floor{{(i-1)\over(j-1)}}\leq \floor{{(n-i)\over (k-j)}}.$$ So for $1\leq i\leq n/2-1$, and considering $i\equiv s \pmod{j-1}$ and $t=\smallfloor{i/(j-1)}$, we have, \begin{eqnarray*} c_j(k,n;i+1) & = & \floor{{i\over j-1}} = t\\ c_j(k,n;i) & = & \floor{{i-1\over j-1}} = \floor{t+{s-1\over j-1}} = \left\{ \begin{array}{ll} t-1, & \text{if $s=0$};\\ t, & \text{if $s\geq 1$}. \end{array} \right. \end{eqnarray*} Take $j'=k-j+1$, and then $j'-1\leq k-j'$. If $\smallfloor{(i-1)/(j'-1)}\leq \smallfloor{(n-i)/(k-j')}$, then $$0\leq c_{j'}(k,n;i+1)-c_{j'}(k,n;i)\leq 1,$$ else \begin{eqnarray*} c_{j'}(k,n;i) &=& \floor{{n-i\over k-j'}} = \floor{{n-i\over j-1}} = \floor{mh_{j-1}-t-{s\over j-1}}\\ &=& \left\{ \begin{array}{ll} (mh_{j-1}-t), & \text{if $s=0$};\\ (mh_{j-1}-t-1), & \text{otherwise}.\\ \end{array} \right.\\ c_{j'}(k,n;i+1) & = & \floor{{n-i-1\over k-j'}} = \floor{mh_{j-1}-t-{s+1\over j-1}}=(mh_{j-1}-t-1) \end{eqnarray*} Therefore, $$c_j(k,n;i+1)+c_{j'}(k,n;i+1)\geq c_j(k,n;i)+c_{j'}(k,n;i).$$ So the sequence $c(k,n;x)$ with $1\leq x\leq n/2$ is non-decreasing and hence the sequence $c(k,n;x)$ with $1\leq x\leq n$ is unimodal for infinitely many $n$. \end{proof} \end{lemma} \section{Uniqueness conjectures}\label{sec-uniqueness} In this section, we generalize Szekeres' conjecture and provide a construction for the lower bound. We also provide a construction algorithm for $r(k,n)$. Define $$J(k,L) = \set{(n,m): n\leq L, r(k,n)=m \text{ and } b(k,n)=1}.$$ We have the following experimental data, based on which we formulate Conjectures \ref{conj-1} and \ref{conj-2}: \begin{eqnarray*} J(3,123) & = & \parbox[t]{4in}{\{$(2,2), (5,4), (14,8), (30,12), (41,16), (74,22), (84,24), (104,28)$, $(114,30), (122,32)$\},}\\ J(5,105) & = & \set{(2,2),(3,3),(4,4),(9,8),(14,12),(19,16),(44,32),(69,48),(94,64)},\\ J(7,139) & = & \parbox[t]{4in}{\{$(2,2), (3,3), (4,4), (5,5), (6,6), (13,12), (20,18), (27,24), (34,30)$, $(41,36), (90,72), (139,108)$\},}\\ J(11,117) & = & \parbox[t]{4in}{\{$(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),(8,8),(9,9),(10,10),(21,20)$, $(32,30),(43,40),(54,50),(65,60),(76,70),(87,80),(98,90),(109,100)$\},}\\ J(13,161) & = & \parbox[t]{4in}{\{$(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),(8,8),(9,9),(10,10),(11,11)$, $(12,12),(25,24),(38,36),(51,48),(64,60),(77,72),(90,84),(103,96)$, $(116,108),(129,120),(142,132),(155,144)$\}.} \end{eqnarray*} %$$J(3,67) = \set{(2,2), (5,4),(14,8), (30,12),(41,16)},$$ %$$J(5,105)=\set{(2,2),(3,3),(4,4),(9,8),(14,12),(19,16),(44,32),(69,48),(94,64)},$$ %$$J(7,139)=\parbox[t]{4in}{\{(2,2), (3,3), (4,4), (5,5), (6,6), (13,12), (20,18), (27,24), (34,30), (41,36), (90,72), (139,108)\}}$$ %Based on experimental data, we generalize the Szekeres' conjecture as follows: \begin{conj}[The Uniqueness Conjecture]\label{conj-1} Consider a prime $p\geq 3$ and an integer $t\geq 1$. % $1\leq i\leq p-1$, and $t\geq 1$. %$x = [(p-2)p^t+1]/(p-1)$. Then for $1\leq i\leq p-1$, $$r\left(p, {(ip-i-1)p^t+1 \over (p-1)}\right)= i\cdot(p-1)^t,$$ and $b\left(p, x\right)=1$ where $1\leq x\leq p-2$ or else $$x={(ip-i-1)p^t+1 \over (p-1)}.$$ \end{conj} It can be observed that Szekeres' conjecture is a special case of Conjecture \ref{conj-1} with $i=1$. \begin{conj}[Strong Uniqueness Conjecture]\label{conj-2} Consider a prime $p>3$ and an integer $t\geq 1$. Then $b(p, x)=1$ if and only if $1\leq x\leq p-2$ or else $$x = {(ip-i-1)p^t+1 \over (p-1)}$$ with $1\leq i\leq p-1$. \end{conj} See Appendix \ref{app-3} for data supporting Conjectures \ref{conj-1} and \ref{conj-2}. \subsection{Construction for the lower-bound of Conjecture \ref{conj-1}} For a prime $p>3$ and $1\leq i\leq p-1$, take $$n={(ip-i-1)p^t+1 \over p-1} = ip^t-p^{t-1}-p^{t-2}-\cdots-p-1.$$ We can construct a $p$-AP free subset of $\set{1,2,\ldots,n}$ of size $i\cdot(p-1)^t$ as follows: \begin{eqnarray*} T_0 &=& \set{1,2,\ldots,n},\\ T_1 &=& T_0 - \set{j : j\equiv{0}\pmod{p}} = T_0 - S_0,\\ T_2 &=& T_1 - \set{j_1p^2-p+j_2 : 1\leq j_1\leq \smallfloor{n/p^2}, 1\leq j_2\leq p-1} = T_1 - S_1, \\ T_3 &=& T_2 - \set{j_1p^3-p^2+j_2p-j_3 : 1\leq j_1\leq \smallfloor{n/p^3}, 1\leq j_2,j_3\leq p-1} = T_2 - S_2,\\ T_4 &=& T_3 - \set{j_1p^4-p^3+j_2p^2-j_3p+j_4 : 1\leq j_1\leq \smallfloor{n/p^4}, 1\leq j_2,j_3,j_4\leq p-1}\\ &=& T_3 - S_3,\\ &\vdots,&\\ T_t %&=& T_{t-1} - \set{j_1p^t-p^{t-1}+\cdots+(-1)^{t-1}j_{t-1}p+(-1)^tj_t: 1\leq j_1\leq \smallfloor{n/p^t}, 1\leq j_2,j_3,\ldots,j_t\leq p-1}\\ &=& T_{t-1} - \set{j_1p^t-p^{t-1}+\sum_{\ell=2}^tp^{t-\ell}j_\ell(-1)^\ell: 1\leq j_1\leq \smallfloor{n/p^t}, 1\leq j_2,j_3,\ldots,j_t\leq p-1}\\ %\cdots+(-1)^{t-1}j_{t-1}p+(-1)^tj_t: 1\leq j_1\leq \smallfloor{n/p^t}, 1\leq j_2,j_3,\ldots,j_t\leq p-1}\\ &=& T_{t-1}-S_{t-1}. \end{eqnarray*} It can be observed that \begin{eqnarray*} |S_0| &=& \smallfloor{n/p} = ip^{t-1}-p^{t-2}-\cdots-p-2,\\ |S_1| &=& (p-1)\smallfloor{n/p^2} = (p-1)\parens{ip^{t-2}-p^{t-3}-\cdots-p-2},\\ |S_2| &=& (p-1)^2\smallfloor{n/p^3} = (p-1)^2\parens{ip^{t-3}-p^{t-4}-\cdots-p-2},\\ &\vdots,&\\ |S_{t-1}| &=& (p-1)^{t-1}\smallfloor{n/p^t} = (p-1)^{t-1}(i-1). \end{eqnarray*} \begin{lemma} The $S_\ell$'s for $0\leq \ell\leq t-1$ are disjoint. \begin{proof} Each element in $S_0$ is divisible by $p$, and no element in any other $S_\ell$ is divisible by $p$. So $S_0$ is disjoint from every other $S_\ell$. For $2\leq \ell\leq t-1$, $$S_\ell = \set{(xp+(-1)^{\ell-1}j_{\ell+1}) \in T_0 : x\in S_{\ell-1}, 1\leq j_{\ell+1}\leq p-1},$$ and hence $S_\ell\cap S_u=\emptyset$ for $1\leq u\leq \ell-1$. \end{proof} \end{lemma} \begin{lemma} For a prime $p>3$ and $1\leq i\leq p-1$, $$|T_t| = i\cdot(p-1)^t.$$ \begin{proof} We can write the summation $\sum_{j=0}^{t-1}|S_j|$ as follows: \begin{eqnarray*} \sum_{j=0}^{t-1}|S_j| &=& ip^{t-1}\parens{\sum_{a=0}^{t-1}{a\choose 0}} + \cdots + (-1)^{\ell-1}ip^{t-\ell}\parens{\sum_{a=\ell-1}^{t-1}{a\choose \ell-1}} + \cdots -i - \sum_{\ell=0}^{t-1}p^\ell,\\ &=& ip^{t-1}{t\choose 1} + \cdots + (-1)^{\ell-1}ip^{t-\ell}{t\choose \ell} + \cdots -i - \sum_{\ell=0}^{t-1}p^\ell,\\ &=& i\sum_{\ell=1}^t{t\choose \ell}p^{t-\ell}(-1)^{\ell-1}-\sum_{\ell=0}^{t-1}p^\ell. \end{eqnarray*} The fact $$\sum_{a=\ell-1}^{t-1}{a\choose \ell-1}={t \choose \ell}$$ can be easily proven using induction on $t$ and using the fact that $${t\choose\ell}+{t\choose\ell-1}={t+1\choose \ell}.$$ Now, we have \begin{eqnarray*} |T_t| &=& n-\sum_{j=0}^{t-1}|S_j|,\\ &=& ip^t-\sum_{\ell=0}^{t-1}p^\ell -\parens{i\sum_{\ell=1}^t{t\choose \ell}p^{t-\ell}(-1)^{\ell-1}-\sum_{\ell=0}^{t-1}p^\ell},\\ &=& ip^t+i\sum_{\ell=1}^t{t\choose \ell}p^{t-\ell}(-1)^{\ell} = i\cdot(p-1)^t. \end{eqnarray*} \end{proof} \end{lemma} \begin{lemma}\label{lemma-Xd} Given a prime $p>3$, $n=ip^t-\sum_{\ell=0}^{t-1}p^\ell$ with $1\leq i\leq p-1$, and the set $T=\set{1,2,\ldots,n}$; the set $T_1$ contains no $p$-AP with $$d \in \set{1 \leq d_1 \leq \smallfloor{(n-1) / (p-1)}: d_1 \not\equiv{0}\pmod{p}}.$$ \begin{proof} Assume $T_1$ contains a $p$-AP $a,a+d,\ldots,a+(p-1)d$. Here $a\not\equiv{0}\pmod{p}$. Suppose $a\equiv{j}\pmod{p}$ for some $1\leq j\leq p-1$. Then $a+d(p-z)\equiv 0\pmod{p}$ for some $1\leq z\leq p-1$ when $dz\equiv{j}\pmod{p}$. For each $d\in \set{1\leq d_1\leq \smallfloor{(n-1)/(p-1)}: d_1\not\equiv{0}\pmod{p}}$, $$\bigcup_{z=1}^{p-1}\set{dz\pmod{p}}=\set{1,2,\ldots,p-1}$$ and so there exists $1\leq z\leq p-1$ for any $1\leq j \leq p-1$ such that $dz\equiv{j}\pmod{p}$. But, this is a contradiction as there is no number in $T_1$ which is divisible by $p$. Hence $T_1$ contains no $p$-AP with $d\in \set{1\leq d_1\leq \smallfloor{(n-1)/(p-1)}: d_1\not\equiv{0}\pmod{p}}$. \end{proof} \end{lemma} \begin{lemma} The set $T_t$ is $p$-AP free. \begin{proof} By construction, $T_t$ contains no $p$-AP with $d\in\set{1,p,p^2,\ldots,p^t}$. By Lemma \ref{lemma-Xd}, $T_t$ does not contain a $p$-AP with any other $d$. Hence $T_t$ is $p$-AP free. \end{proof} \end{lemma} \subsection{A construction algorithm for $r(k,n)$} In this section, we propose a greedy algorithm for construction of $k$-AP free subsequence of $1,2,\ldots,n$. We call this algorithm \emph{Bi-symmetric Greedy Algorithm} (BGA) as it builds a fully symmetric subsequence that is $k$-AP free. \begin{enumerate} \item Take $T = \set{1,n}$. \item Choose the smallest $j\in \set{1,2,\ldots,n}-T$ such that $T\cup\set{j,n-j+1}$ is $k$-AP free. Set $T = T\cup\set{j,n-j+1}$. \item Repeat step 2 until no such $j$ can be found. \item Output $T$. \end{enumerate} Clearly, $$r(k,n) \geq |BGA(k,n)|.$$ From experimental data, we have the following observation: \begin{obs} Consider a prime $p>3$. Then $|BGA(p,x)|=x$ if $1\leq x\leq p-2$, or else for $1\leq i\leq p-1$ and $t\geq 1$, $$\left|BGA\left(p, {(ip-i-1)p^t+1 \over (p-1)}\right)\right| = i\cdot(p-1)^t.$$ \end{obs} See Appendix \ref{app-2} for supporting data. \section*{Acknowledgements} The authors would like to thank the anonymous referee and the Editor for helpful comments and suggestions. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{thebibliography}{9} \bibitem{behrend} F. A. Behrend, On Sets of Integers Which Contain No Three Terms in Arithmetic Progression, \emph{Proc. Nat. Acad. Sci. USA}, \textbf{32} (1946), 331--332. \bibitem{dybizbanski} J. Dybizba\'nski, Sequences containing no 3-term arithmetic progressions, \emph{Elec. J. of Comb.}, \textbf{19(2)} (2012), \#P15. \bibitem{elkin} M. Elkin, An Improved Construction of Progression-Free Sets, \emph{Israeli J. Math.}, \textbf{184}, (2011), 93--128. \bibitem{erdos-turan} P. Erd\H{o}s and P. Tur\'an, On some sequence of integers, \emph{J. London Math. Soc.}, \textbf{11} (1936), 261--264. \bibitem{roth} K. F. Roth, On certain set of integers, \emph{J. London Math. Soc.}, \textbf{28} (1953), 104--109. \bibitem{salem-spencer} R. Salem and D. C. Spencer, On Sets of Integers Which Contain No Three Terms in Arithmetic Progression, \emph{Proc. Nat. Acad. Sci. USA}, \textbf{28} (1942), 561--563. \bibitem{sharma} A. Sharma, Sequences of Integers Avoiding 3-term Arithmetic Progressions, \emph{Elec. J. of Comb.}, \textbf{19} (2012), \#P27. \bibitem{szemeredi} E. Szemeredi, On sets of integers containing no $k$ elements in arithmetic progression, \emph{Acta Arithmetica}, \textbf{27} (1975), 199--245. \end{thebibliography} \newpage \appendix \section{Computed values}\label{app-1} \footnotesize \indent\indent $f(3)=4$, $c_{max}(3,n-4)=c_{max}(3,n)+4$ for $n\ge 8$ \begin{longtable}{c|c|c||c|c|c||c|c|c||c} \hline $n$ & $c_{max}(3,n)$ & $|U|$ & $n$ & $c_{max}(3,n)$ & $|U|$ & $n$ & $c_{max}(3,n)$ & $|U|$ & \\ \hline 4 & 2 & 2 & 8 & 6 & 2 & 12 & 10 & 2 & $\cdots$ \\ 5 & 4 & \bf{4} & 9 & 8 & \bf{4} & 13 & 12 & \bf{4} & $\cdots$ \\ 6 & 4 & 2 & 10 & 8 & 2 & 14 & 12 & 2 & $\cdots$ \\ 7 & 5 & \bf{4} & 11 & 9 & \bf{4} & 15 & 13 & \bf{4} & $\cdots$ \\ \hline \end{longtable} $f(5)=8$, $c_{max}(5,n-24)=c_{max}(5,n)+20$ for $n\ge 62$ \begin{longtable}{c|c|c||c|c|c||c|c|c||c} \hline $n$ & $c_{max}(5,n)$ & $|U|$ & $n$ & $c_{max}(5,n)$ & $|U|$ & $n$ & $c_{max}(5,n)$ & $|U|$ & \\ \hline 38 & 29 & 6 & 62 & 49 & 6 & 86 & 69 & 6 & $\cdots$ \\ 39 & 30 & 6 & 63 & 50 & 6 & 87 & 70 & 6 & $\cdots$ \\ 40 & 31 & 6 & 64 & 51 & 6 & 88 & 71 & 6 & $\cdots$ \\ 41 & 32 & 6 & 65 & 52 & 6 & 89 & 72 & 6 & $\cdots$ \\ 42 & 33 & \bf{8} & 66 & 53 & \bf{8} & 90 & 73 & \bf{8} & $\cdots$ \\ $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ &$\vdots$ & $\vdots$ & $\vdots$ \\ 60 & 47 & 4 & 84 & 67 & 4 & 108 & 87 & 4 & $\cdots$ \\ 61 & 49 & \bf{8} & 85 & 69 & \bf{8} & 109 & 89 & \bf{8} & $\cdots$ \\ \hline \end{longtable} $f(7)=14$, $c_{max}(7,n-120)=c_{max}(7,n)+94$ for $n\ge 467$ \begin{longtable}{c|c|c||c|c|c||c|c|c||c} \hline $n$ & $c_{max}(7,n)$ & $|U|$ & $n$ & $c_{max}(7,n)$ & $|U|$ & $n$ & $c_{max}(7,n)$ & $|U|$ & \\ \hline 347 & 268 & 10 & 467 & 362 & 10 & 587 & 456 & 10 & $\cdots$ \\ 348 & 269 & 10 & 468 & 363 & 10 & 588 & 457 & 10 & $\cdots$ \\ 349 & 270 & 10 & 469 & 364 & 10 & 589 & 458 & 10 & $\cdots$ \\ 350 & 271 & 10 & 470 & 365 & 10 & 590 & 459 & 10 & $\cdots$ \\ $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ &$\vdots$ & $\vdots$ & $\vdots$ \\ 358 & 278 & \bf{14} & 478 & 372 & \bf{14} & 598 & 466 & \bf{14} & $\cdots$ \\ $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ &$\vdots$ & $\vdots$ & $\vdots$ \\ 465 & 361 & 10 & 585 & 455 & 10 & 705 & 549 & 10 & $\cdots$ \\ 466 & 361 & \bf{14} & 586 & 455 & \bf{14} & 706 & 549 & \bf{14} & $\cdots$ \\ \hline \end{longtable} $f(9)=20$, $c_{max}(9,n-6720)=c_{max}(9,n)+5104$ for $n\ge 13365$ \begin{longtable}{c|c|c||c|c|c||c|c|c||c} \hline $n$ & $c_{max}(9,n)$ & $|U|$ & $n$ & $c_{max}(9,n)$ & $|U|$ & $n$ & $c_{max}(9,n)$ & $|U|$ & \\ \hline 6645 & 5043 & 14 & 13365 & 10147 & 14 & 20085 & 15251 & 14 & $\cdots$ \\ 6646 & 5045 & 14 & 13366 & 10149 & 14 & 20086 & 15253 & 14 & $\cdots$ \\ 6647 & 5045 & 16 & 13367 & 10149 & 16 & 20087 & 15253 & 16 & $\cdots$ \\ 6648 & 5045 & 14 & 13368 & 10149 & 14 & 20088 & 15253 & 14 & $\cdots$ \\ $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ &$\vdots$ & $\vdots$ & $\vdots$ \\ 6691 & 5078 & \bf{20} & 13411 & 10182 & \bf{20} & 20131 & 15286 & \bf{20} & $\cdots$ \\ $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ &$\vdots$ & $\vdots$ & $\vdots$ \\ 13363 & 10146 & 14 & 20083 & 15250 & 14 & 26803 & 20354 & 14 & $\cdots$ \\ 13364 & 10146 & 16 & 20084 & 15250 & 16 & 26804 & 20354 & 16 & $\cdots$ \\ \hline \end{longtable} $f(11)=26$, $f(13)=36$ \normalsize \section{BGA results}\label{app-2} $$p=3$$ \footnotesize $t=1$, $i=1$, $|BGA(3,2)|=2$\\ $BGA(3,2)|=\{1, 2\}$\\ $t=2$, $i=1$, $|BGA(3,5)|=4$\\ $BGA(3,5)|=\{1, 2, 4, 5\}$\\ $t=3$, $i=1$, $|BGA(3,14)|=8$\\ $BGA(3,14)|=\{1, 2, 4, 5, 10, 11, 13, 14\}$\\ $t=4$, $i=1$, $|BGA(3,41)|=16$\\ $BGA(3,41)|=\{1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 37, 38, 40, 41\}$\\ $t=5$, $i=1$, $|BGA(3,122)|=32$\\ $BGA(3,122)|=\{1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 37, 38, 40, 41, 82, 83, 85, 86, 91, 92, 94, 95, 109, 110, $\\$112, 113, 118, 119, 121, 122\}$\\ $t=6$, $i=1$, $|BGA(3,365)|=64$\\ $BGA(3,365)|=\{1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 37, 38, 40, 41, 82, 83, 85, 86, 91, 92, 94, 95, 109, 110, $\\$112, 113, 118, 119, 121, 122, 244, 245, 247, 248, 253, 254, 256, 257, 271, 272, 274, 275, 280, 281, 283, 284, 325, $\\$326, 328, 329, 334, 335, 337, 338, 352, 353, 355, 356, 361, 362, 364, 365\}$\\ $t=7$, $i=1$, $|BGA(3,1094)|=128$\\ $BGA(3,1094)|=\{1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 37, 38, 40, 41, 82, 83, 85, 86, 91, 92, 94, 95, 109, 110, $\\$112, 113, 118, 119, 121, 122, 244, 245, 247, 248, 253, 254, 256, 257, 271, 272, 274, 275, 280, 281, 283, 284, 325, $\\$326, 328, 329, 334, 335, 337, 338, 352, 353, 355, 356, 361, 362, 364, 365, 730, 731, 733, 734, 739, 740, 742, 743,$\\$ 757, 758, 760, 761, 766, 767, 769, 770, 811, 812, 814, 815, 820, 821, 823, 824, 838, 839, 841, 842, 847, 848, 850,$\\$ 851, 973, 974, 976, 977, 982, 983, 985, 986, 1000, 1001, 1003, 1004, 1009, 1010, 1012, 1013, 1054, 1055, 1057,$\\$ 1058, 1063, 1064, 1066, 1067, 1081, 1082, 1084, 1085, 1090, 1091, 1093, 1094\}$\\ \normalsize $$p=5$$ \footnotesize $t=1$, $i=1$, $|BGA(5,4)|=4$\\ $BGA(5,4)|=\{1, 2, 3, 4\}$\\ $t=1$, $i=2$, $|BGA(5,9)|=8$\\ $BGA(5,9)|=\{1, 2, 3, 4, 6, 7, 8, 9\}$\\ $t=1$, $i=3$, $|BGA(5,14)|=12$\\ $BGA(5,14)|=\{1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14\}$\\ $t=2$, $i=1$, $|BGA(5,19)|=16$\\ $BGA(5,19)|=\{1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19\}$\\ $t=2$, $i=2$, $|BGA(5,44)|=32$\\ $BGA(5,44)|=\{1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 26, 27, 28, 29, 31, 32, 33, 34, 36, 37, 38, 39, 41, $\\$42, 43, 44\}$\\ $t=2$, $i=3$, $|BGA(5,69)|=48$\\ $BGA(5,69)|=\{1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 26, 27, 28, 29, 31, 32, 33, 34, 36, 37, 38, 39, 41, $\\$42, 43, 44, 51, 52, 53, 54, 56, 57, 58, 59, 61, 62, 63, 64, 66, 67, 68, 69\}$\\ $t=3$, $i=1$, $|BGA(5,94)|=64$\\ $BGA(5,94)|=\{1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 26, 27, 28, 29, 31, 32, 33, 34, 36, 37, 38, 39, 41,$\\$ 42, 43, 44, 51, 52, 53, 54, 56, 57, 58, 59, 61, 62, 63, 64, 66, 67, 68, 69, 76, 77, 78, 79, 81, 82, 83, 84, 86, 87, 88, 89,$\\$ 91, 92, 93, 94\}$\\ $t=3$, $i=2$, $|BGA(5,219)|=128$\\ $BGA(5,219)|=\{1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 26, 27, 28, 29, 31, 32, 33, 34, 36, 37, 38, 39, 41, $\\$42, 43, 44, 51, 52, 53, 54, 56, 57, 58, 59, 61, 62, 63, 64, 66, 67, 68, 69, 76, 77, 78, 79, 81, 82, 83, 84, 86, 87, 88, 89,$\\$ 91, 92, 93, 94, 126, 127, 128, 129, 131, 132, 133, 134, 136, 137, 138, 139, 141, 142, 143, 144, 151, 152, 153, 154,$\\$ 156, 157, 158, 159, 161, 162, 163, 164, 166, 167, 168, 169, 176, 177, 178, 179, 181, 182, 183, 184, 186, 187, 188,$\\$ 189, 191, 192, 193, 194, 201, 202, 203, 204, 206, 207, 208, 209, 211, 212, 213, 214, 216, 217, 218, 219\}$\\ \normalsize $$p=7$$ \footnotesize $t=1$, $i=1$, $|BGA(7,6)|=6$\\ $BGA(7,6)|=\{1, 2, 3, 4, 5, 6\}$\\ $t=1$, $i=2$, $|BGA(7,13)|=12$\\ $BGA(7,13)|=\{1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13\}$\\ $t=1$, $i=3$, $|BGA(7,20)|=18$\\ $BGA(7,20)|=\{1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20\}$\\ $t=1$, $i=4$, $|BGA(7,27)|=24$\\ $BGA(7,27)|=\{1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27\}$\\ $t=1$, $i=5$, $|BGA(7,34)|=30$\\ $BGA(7,34)|=\{1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 29, 30, 31, 32, 33,$\\$ 34\}$\\ $t=2$, $i=1$, $|BGA(7,41)|=36$\\ $BGA(7,41)|=\{1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 29, 30, 31, 32, 33,$\\$ 34, 36, 37, 38, 39, 40, 41\}$\\ $t=2$, $i=2$, $|BGA(7,90)|=72$\\ $BGA(7,90)|=\{1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 29, 30, 31, 32, 33,$\\$ 34, 36, 37, 38, 39, 40, 41, 50, 51, 52, 53, 54, 55, 57, 58, 59, 60, 61, 62, 64, 65, 66, 67, 68, 69, 71, 72, 73, 74, 75, 76,$\\$ 78, 79, 80, 81, 82, 83, 85, 86, 87, 88, 89, 90\}$\\ $t=2$, $i=3$, $|BGA(7,139)|=108$\\ $BGA(7,139)|=\{1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 29, 30, 31, 32, 33,$\\$ 34, 36, 37, 38, 39, 40, 41, 50, 51, 52, 53, 54, 55, 57, 58, 59, 60, 61, 62, 64, 65, 66, 67, 68, 69, 71, 72, 73, 74, 75, 76,$\\$ 78, 79, 80, 81, 82, 83, 85, 86, 87, 88, 89, 90, 99, 100, 101, 102, 103, 104, 106, 107, 108, 109, 110, 111, 113, 114,$\\$ 115, 116, 117, 118, 120, 121, 122, 123, 124, 125, 127, 128, 129, 130, 131, 132, 134, 135, 136, 137, 138, 139\}$\\ \normalsize $$p=11$$ \footnotesize $t=1$, $i=1$, $|BGA(11,10)|=10$\\ $BGA(11,10)|=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$\\ $t=1$, $i=2$, $|BGA(11,21)|=20$\\ $BGA(11,21)|=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21\}$\\ $t=1$, $i=3$, $|BGA(11,32)|=30$\\ $BGA(11,32)|=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31,$\\$ 32\}$\\ $t=1$, $i=4$, $|BGA(11,43)|=40$\\ $BGA(11,43)|=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31,$\\$ 32, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43\}$\\ $t=1$, $i=5$, $|BGA(11,54)|=50$\\ $BGA(11,54)|=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31,$\\$ 32, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54\}$\\ $t=1$, $i=6$, $|BGA(11,65)|=60$\\ $BGA(11,65)|=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31,$\\$ 32, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65\}$\\ $t=1$, $i=7$, $|BGA(11,76)|=70$\\ $BGA(11,76)|=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31,$\\$ 32, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, $\\$67, 68, 69, 70, 71, 72, 73, 74, 75, 76\}$\\ $t=1$, $i=8$, $|BGA(11,87)|=80$\\ $BGA(11,87)|=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31,$\\$ 32, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, $\\$67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87\}$\\ $t=1$, $i=9$, $|BGA(11,98)|=90$\\ $BGA(11,98)|=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31,$\\$ 32, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, $\\$67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98\}$\\ $t=2$, $i=1$, $|BGA(11,109)|=100$\\ $BGA(11,109)|=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31,$\\$ 32, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, $\\$67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 100,$\\$ 101, 102, 103, 104, 105, 106, 107, 108, 109\}$\\ $t=2$, $i=2$, $|BGA(11,230)|=200$\\ $BGA(11,230)|=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31,$\\$ 32, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, $\\$67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 100,$\\$ 101, 102, 103, 104, 105, 106, 107, 108, 109, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 133, 134, 135, 136,$\\$ 137, 138, 139, 140, 141, 142, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 155, 156, 157, 158, 159, 160, 161, $\\$162, 163, 164, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186,$\\$ 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 210, 211, 212,$\\$ 213, 214, 215, 216, 217, 218, 219, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230\}$\\ \normalsize \newpage \section{Computed values of $r(k,n)$}\label{app-3} \footnotesize \begin{longtable}{c|c|c|c|c||c|c|c|c|c} \hline $n$ & $b(n)$ & lower bound & $r(3,n)$ & upper bound & $n$ & $b(n)$ & lower bound & $r(3,n)$ & upper bound \\ & & $|BGA(3,n)|$ & & (Theorem~\ref{thm1}) & & & $|BGA(3,n)|$ & & (Theorem~\ref{thm1}) \\ \hline 4 & 2 & 2 & 3 & 3 & 54 & 2 & 16 & 18 & 41 \\ 5 & 1 & 4 & 4 & 4 & 58 & 2 & 16 & 19 & 44\\ 9 & 4 & 4 & 5 & 7 & 63 & 2 & 16 & 20 & 48\\ 11 & 7 & 6 & 6 & 9 & 71 & 4 & 18 & 21 & 54\\ 13 & 6 & 6 & 7 & 10 & 74 & 1 & 18 & 22 & 56\\ 14 & 1 & 8 & 8 & 11 & 82 & 10 & 18 & 23 & 62\\ 20 & 2 & 8 & 9 & 15 & 84 & 1 & 18 & 24 & 63\\ 24 & 2 & 8 & 10 & 18 & 92 & 14 & 22 & 25 & 69\\ 26 & 2 & 10 & 11 & 20 & 95 & 8 & 24 & 26 & 72\\ 30 & 1 & 10 & 12 & 23 & 100 & 2 & 24 & 27 & 75\\ 32 & 2 & 12 & 13 & 24 & 104 & 1 & 24 & 28 & 78\\ 36 & 2 & 12 & 14 & 27 & 111 & 6 & 26 & 29 & 84\\ 40 & 20 & 14 & 15 & 30 & 114 & 1 & 28 & 30 & 86\\ 41 & 1 & 16 & 16 & 31 & 121 & 70 & 30 & 31 & 91\\ 51 & 14 & 16 & 17 & 39 & 122 & 1 & 32 & 32 & 92\\ \hline \end{longtable} \begin{longtable}{c|c|c|c|c||c|c|c|c|c} \hline $n$ & $b(n)$ & lower bound & $r(4,n)$ & upper bound & $n$ & $b(n)$ & lower bound & $r(4,n)$ & upper bound \\ & & $|BGA(4,n)|$ & & (Theorem~\ref{thm1}) & & & $|BGA(4,n)|$ & & (Theorem~\ref{thm1}) \\ \hline 5 & 3 & 4 & 4 & 5 & 30 & 2 & 16 & 18 & 25\\ 6 & 2 & 4 & 5 & 5 & 33 & 6 & 16 & 19 & 28\\ 8 & 4 & 6 & 6 & 7 & 34 & 2 & 18 & 20 & 29\\ 9 & 2 & 6 & 7 & 8 & 37 & 6 & 18 & 21 & 31\\ 10 & 1 & 8 & 8 & 9 & 40 & 14 & 18 & 22 & 34\\ 13 & 3 & 9 & 9 & 11 & 43 & 38 & 18 & 23 & 36\\ 15 & 2 & 8 & 10 & 13 & 45 & 2 & 20 & 24 & 38\\ 17 & 10 & 10 & 11 & 15 & 48 & 2 & 20 & 25 & 40\\ 19 & 24 & 12 & 12 & 16 & 50 & 3 & 22 & 26 & 42\\ 21 & 10 & 12 & 13 & 18 & 53 & 12 & 22 & 27 & 45\\ 23 & 12 & 13 & 14 & 20 & 54 & 1 & 24 & 28 & 45\\ 25 & 2 & 14 & 15 & 21 & 58 & 6 & 26 & 29 & 49\\ 27 & 8 & 14 & 16 & 23 & 60 & 1 & 26 & 30 & 50\\ 28 & 4 & 14 & 17 & 24 & & & & & \\ \hline \end{longtable} \newpage \begin{longtable}{c|c|c|c|c||c|c|c|c|c} \hline $n$ & $b(n)$ & lower bound & $r(5,n)$ & upper bound & $n$ & $b(n)$ & lower bound & $r(5,n)$ & upper bound \\ & & $|BGA(5,n)|$ & & (Theorem~\ref{thm1}) & & & $|BGA(5,n)|$ & & (Theorem~\ref{thm1}) \\ \hline 6 & 4 & 4 & 5 & 6 & 52 & 2 & 32 & 35 & 46\\ 7 & 3 & 6 & 6 & 7 & 54 & 1300 & 32 & 36 & 48\\ 8 & 2 & 6 & 7 & 7 & 56 & 3508 & 32 & 37 & 49\\ 9 & 1 & 8 & 8 & 8 & 57 & 1736 & 36 & 38 & 50\\ 11 & 6 & 8 & 9 & 10 & 58 & 768 & 32 & 39 & 51\\ 12 & 4 & 10 & 10 & 11 & 59 & 256 & 40 & 40 & 52\\ 13 & 2 & 8 & 11 & 12 & 61 & 512 & 36 & 41 & 54\\ 14 & 1 & 12 & 12 & 13 & 62 & 192 & 38 & 42 & 55\\ 16 & 4 & 12 & 13 & 14 & 63 & 64 & 38 & 43 & 56\\ 17 & 3 & 12 & 14 & 15 & 64 & 16 & 36 & 44 & 56\\ 18 & 2 & 14 & 15 & 16 & 66 & 32 & 40 & 45 & 58\\ 19 & 1 & 16 & 16 & 17 & 67 & 12 & 40 & 46 & 59\\ 24 & 40 & 16 & 17 & 21 & 68 & 4 & 42 & 47 & 60\\ 25 & 2 & 16 & 18 & 22 & 69 & 1 & 48 & 48 & 61\\ 27 & 70 & 18 & 19 & 24 & 76 & 2012 & 42 & 49 & 67\\ 28 & 12 & 18 & 20 & 25 & 77 & 1202 & 44 & 50 & 68\\ 29 & 2 & 20 & 21 & 26 & 78 & 640 & 44 & 51 & 69\\ 31 & 5 & 20 & 22 & 28 & 79 & 256 & 48 & 52 & 70\\ 33 & 266 & 22 & 23 & 29 & 81 & 768 & 44 & 53 & 71\\ 34 & 81 & 24 & 24 & 30 & 82 & 432 & 48 & 54 & 72\\ 36 & 236 & 24 & 25 & 32 & 83 & 216 & 48 & 55 & 73\\ 37 & 115 & 26 & 26 & 33 & 84 & 81 & 52 & 56 & 74\\ 38 & 48 & 24 & 27 & 34 & 86 & 216 & 50 & 57 & 76\\ 39 & 16 & 28 & 28 & 35 & 87 & 108 & 52 & 58 & 77\\ 41 & 32 & 26 & 29 & 36 & 88 & 48 & 50 & 59 & 77\\ 42 & 12 & 28 & 30 & 37 & 89 & 16 & 56 & 60 & 78\\ 43 & 4 & 30 & 31 & 38 & 91 & 32 & 54 & 61 & 80\\ 44 & 1 & 32 & 32 & 39 & 92 & 12 & 56 & 62 & 81\\ 49 & 2 & 32 & 33 & 43 & 93 & 4 & 56 & 63 & 82\\ 51 & 18 & 32 & 34 & 45 & 94 & 1 & 64 & 64 & 83\\ \hline \end{longtable} \newpage \begin{longtable}{c|c|c|c|c||c|c|c|c|c} \hline $n$ & $b(n)$ & lower bound & $r(7,n)$ & upper bound & $n$ & $b(n)$ & lower bound & $r(7,n)$ & upper bound \\ & & $|BGA(7,n)|$ & & (Theorem~\ref{thm1}) & & & $|BGA(7,n)|$ & & (Theorem~\ref{thm1}) \\ \hline 8 & 6 & 6 & 7 & 8 & 51 & 76 & 38 & 40 & 47\\ 9 & 5 & 8 & 8 & 9 & 52 & 22 & 38 & 41 & 48\\ 10 & 4 & 8 & 9 & 10 & 53 & 2 & 40 & 42 & 49\\ 11 & 3 & 10 & 10 & 11 & 55 & 242 & 42 & 43 & 51\\ 12 & 2 & 10 & 11 & 11 & 56 & 8 & 42 & 44 & 52\\ 13 & 1 & 12 & 12 & 12 & 57 & 4 & 42 & 45 & 53\\ 15 & 12 & 12 & 13 & 14 & 59 & 218 & 44 & 46 & 55\\ 16 & 9 & 14 & 14 & 15 & 60 & 54 & 46 & 47 & 55\\ 17 & 6 & 13 & 15 & 16 & 61 & 10 & 46 & 48 & 56\\ 18 & 4 & 16 & 16 & 17 & 63 & 32 & 48 & 49 & 58\\ 19 & 2 & 16 & 17 & 18 & 64 & 14 & 48 & 50 & 59\\ 20 & 1 & 18 & 18 & 19 & 65 & 2 & 50 & 51 & 60\\ 22 & 8 & 18 & 19 & 21 & 67 & 19807 & 52 & 52 & 62\\ 23 & 6 & 20 & 20 & 22 & 68 & 10294 & 52 & 53 & 63\\ 24 & 4 & 20 & 21 & 22 & 69 & 4103 & 54 & 54 & 64\\ 25 & 3 & 20 & 22 & 23 & 71 & 18522 & 54 & 55 & 66\\ 26 & 2 & 20 & 23 & 24 & 72 & 11541 & 56 & 56 & 66\\ 27 & 1 & 24 & 24 & 25 & 73 & 6914 & 54 & 57 & 67\\ 29 & 6 & 22 & 25 & 27 & 74 & 3888 & 56 & 58 & 68\\ 30 & 5 & 24 & 26 & 28 & 75 & 1944 & 56 & 59 & 69\\ 31 & 4 & 24 & 27 & 29 & 76 & 729 & 60 & 60 & 70\\ 32 & 3 & 24 & 28 & 30 & 78 & 2918 & 58 & 61 & 72\\ 33 & 2 & 26 & 29 & 31 & 79 & 1621 & 62 & 62 & 73\\ 34 & 1 & 30 & 30 & 32 & 80 & 864 & 60 & 63 & 74\\ 36 & 6 & 30 & 31 & 33 & 81 & 432 & 60 & 64 & 75\\ 37 & 5 & 28 & 32 & 34 & 82 & 192 & 62 & 65 & 76\\ 38 & 4 & 30 & 33 & 35 & 83 & 64 & 66 & 66 & 77\\ 39 & 3 & 32 & 34 & 36 & 85 & 192 & 64 & 67 & 78\\ 40 & 2 & 30 & 35 & 37 & 86 & 80 & 64 & 68 & 79\\ 41 & 1 & 36 & 36 & 38 & 87 & 32 & 66 & 69 & 80\\ 46 & 18 & 36 & 37 & 43 & 88 & 12 & 68 & 70 & 81\\ 48 & 9 & 36 & 38 & 44 & 89 & 4 & 66 & 71 & 82\\ 50 & 392 & 36 & 39 & 46 & 90 & 1 & 72 & 72 & 83\\ \hline \end{longtable} \newpage \begin{longtable}{c|c|c|c|c||c|c|c|c|c} \hline $n$ & $b(n)$ & lower bound & $r(11,n)$ & upper bound & $n$ & $b(n)$ & lower bound & $r(11,n)$ & upper bound \\ & & $|BGA(11,n)|$ & & (Theorem~\ref{thm1}) & & & $|BGA(11,n)|$ & & (Theorem~\ref{thm1}) \\ \hline 12 & 10 & 10 & 11 & 12 & 61 & 5 & 54 & 56 & 58\\ 13 & 9 & 12 & 12 & 13 & 62 & 4 & 52 & 57 & 59\\ 14 & 8 & 12 & 13 & 14 & 63 & 3 & 54 & 58 & 60\\ 15 & 7 & 14 & 14 & 15 & 64 & 2 & 56 & 59 & 61\\ 16 & 6 & 14 & 15 & 16 & 65 & 1 & 60 & 60 & 62\\ 17 & 5 & 16 & 16 & 17 & 67 & 10 & 56 & 61 & 64\\ 18 & 4 & 16 & 17 & 18 & 68 & 9 & 58 & 62 & 65\\ 19 & 3 & 18 & 18 & 19 & 69 & 8 & 58 & 63 & 66\\ 20 & 2 & 18 & 19 & 19 & 70 & 7 & 62 & 64 & 67\\ 21 & 1 & 20 & 20 & 20 & 71 & 6 & 62 & 65 & 68\\ 23 & 30 & 20 & 21 & 22 & 72 & 5 & 60 & 66 & 69\\ 24 & 25 & 22 & 22 & 23 & 73 & 4 & 62 & 67 & 70\\ 25 & 20 & 21 & 23 & 24 & 74 & 3 & 62 & 68 & 71\\ 26 & 16 & 24 & 24 & 25 & 75 & 2 & 66 & 69 & 72\\ 27 & 12 & 24 & 25 & 26 & 76 & 1 & 70 & 70 & 73\\ 28 & 9 & 26 & 26 & 27 & 78 & 10 & 66 & 71 & 75\\ 29 & 6 & 25 & 27 & 28 & 79 & 9 & 66 & 72 & 76\\ 30 & 4 & 28 & 28 & 29 & 80 & 8 & 68 & 73 & 76\\ 31 & 2 & 28 & 29 & 30 & 81 & 7 & 68 & 74 & 77\\ 32 & 1 & 30 & 30 & 31 & 82 & 6 & 68 & 75 & 78\\ 34 & 20 & 30 & 31 & 33 & 83 & 5 & 72 & 76 & 79\\ 35 & 16 & 32 & 32 & 34 & 84 & 4 & 72 & 77 & 80\\ 36 & 12 & 32 & 33 & 35 & 85 & 3 & 74 & 78 & 81\\ 37 & 9 & 32 & 34 & 36 & 86 & 2 & 74 & 79 & 82\\ 38 & 6 & 34 & 35 & 37 & 87 & 1 & 80 & 80 & 83\\ 39 & 5 & 34 & 36 & 38 & 89 & 10 & 76 & 81 & 85\\ 40 & 4 & 36 & 37 & 38 & 90 & 9 & 78 & 82 & 86\\ 41 & 3 & 36 & 38 & 39 & 91 & 8 & 76 & 83 & 87\\ 42 & 2 & 38 & 39 & 40 & 92 & 7 & 80 & 84 & 88\\ 43 & 1 & 40 & 40 & 41 & 93 & 6 & 80 & 85 & 89\\ 45 & 10 & 39 & 41 & 43 & 94 & 5 & 80 & 86 & 90\\ 46 & 9 & 40 & 42 & 44 & 95 & 4 & 82 & 87 & 91\\ 47 & 8 & 40 & 43 & 45 & 96 & 3 & 80 & 88 & 92\\ 48 & 7 & 42 & 44 & 46 & 97 & 2 & 80 & 89 & 93\\ 49 & 6 & 42 & 45 & 47 & 98 & 1 & 90 & 90 & 94\\ 50 & 5 & 44 & 46 & 48 & 100 & 10 & 84 & 91 & 95\\ 51 & 4 & 43 & 47 & 49 & 101 & 9 & 84 & 92 & 96\\ 52 & 3 & 44 & 48 & 50 & 102 & 8 & 88 & 93 & 97\\ 53 & 2 & 46 & 49 & 51 & 103 & 7 & 86 & 94 & 98\\ 54 & 1 & 50 & 50 & 52 & 104 & 6 & 88 & 95 & 99\\ 56 & 10 & 48 & 51 & 54 & 105 & 5 & 90 & 96 & 100\\ 57 & 9 & 50 & 52 & 55 & 106 & 4 & 90 & 97 & 101\\ 58 & 8 & 50 & 53 & 56 & 107 & 3 & 92 & 98 & 102\\ 59 & 7 & 50 & 54 & 57 & 108 & 2 & 92 & 99 & 103\\ 60 & 6 & 52 & 55 & 57 & 109 & 1 & 100 & 100 & 104\\ \hline \end{longtable} \normalsize \end{document}