Problems & Puzzles: Problems

Problem 42 . Floor Exponent Prime Sequences

David Terr kindly sent the following problem to our pages:

We define a floor exponent prime sequence (FEPS) to be a sequence of primes of the form {p1, p2, ... , pr}, where pi = Floor{ti} for some t>2. For example, for t=1287/545, we get the sequence {2, 5, 13, 31, 73, 173, 409, 967} (see Crandall and Pomerance, "Prime Numbers, a Computational Perspective" (2000), exercise 1.75, p.69). Crandall and Pomerance ask whether any longer such sequences exist, whether such a sequence can be infinite, and whether an infinite number of such sequences of length 3 exist. In 1989, A. Balog showed that there are infinitely many such sequences of length 2.

Recently I began to study this problem. After a few days, I discovered a rather simple mechanical procedure for generating all FEPS with base t up to a given bound. Let FEPS(t) denote the floor exponent prime sequence with base t and let EFEPS(t) denote the sequence augmented by one (composite) element. Thus, FEPS(2) = {2} and EFEPS(2) = {2,4}. We proceed as follows: Call a base t a boundary value if t is FEPS(t1) is different from FEPS(t) for all t1<t. Suppose t1 is a boundary value. Given a FEPS(t1) = {p1, p2, ..., pr, p(r+1)} where pi = Floor(ti) is prime for 1<=i<=r and composite for r+1, compute the next boundary value t2 by computing the minimum of (p_i+1)1/i and NextPrime(p_(r+1))(1/(r+1)). For example, when t1=2, we have EFEPS(t1)={2,4}, so t2 = min(3,sqrt(5)) = sqrt(5) and FEPS(sqrt(5))={2,5,11} is the next FEPS and EFEPS(sqrt(5))={2,5,11,25}. (We get 11 for free here since 11 < t23 = 5^(3/2)). We may continue in this way to get all FEPS(t) in this way with t up to some bound X. I did so during the past few days and was rather surprised by the results! It didn't take long to discover the first FEPS of length 9, namely FEPS(3450844193(1/9))={11,131,1511,17341, 198997, 2283583, 26205133, 300715537, 3450844193} (Sloan's sequence A076255) and the first of length 10, namely FEPS(39661481813(1/10))={11,131,1511,17351,199151,2285711,26233621,301089179,3455668247,39661481813}

(Sloan's sequence A076357). Shortly thereafter I discovered thousands more, most of them as long or longer than these! Thus far, the longest such sequence I've found is:

FEPS(245092494303867872316927840433058150121090972563187226252192162731242781828213\
525601390456874200763428926486556401229467984897295568912536209575405704779365\
881331794192534581134284391993662578240712109237575614929981232768530259462270\
2807975786215971789524086870912809903356207088970031733058733884867
(1/100)),

which has length 100.

Based on numerical analysis of the FEPS I've produced so far, I propose the following conjectures:

1. For a fixed positive integer k, let πk(x) denote the number of FEPS with base t<=x. Then πk(x) is asymptotic to 1/k! (x/log(x))k as x approaches infinity. Note that for k=1, this reduces to the prime number theorem.

2. There are infinitely many FEPS of length k for all k>1.

3. There are no infinite FEPS.

4. Let Π(x) denote the total number of FEPS with t<x. Then log(Π(x)) is asymptotic to x/log(x) as x approaches infinity.

5. For fixed x, the distribution of lengths of FEPS is asymptotically Poissonian with mean x/log(x) as x approaches infinity. See the puzzle 227.

*** Records   |  Conjectures  |  Problems  |  Puzzles 