Journal of Integer Sequences, Vol. 1 (1998), Article 98.1.2 |

School of Computer Science

Carnegie Mellon University, Pittsburgh, PA 15213-3890

Email address: leg@andrew.cmu.edu

and

Stephen J. Greenfield

Department of Mathematics

Rutgers University, New Brunswick NJ 08903-2390

Email address: greenfie@math.rutgers.edu

"Bertrand's Postulate" is that, for every n > 3, there is a
prime p satisfying n < p < 2n-2. Bertrand verified this
for n < 3, 000, 000 and Tchebychef proved it for all
n > 3 in 1850. |

**Proof.** We prove this by complete induction. The assertion is
true when *k=1* since 3 is prime. Now consider the set of
integers {*1, 2, ..., 2k*}, and assume that all the sets {*1, 2,
..., 2j*} have been successfully paired where *j* is any
integer in the range *0 < j < k*. We begin by trying to pair
*2k* with some other number. The possible pairs are *(j,
2k)* with *0 < j < 2k*. The sums of these pairs are all the
integers from *2k+1* to *4k-1*. Since *2 (2k+1) -2 >
4k-1* Bertrand's Postulate insures that one of these numbers, say
*2k+m*, is a prime. But *m* is odd, so the set {*m, m+1,
..., 2k-1, 2k*} has an even number of elements. This set can be
paired so that the sum of the elements in each pair is the prime
*2k+m*: just pair *m+1* with *2k-1*, *m+2* with
*2k-2*, etc. The proof is done because our inductive assumption
implies that the initial segment from *1* to *m-1* can be
paired so that the sum of the elements in each pair is a prime. ¤

**Definition 1.** A sequence of integers {*a _{k}*} has
the

**Note.** The fact that *f(k)=k* has the CB property is
essentially *equivalent* to Bertrand's Postulate. For if we know
that for every positive integer *k*, there is *m* with *0 <
m < 2k* so that *2k+m* is prime, then (taking *n = 2k*)
there must be a prime between *n* and *2n*. A simple
adjustment can be made for odd *n* so a form of Bertrand's Postulate
must be true.

What other functions have the CB property? Simple numerical
experiments lead to the belief that many functions do or that they
have the CB property "eventually". For example, suppose *f* is a
polynomial of degree 1 (*f(n)=an+b*), and property CB holds. Then
*f(n)+f(m)= a(n+m) + 2b* must be prime infinitely often. By the
classical result of Dirichlet on primes in arithmetic progressions
this is equivalent to asking that gcd(*a*,*2b*) = 1. This
Dirichlet condition does *not* imply the CB property, however:
consider the function *f(n)=11n+1* and the set of the first
*2k* values of *f* when *k=1*. But such functions most
likely eventually satisfy CB.

**Definition 2.** A sequence of integers {*a _{k}*} has

We suspect the following result is true:

**Conjecture 0.** If *f(n)= an+b* and *a* and *b*
satisfy the Dirichlet condition gcd(*a*,*2b*)=1, then
*f* is eventually CB.

