Problems & Puzzles: Conjectures

Conjecture 29. The Frank Buss's  B(n) function

Frank Buss has defined a recursive function B(n) that - conjecturally - generates:

• only primes

• none of these twice

• all the primes

This is the Buss's recursive function:

• f(1)=1

• B(n)= nxtprime{f(n)+1)} - f(n)

• f(n)=f(n-1).B(n-1)

The first few members of the sequence are:

 n f(n) B(n) 1 1 2 2 2 3 3 6 5 4 30 7 5 210 13 6 ... 11 7 ... 17 8 ... 19 9 ... 23 10 ... 37 11 ... 73

My first comment to him was:

"...At the very first your sequence seems to be the same than the Fortune's Conjecture and the corresponding sequence described in A2, p. 7, UPiNT, by R.K.Guy.

While it's very similar in the structure, the particular initial conditions & the recursivity you impose, soon makes the difference, i.e.: In the Fortune's sequence the small prime 11 never appears, and in the Fortune's sequence the prime 61 is obtained twice very soon (in the steps 10 & 12)

So, this is an entirely new sequence..."

Question: Can you disapprove the Buss's Conjecture? that is to say:

a) find a composite B(n)
b) find one pair (n, m) such that B(n)=B(m) if n & m are distinct?
c) find a prime non-listed in the sequence B(n)

________
* See (EIS A067836,  A062894 )

Phil Carmody, Richard Pinch, Rudolph Knjzek, each one by his own, have shown that the question b) is impossible to get, by the very nature of the B(n) definition:

...It is fairly easy to see that any two members of the Buss sequence B(n) are coprime. Suppose that p is a prime factor of B(n) (I do not assume that B(n) is always prime) so that p also divides f(m) for all m > n. Consider any value of m > n, then p divides q - f(m) where q is the next prime larger than f(m)+1. But p | f(m) so q > f(m)+1 > p. Hence we cannot have p | q and so we cannot have p | B(m) = q - f(m). This implies in particular that the B(n) are all distinct...

***

Felice Russo wrote (3/1/02):

"...about the conjecture 29 I have tested it up to n=603. No composite number has been found. ( See attached file for the values of B(n)). The first primes that have not been generated up to n=603 are: 503, 677, 811, 911, 997, 1163, 1193, 1303, 1367, 1459, 1493, 1567 ....... Only for curiosity. The function B(n) tend in average to follow the curve: 2.1*n^1.22, ..."

So, the first follow-up question for this puzzle is find the n value such that B(n)=503

***

Robert Smith wrote (3/6/6):

I thought I would try to find 503 as part of this conjecture. I have taken n now on to 666, and of the listed gaps only 1163 is eliminated at n=610.

Regarding the conjecture that the series only includes primes, I could add the following:

Primorials are associated with large prime gaps, as no number in the range p#+2 to p#+p can be prime.

Let the largest value of B(n) to date be x. In the first 650n x=28559

f(n) is a deficient form of the primorial x#, being the product of distinct primes, but not necessarily all of them up to x.

Let's define the deficient factorial Q as x#/(product of the deficient primes (r* r*r..), where the r’s are the 1st, 2nd, 3rd smallest values of B(n) which have not been generated by the Buss function to date.

Only Q + any of the r or some multiple of r’s can be prime between Q+2 and Q+x. The smallest combination of r’s is r*r. Up to n=603, r*r=503*677=340531 is significantly greater than x.=28559.

Odd integer Q+s, larger than Q+p, can be prime, as long as s is not divisible by any of the primes in the B(n) series to date. The next prime after Q+2 will be defined by s= a prime not in the series B(n) to date, or by a multiple of the r’s . Again, the smallest non-prime s would be r*r.

The largest prime smaller than 340531 is 340519, which is the 29223rd prime. Only 603 primes are in B(n) series, therefore all of the 28620 values of Q+(one of the primes not in the B(n) series) must be composite, and Q+340531 must also be prime.

The chances of a non prime value is therefore negligible and will only become non negligible if either these low values of r and r persist for many, many iterations. However, negligible is not the same as zero. A string of 29223 composites might just be round the corner!

***

On December 15, 2014, Dana Jacobsen wrote:

I have calculated the first 3334 terms of OEIS A067836  (the B(n) of conjecture 29.  B(3289) = 503, B(3048) = 1193, B(2887) = 2027.  No composites (and no duplicates) to this point.  The largest value to this point is B(3249) = 145069.  The smallest values not present: 3659, 4243, 5581, 6217, 6323, 6529, 6833, 6961, 7129, 7219, 7243.

f(3289) is 13361 digits, and it takes about 1 minute to find B(3289) from f(3289) since this is a very small gap.  I used the Perl ntheory module for the calculations.  The next_prime function uses an ES BPSW test, but it wouldn't be hard to run more tests on the values.

I suppose I should update the OEIS b-files.

*** Records   |  Conjectures  |  Problems  |  Puzzles  Home | Melancholia | Problems & Puzzles | References | News | Personal Page | Puzzlers | Search | Bulletin Board | Chat | Random Link Copyright © 1999-2012 primepuzzles.net. All rights reserved.