Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Infinitely many primes in every row of array

  1. Mar 25, 2012 #1
    I asked this question on one another forum but didn't get any answer .

    Consider the following array of natural numbers :

    [tex]\begin{array}{ccccccccc}
    1 & 2 & 4 & 7 & 11 & 16 & 22 & 29 & \ldots \\
    3 & 5 & 8 & 12 & 17 & 23 & 30 & 38 & \ldots \\
    6 & 9 & 13 & 18 & 24 & 31 & 39 & 48 & \ldots \\
    10 & 14 & 19 & 25 & 32 & 40 & 49 & 59 & \ldots \\
    15 & 20 & 26 & 33 & 41 & 50 & 60 & 71 & \ldots \\
    21 & 27 & 34 & 42 & 51 & 61 & 72 & 84 & \ldots \\
    \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots &
    \end{array}[/tex]

    Question : Are there infinitely many primes in every row of this array ?

    My attempt :

    The nth term of the first row is given by :

    [tex]a_n=\frac{1}{2}(n^2-n+2)[/tex]

    [tex]\text{for}~ n=2k~\text {we have :} [/tex]
    [tex]a_{2k}=P(k)=2k^2-k+1[/tex]
    [tex]\text{and for}~ n=2k-1~\text{ we have :}[/tex]
    [tex]a_{2k-1}=Q(k)=2k^2-3k+2[/tex]

    Note that both P(k) and Q(k) are irreducible over integers .

    Also note that : [tex]\gcd(P(1),P(2),\ldots)=1 ~\text{and}~ \gcd(Q(1),Q(2),\ldots)=1[/tex]

    So, according to Bunyakowsky conjecture both P(k) and Q(k) generates for natural arguments infinitely many prime numbers . Therefore , if Bunyakowsky conjecture is true first row contains infinitely many primes . One can draw same conclusion for all other rows .

    Is my reasoning correct ? Is there some other approach to this problem ?
     
  2. jcsd
  3. Mar 25, 2012 #2
    This is an open problem, and as you correctly observe, it is a special case of a conjecture by Bunyakovsky (from 1857).
    Yes
    uhm... other than what? It is interesting to note that no quadratic polynomials (or higher degrees) over Z have been shown to generate an infinitude of primes.
     
  4. Mar 25, 2012 #3
    The two dimensional form of that formula is[tex]a_{m,n}=\frac{m^2 + n^2 + 2mn - m - 3n + 2}{2}.[/tex]A different way to approach this could be to try to prove[tex]\forall n \exists m : a_{m,n} \in P.[/tex]As opposed to the way you seem to be going about it, by proving[tex]\forall m \exists n : a_{m,n} \in P.[/tex]It would really only make the difference of changing which polynomial you're trying to prove to generate an infinitude of primes over Z. Either way, it would still require being the first to prove a polynomial can generate an infinitude of primes.
     
  5. Mar 25, 2012 #4
    can you please show how you derived the 2-D formula. I am working with a similar problem where I know both formulas but cannot combine them into two. Thanks
     
  6. Mar 25, 2012 #5
    It wasn't too advanced, more of a hack actually. I used Wolfram|Alpha to find the generating polynomial of each row, which were all of the form [tex]m^2 + Am + B.[/tex]

    A was -1, 1, 3, 5, ... and B was 2, 4, 8, 14, ...

    I just used Wolfram|Alpha again to find the generating functions for A and B which where A(n)=2n-3 and B(n)=n^2-n+2. I plugged those in for A and B.

    Something interesting I noticed is that B is the function for the first row of the matrix, but with row as input rather than column. This suggests that the matrix could (relatively) easily be extended to more dimensions. For example, [tex]a_{x,y,z}=\frac{x^2 + x(2y-3) + y^2 + y(2z-3) + z^2}{2}.[/tex]

    I haven't actually looked at that (mainly because I'm too lazy), so I don't know for sure if it's actually a 3d generalization, but I think it works...
     
  7. Mar 26, 2012 #6
    In the first colomn we have the triangular numbers, m(m+1)/2. Then observe that in row m, to get the number in the next colomn, you have to add m, then you have to add m+1, m+2, and so on. So in row m, colomn n, adding m(n-1) to the formula takes care of the +m parts, and adding (n-1)(n-2)/2, the triangular number 1+2+...+n-2, will complete the formula. So the element in row m, colomn n can be written m(m-1)/2 + (n-1)(n-2)/2 + mn.

    There are many ways to generalize, but if you want to place all the positive integers in a 3-dimensional array, in a similar way, you will get the tetrahedal numbers n(n+1)(n+2)/6 (= 1,4,10,20,35,...) along one of the edges, and I assume the general formula will be a cubic polynomial.
     
  8. Mar 26, 2012 #7
    As a possible explanation of why there may be only a finite number of primes in a given row, I haved previously determined that each term [tex]a_{m,n}[/tex] generates 2*G infinite series where G is the number of ways the value [tex]a_{m,n}[/tex] can be expressed as a product of two factors A,B. Such series being [tex]S_{1} = A, S_{2} = B, S_{n} = 6*S_{n-1} - S_{n-2} + (A+B - 2m - 2n + 3)[/tex]. within the parentheses, A and B can be each positive or each negative. These series have the property that the product of any two adjacent terms is an element of row m. With so many elements of row m being determined to be a product by infinite series in the order of twice the number of factors of all prior terms, there seems that eventually there would be little chance for prime elements.
     
    Last edited: Mar 27, 2012
  9. Mar 27, 2012 #8
    Sorry but the recursive formula is;
    [tex]S_{n} = 6*S_{n-1} - S_{n-2} + 2*(A+B-2m -2n +3)[/tex] .
    I forgot the multiplication by 2 part. Also, although A and B can be either both positive or both negative, this must be consistent through out.
    Example, for [tex]a_{1,3}[/tex]
    S = {2,2,8,...} or {-2,-2,-28, ...} or {1,4,23,...} or {-1,-4,-43...} or {-4,-1, -22,...} or {4,1,2,...}
     
    Last edited: Mar 27, 2012
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Infinitely many primes in every row of array
  1. Infinite primes? (Replies: 8)

  2. Infinite primes proof? (Replies: 2)

Loading...