\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf Integer Sequences Avoiding Prime Pairwise \\ \vskip .1in Sums } \vskip 1cm \large Yong-Gao Chen\footnote{Supported by the National Natural Science Foundation of China, Grant No.\ 10771103.}\\ Department of Mathematics \\ Nanjing Normal University\\ Nanjing 210097 \\ P. R. CHINA\\ \href{mailto:ygchen@njnu.edu.cn}{\tt ygchen@njnu.edu.cn} \\ \end{center} \vskip .2 in \begin{abstract} The following result is proved: If $A\subseteq \{ 1,\, 2,\, \ldots ,\, n\} $ is the subset of largest cardinality such that the sum of no two (distinct) elements of $A$ is prime, then $|A|=\lfloor(n+1)/2\rfloor$ and all the elements of $A$ have the same parity. The following open question is posed: what is the largest cardinality of $A\subseteq \{ 1,\, 2,\, \ldots ,\, n\} $ such that the sum of no two (distinct) elements of $A$ is prime and $A$ contains elements of both parities? \end{abstract} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{defin}[theorem]{Definition} \newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}} \newtheorem{examp}[theorem]{Example} \newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}} \newtheorem{rema}[theorem]{Example} \newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}} \newtheorem{ques}[theorem]{Question} \newenvironment{question}{\begin{ques}\normalfont\quad}{\end{ques}} \section{Introduction} Some combinatorial problems have the following structure: find subsets $A\subseteq \{ 1,\, 2,\, \ldots ,\, n\} $ such that the sum of no two (distinct) elements of $A$ belongs to $T$,\, where $T$ is a given set. We say that such a $A$ is a {\it $T$-sumset-free set}. In this note we deal with the case $T=P$,\, the set of all primes. There appear to be no previous papers on this topic. We try to determine all prime-sumset-free subsets of $\{ 1,\, 2,\, \ldots ,\, n\} $ with the largest cardinality. Let the largest cardinality be $U_n$. It is clear that the set of all even (odd) integers in $\{ 1,\, 2,\, \ldots ,\, n\} $ is a prime-sumset-free set. So $U_n\ge \lfloor(n+1)/2\rfloor$. If $n+1$ is prime,\, then by considering $a$ and $n+1-a$ we have $U_n\le \lfloor(n+1)/2\rfloor$. Thus $U_n=\lfloor(n+1)/2\rfloor$ if $n+1$ is prime. By employing results about the distribution of primes we prove \begin{theorem}\label{thm1} For all $n\ge 1$ we have $U_n=\lfloor\frac12(n+1)\rfloor$. Furthermore,\, if $A\subseteq \{ 1,\, 2,\, \ldots ,\, n\} $ is a prime-sumset-free set with $|A|=U_n$,\, then all elements of $A$ have the same parity. \end{theorem} A prime-sumset-free subset $A$ of $\{ 1,\, 2,\, \ldots ,\, n\} $ is called {\it an extremal prime-sumset-free subset} of $\{ 1,\, 2,\, \ldots ,\, n\} $ if $A\cup \{ a\} $ is not a prime-sumset-free subset for any $a\in \{ 1,\, 2,\, \ldots ,\, n\}\setminus A $. Let $PF_k(n)$ $(k=1,\, 2,\, \ldots )$ be the sequence of cardinalities of all extremal prime-sumset-free subsets of $\{ 1,\, 2,\, \ldots ,\, n\} $ with $PF_1(n)>PF_2(n)>\ldots $. By the theorem we have $PF_1(n)=U_n=\lfloor(n+1)/2\rfloor$. We pose the following open question: \begin{question} What are the values of $PF_k(n)$? In particular,\, What is the value of $PF_2(n)$?\end{question} \begin{question} Determine all extremal prime-sumset-free subsets $A$ with $|A|=PF_2(n)$.\end{question} \section{Proof of the Theorem} Although the proof of the second part implies the first part, we give a proof of the first part by induction and the application of Bertrand's postulate here. It is easy to see that the conclusion is true for $n=1$. Now we assume that the conclusion is true for $n\sqrt 2 n$ and $n\ge 8$,\, then there exists at least one prime $p$ with $m>p>n$.\end{lemma} \begin{proof} By direct calculation we know that Lemma \ref{lem1} is true for $8\le x\le 25$. If $x>25$, by Nagura \cite{Nagura} (see also \cite[Lemma 4]{Chen} ) we have $$\pi (\sqrt 2 x)-\pi (x)\ge \pi \bigl(\frac 65 x\bigr)-\pi (x)\ge 1.$$ This completes the proof of Lemma \ref{lem1}.\end{proof} Now we return to prove the second part of Theorem \ref{thm1}. For $n\le 8$ we can verify Theorem \ref{thm1} directly. Now we assume that $k>8$ and Theorem \ref{thm1} is true for all $n\sqrt 2 k$. If $8(\sqrt 2-1)k\ge 8$. For any $q_k-k\le a \le k$ we have $|A\cap \{ a,\, \,\, q_k-a\} |\le 1$. Hence $$|A\cap [q_k-k,\, \,\, k]|\le \frac 12 (2k-q_k+1).$$ Since $A\cap [1,\, \,\, q_k-k-1]$ is a prime-sumset-free set,\, we have $$|A\cap [1,\, \,\, q_k-k-1]|\le U_{q_k-k-1}=\bigl\lfloor \frac 12(q_k-k)\bigr\rfloor .$$ By the assumption $|A|=U_k=\lfloor(k+1)/2\rfloor$ we have \begin{eqnarray*}\bigl\lfloor\frac 12(k+1)\bigr\rfloor=|A|&=&|A\cap [1,\, \,\, q_k-k-1]| +|A\cap [q_k-k,\, \,\, k]|\\ &\le & \bigl\lfloor\frac 12(q_k-k)\bigr\rfloor +\frac 12(2k-q_k+1)\\ &=&\bigl\lfloor\frac 12(k+1)\bigr\rfloor.\end{eqnarray*} So $$|A\cap [1,\, \,\, q_k-k-1]|= \bigl\lfloor\frac 12(q_k-k)\bigr\rfloor =U_{q_k-k-1} .$$ If $2|k$,\, then by the induction hypothesis we have $$A\cap [1,\, \,\, q_k-k-1]=\{ 1,\, 3,\, \ldots ,\, q_k-k-2\} \mbox{ or } \{ 2,\, 4,\, \ldots ,\, q_k-k-1\} .$$ If $2\not| k$,\, then by the induction hypothesis we have $$A\cap [1,\, \,\, q_k-k-1]=\{ 1,\, 3,\, \ldots ,\, q_k-k-1\} .$$ {\bf Case 1:} $2|k$ and $A\cap [1,\, \,\, q_k-k-1]=\{ 1,\, 3,\, \ldots ,\, q_k-k-2\} $. Let $2m\in [q_k-k,\, \,\, k]$. Then $$\frac{2m+q_k-k}{2m}=1+\frac{q_k-k}{2m}>1+\frac{\sqrt 2 k-k}{k}=\sqrt 2.$$ By $q_k-k\ge 8$ and Lemma \ref{lem1} there exists at least one prime $p$ with $2m1+\frac{\sqrt 2 k-k}{k}=\sqrt 2.$$ By $q_k-k\ge 8$ and Lemma \ref{lem1} there exists at least one prime $p$ with $2m+11+\frac{\sqrt 2 k-k}{k}=\sqrt 2.$$ By $q_k-k\ge 8$ and Lemma \ref{lem1} there exists at least one prime $p$ with $2m