Subject: Prime sequences
From: [email-masked] (David A. Wagner)
Date: Sun, 16 May 1993 18:49:14 GMT
Newsgroups: rec.puzzles,sci.math

I was trying to solve a puzzle about matrices where adjacent
elements sum up to primes, and I started to wonder a little about
a one-dimensional analogue to that problem.

	Suppose we have a sequence of positive integers x_1, x_2, ...
such that x_i + x_{i+1} is prime for all i > 0; let's call this a
"prime sequence".  It's easy to construct a "prime sequence". My
question: is there a "prime sequence" with an infinite number of
k such that x_1, x_2, ..., x_k is a permutation of 1, 2, ..., k?
If so, can you find one?

	In other words, I'm curious to see if there is a "prime
sequence" that uses up the whole numbers about as fast as the
sequence 1, 2, 3, ... does?

	I thought a little about using a greedy approach to construct
such a sequence.  Suppose we already have x_1, x_2, ..., x_j.  Then
pick the smallest unused number that sums with x_j to a prime, and let
that number be our x_{j+1}.  Assuming you take x_1=1, the resulting
sequence begins 1, 2, 3, 4, 7, 6, 5, 8, 9, 10.

	What we get is (obviously) a "prime sequence".  How fast
does it use up the whole numbers?  I don't know: but I did write a
C program to try to construct the first hundred thousand elements
of this greedy sequence, and the result does indeed contain many
prefixes which are permutations; this makes me think the greedy
approach may even solve my puzzle.  Any thoughts?

--------------------------------------------------------------------------------
David Wagner                                              [email-masked]