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