Xref: princeton rec.puzzles:17254 sci.math:32923
Newsgroups: rec.puzzles,sci.math
Path: princeton!phoenix.Princeton.EDU!dawagner
From: dawagner@phoenix.Princeton.EDU (David A. Wagner)
Subject: Prime sequences
Message-ID: <1993May16.184914.17053@Princeton.EDU>
Originator: news@nimaster
Sender: news@Princeton.EDU (USENET News System)
Nntp-Posting-Host: phoenix.princeton.edu
Organization: Princeton University
Date: Sun, 16 May 1993 18:49:14 GMT
Lines: 30

	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                                              dawagner@princeton.edu