The proof would imitate that of Theorem 1 above. If *M(K)* is the
number of primes less than *K* of the form *ak+b*, then
*M(K)* is approximately * C K/ (log K)* where *C* is a
constant (the reciprocal of the Euler phi function at *a*). For
example, see [E], p. 17, where an error estimate (* O(K exp(-c (log
K) ^{½})* with

**"Theorem 2".** The probability that the set {1^{2},
2^{2}, ..., *(2k)*^{2}} can be broken up into
*k* pairs so that the sum of the elements of each pair is a prime
approaches 1 as *k* approaches infinity.

**"Proof".** The Prime Number Theorem states that there are about
*K/(log K)* primes less than or equal to *K*. Thus the
chance that *t* randomly selected integers in the range
*[1,K]* are prime is approximately *(log
K) ^{-t}*. If we fix a positive integer

**Comments.** The use of the quotes (" and ") in both the Theorem
and the Proof above is certainly justified, since both the statement
and the verification are more approximate than precise. What is really
shown is that any sequence with at most, say, polynomial growth (such
as *k ^{2}*), will have "the CB property" relative to a
"sparse" sequence such as the primes. We have implicitly made
assumptions about uniform distribution and independence which are not
valid here. First, the sums of the elements in each pair are far from
random relative to the primes (e.g., the function

In spite of the above objections, experimental evidence shows that
there are far *more* successful pairings than predicted by the
rough probabilistic "Proof" above. Below is a table of what happens
for *k* between 1 and 10 in both the linear (*f(k)=k*) and
quadratic (*f(k)=k^2*) cases. We give the "expected" number of
successful complete pairings predicted using a Stirling's formula
approximation (for the quadratic case as in the "Proof" above, and
for the linear case with *K=4k*). We show the number actually
observed. For background, we also present the total number of possible
complete pairings (our probabilistic universe) in each case.

k = |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

# of complete pairings | 1 | 3 | 15 | 105 | 945 | 10 395 | 135 135 | 2 027 025 | 34 459 425 | 654 729 075 |

Expected number of successes (linear case) | .7505 | .7081 | .9912 | 1.795 | 3.949 | 10.15 | 29.80 | 97.89 | 355.2 | 1 409 |

Actual # of successes (linear case) | 1 | 2 | 3 | 6 | 26 | 96 | 210 | 1 106 | 3 759 | 12 577 |

Expected # of successes (quad. case) | .5004 | .2549 | .1944 | .1914 | .2282 | .3174 | .5022 | .8883 | 1.733 | 3.691 |

Actual # of successes (quad. case) | 1 | 1 | 2 | 4 | 12 | 9 | 72 | 160 | 428 | 2 434 |

We cannot explain the interesting large discrepancies in the figures above.

It is possible to obtain functions which are far from having the CB property but which also have pairwise relatively prime values.

**Theorem 3.** There exist injective integer-valued functions
*f* with gcd(*f(i)*, *f(j)*) = 1 for all positive
integer i and j, and such that *f(i)+f(j)* is composite for all
positive integer *i* and *j*.

**Proof.** We give a simple "lacunary" construction of one such
function. First, for each integer *K* we construct an
integer-valued function *g _{K}* which signals

**Note.** The (non-unique) function created in the theorem is
increasing. For example, if we begin by assuming *f(1)=1* then
*f(2)=3*, *f(3)=7*, *f(4)=5 041* and *f(5)*
is approximately 10^{16 480}. So *f* is very
rapidly increasing. Are there simple functions with slower growth
which satisfy the conclusions of this theorem? The probabilistic
assertions of "Theorem" 2 do *not* apply to the functions
constructed here because of their rapid growth.

**Conjecture 1.** Suppose *f* is a polynomial with integer
coefficients which is positive for positive *k*. Then *f*
has property CB eventually if and only if *f(k)+f(j)* is an
irreducible polynomial in two variables and *f(k)+f(j)* has
content 1.

"Content" here means the gcd of the coefficients of a polynomial,
and is the natural generalization of the Dirichlet condition of
Conjecture 0. Certainly the conditions of this Conjecture are necessary,
and the probabilistic analysis of "Theorem" 2 makes it natural to
hope that they are sufficient. Of course the CB problem can be
restated as a graph-coloring problem, where the nodes are the integers
{1, 2, ..., *2k*}, and two nodes *k* and *j* are
connected by an edge exactly when *f(k)+f(j)* is prime. This
seems to offer no enlightenment, but does lead to a somewhat
generalized conjecture. We could put in edges where other functions
are prime (e.g., *k ^{2} + kj + j^{2}*), or we can
even investigate more general examples (analogous to directed
graphs). Namely, we can study any polynomial in two variables, rather
than one which is symmetric in its two variables. Then the CB
property itself will lose some symmetry, but here is one possible
generalization:

**Conjecture 2.** Suppose *p(k,j)* is a polynomial in two
variables with integer coefficients, and *p* is irreducible with
content 1. If *n* is sufficiently large, then the set {1, 2, ...,
*2n*} can be arranged into *n* disjoint pairs so that if
(*a*,*b*) is one pair, either *p(a,b)* or *p(b,a)*
is prime.

Numerical experiments with several polynomials (e.g.,
*k+j ^{2}*,

We can further generalize by looking at "higher order" versions of the CB property:

**Definition 3.** Suppose *N* is a positive integer. A sequence
of integers {*a _{k}*} has the

One can make obvious generalizations to fit the phrases: a function
has the *N*^{th} order CB property or a sequence (or
function) has the *N*^{th} order CB property
eventually. When *N* = 1, such sequences have to be subsequences
of the primes. A simple conjecture which we are unable to verify is
the following:

**Conjecture 3.** The sequence of odd integers {1, 3, 5, ... } has
the third order CB property eventually.

Again, probabilistic reasoning coupled with the obvious necessary
conditions applied here to the polynomial *2 (k + j + i) + 3*
seem to suggest the truth of Conjecture 3.

A additional natural collection of sequences to study for CB behavior
would be sequences defined by simple linear recursions. For example,
consider the sequence defined by the following recursion and initial
condition: * a _{n+1} = 2 a_{n} + 1* with

This recursion can be solved explicitly to obtain *a _{n} =
2^{n} -1*. Does this sequence have the third order CB
property? Here the probabilistic reasoning does not apply because of
the growth of {

On the other hand, functions with finite range are also of interest.
In trying to determine how many distinct functions with finite range
there are which have the *N*^{th} order CB property, we
come across the following extremal problem:

**Problem 1.** Suppose *S* and *T* are positive
integers. Find a set of integers {*a _{1}, ...,
a_{S}*} with the maximum number of

Is an initial segment of the integers such an extremal set?

These questions all seem to be difficult because even the simplest
non-linear case (does *f(k)=k ^{2}* have the CB property?)
approaches the limits of current knowledge. For example, it is not
known if there are infinitely many prime numbers of the form

Finally, we have a question about algorithms. Suppose we're given
an integer-valued function, *f*. How can we check if some initial
values of *f* have the CB property? Since the number of pairs to
be checked is very large, any way to shrink this number is worth
considering. It is disconcerting to report that a sort of **Greedy
Algorithm** seems to work even when there is no justification. The
Greedy Algorithm is motivated by the proof of Theorem 1. Suppose
*f* is increasing (e.g., *f(k)=k* or
*f(k)=k ^{2}*). In order to check pairs in the set {

The proof of Theorem 1 shows that the Greedy Algorithm must be
successful for *f(k)=k*. However, the Greedy Algorithm has been
successful in every example we have checked for
*f(k)=k ^{2}*. It does not seem to work with some other
polynomials. If

**Problem 2.** Is the Greedy Algorithm always successful for
*f(k)= k ^{2}*?

It is possible that we've just been lucky because there are many coincidences for small numbers.

[HW] G. H. Hardy and E. M. Wright,

(This is the source for sequences A000341 and A000348 .)

Written October 1991; revised December 1997; published in Journal of Integer Sequences Jan. 1, 1998.

Return to