Problems & Puzzles: Puzzles

Puzzle 691 Conjectures related to Gilbreath's scheme The young Meisami Mahdi sent the following Conjectures closely related to the well known Gilbreath scheme & conjecture. (See 1 & our puzzle 274) For a function f from 1 to N define D(f)(n)=f(n+1)-f(n) as a derivative. For a list  {f(1),f(2),f(3),.....} of values of f define: D0(f):={f(1),f(2),f(3),.....}  D1(f):={D(f)(1),D(f)(2),D(f)(3),......}=D( {f(1),f(2),f(3),.....}  ) D2(f):={D(D1(f))(1),D(D2(f))(2),....}=D( {D(f)(1),D(f)(2),D(f)(3),......} ) and so on for Dk(f) for every k. As an example consider f(n)=3n+1 or {4,7,10,13,16,....}, D1(f)={3,3,3,3,3,3,....}. Another example  take g(n)=n^2 or {1,4,9,16,25,36,49,....} D1(g)={3,5,7,9,11,13,....} , D2(g)={2,2,2,2,2,2,2,....} Conjecture1: Let p(n) be prime number function, then there is not any k for which all elements of the set Dk(p) are equal. Conjecture 2: (a conjecture stronger  than conjecture1): There is a m such that for every k greater than m,Dk(p) does not have any two equal elements. Conjecture 3: For every natural number m there is a k such that m is an element of Dk(p). But if we change the definition of D(f)(n) and define a new derivative AD(f)(n)=|f(n+1)-f(n)|  (=Absolute value of D(f)(n)) like something we have in Gilbreath's conjecture (the first element of each ADk(p) is 1). Conjecture 4:There is a m such that for every k greater than m we have just 1,0,2 as elements of ADk(p). Q. Can you prove the conjectures by Mahdi or show a counterexample?

---

Contributions came from Jan van Delden & Emmanuel Vantieghem.

***

Jan wrote:

Conjecture 1: Consider g[] a polynomial with degree k. Then D[k]g[] is constant, i.e. D[k]g[l]=c for every l.
Or the other way around, if there exists a k such that D[k]g[] is constant (and D[m]g[] is not constant with g<k), we must have that g[] is a polynomial with degree k.

 

So the conjecture is equivalent to p[] is not a polynomial of degree k.

One can do a little better:

 

p[n] is integer, so all D[k]p[n] are integer by construction. So if D[k]p[n] is constant it is an integer. Reversing the process shows that we must have that p[] is a polynomial with rational coefficients.

The conjecture is equal to: p[] is not a polynomial with finite degree and rational coefficents.

This has been proved, in fact we have the stronger theorem by Legendre:
There is no rational algebraic function which always gives primes.

 

Conjecture 2: Clearly m>1, since there are a lot of twin primes. The conjecture states that the distribution of primes is highly irregular. I agree, but proving this in this form would be something.

 

[B.T.W.: See Yitang Zhang on a proof that there exists a number N<70*10^6 such that there are infinitely many primegaps equal to N.
There was an article in a Dutch Newspaper regarding his remarkable proof.]

 

Conjecture 3: A bold statement. And hard to prove or disprove.

 

Conjecture 4: I investigated M[N], where M is the first value of k for which AD[k]p[] is in {0,1,2}, with p[] restricted to [1,N]. So slightly different from m.

 

N  M[N]

1   0

5 2

11 3

18 4

19 5

31 9

35 10

70 11

110 13

112 15

190 16

193 17

194 18

195 19

196 20

312 23

764 24

899 27

901 35

2216 39

 

See Caldwell’s pages for a table of M[pi(10^k)], i.e. N=pi(10^k), k=2..13.

Curve fitting these values gives:   M=0.393*ln(N)^2.249 with R^2=0.998.

 

We see that M is a nondecreasing stepfunction of N. I see no reason why M (and thus m) is bounded above by a constant.

***

Emmmanuel wrote:

About conjecture 1 : it is true and easy to prove.  Indeed, one sees immediately that, for every  k > 0  the sequence  Dk(p)  has first element odd and all other elements even.  So, there is not any k for which all elements of the sequence are equal.

About conjecture 3 : I'm convinced that it is not true.  For instance, 15 is not an element of any  Dk(p)  for  k < 30000.  The first element of  Dk(p)  is the only odd number in  Dk(p)  and is very big (in absolute value) in comparison with  k .

About conjecture 4 : in the article of Wikipedia we read that Odlyzko figured out that  AD635(p)  has only  0, 1  and 2  among his first  3.4*10^11 elements.  I think that it will be very difficult to prove or disprove that ALL its elements are 0,1 or 2.  In my opinion the conjecture is not true.

It is clear that conjecture 4 implies the Gilbreath conjecture.  Indeed, if such an  m  exists then  Dk(p)  would look like 1, followed by a sequence of zeros and twos. And thus, the 1 in front would stay ad infinitum ...

 

***