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

Relate Mersenne Primes To Sq Triangular Nos.

  1. May 16, 2006 #1
    Conjecture, For p>2, the [tex]2^(p-1)[/tex] th square triangular number is divisible by [tex]M_{p}[/tex] if and only if [tex]M_{p}[/tex] is prime. I checked this for 2<p<27. For instance the first four square triangular numbers are 0,1,36 and 1225 and the fourth is divisible by .
    PS In fact it appears that if is prime then for any starting integers [tex]S_{1}[/tex] and [tex]S_2[/tex] having the recursive relation ,
    [tex]S_{n} = 6*S_{n-1} - S_{n-2}[/tex] the following congruence holds:
    [tex]S_{2^{p-1}} = S_{1} \mod M_{p}. There is prize money lurking here for those who are interested.

    _________________
    Have a useful day
     
  2. jcsd
  3. May 16, 2006 #2

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    Fancy explaining that a bit more clearly, like what you mean by a square triangular number?
     
  4. May 17, 2006 #3
    Looks like he means numbers that are simultaneously square numbers and triangular numbers. E.g. 36 = 6x6 = 1+2+3+4+5+6+7+8
     
  5. May 17, 2006 #4
    The recursive relation for square triangular numbers is known to be [tex]S_0 = 0, S_1 = 1, S_{n} = 6*S_{n-1} - S_{n-2}[/tex]
    [tex]T(m) = m(m+1)/2 = S_{n}*S_{n}[/tex]

    Thus my conjecture about square triangular numbers is just a special case of my more general conjecture which is that for the same type of series with any two starting integers that if [tex]M_{p}[/tex] is a prime Mersenne number then [tex]S_{(1+i)} = S_{(2^{p-1}+i)} \mod M_{p}[/tex]. With [tex]S_{1} = 0, M_{p} = \mbox{prime}[/tex] then [tex]M_{p} \mid S_{2^{p-1}}[/tex] for any integer S_2.
     
    Last edited: May 17, 2006
  6. May 17, 2006 #5
    The recursive relation for square triangular numbers is known to be [tex]S_0 = 0, S_1 = 1, S_{n} = 6*S_{n-1} - S_{n-2}[/tex]
    [tex]T(m) = m(m+1)/2 = S_{n}*S_{n}[/tex]

    Thus my conjecture about square triangular numbers is just a special case of my more gemeral conjecture which is that for the same type of series with any two starting integers that if [tex]M_{p}=2^{p} - 1[/tex] is a prime Mersenne number then [tex]S_{(1+i)} = S_{(2^{p-1}+i)} \mod M_{p}[/tex]. With [tex]S_{1} = 0, M_{p} = \mbox{prime}[/tex] then [tex]M_{p} \mid S_{2^{p-1}}[/tex] for any integer S_2.
     
  7. May 18, 2006 #6
    After more consideration, I realized that it is not necessary to store more than one term and that my test can be refined so that there are only p-1 terms that need to be calculated.

    Input p
    M(p) = 2^p -1
    S_0 = 1
    C = p
    Do
    S_0 = (4*S_0)*(8*S_0 + 1) Mod M(p)
    C = C - 1
    Loop until C = 1
    If S_0 = 1 Then
    Print "M(" & p & ") is prime"
    Else
    Print "M(" & p & ") is not prime"
    End If.

    Although this test involves more steps, it basically involves almost the same complexity as the Lucus-Lehmer Test since the additional steps are register shifts and the addition of 1
    It is based upon the fact that 1 is the 2nd square triangular number and that The S_0's follow the sequence ST(2),ST(3),ST(5),ST(9),ST(17).... i.e. ST(2^n+1) in the sequence of square triangular numbers (modulus M(p) of course). I checked the test for p = 3 to 28. It doesn't work for p = 2 since 3 is a factor of 6.

    Any comments?
     
  8. May 28, 2006 #7
    I managed to write a basic program using true/false arrays with binary like addition subtraction and multiplication that checked all Mersenne numbers, [tex]2^{p} -1 \mid p = \mb{prime}[/tex] for primes from p = 3 up through p = 929 base upon the relation between Mersenne Primes and Square Triangular Numbers. I designed it to do primes up to p= 4999 without modification, but it takes something in the order of a 8 hour day to check up through p=929. I am not sure since I upgraded my program after the first 82 primes and it did the next 82 primes in about the same time, so I am only estimating that it would have taken less than 1/4 the time to check the first 82 primes.

    My conjecture in the preceeding post still holds with the lone exception being 2^2 - 1 which I dont think affects my conjecture since 3 is a special case related to the recursive sequence S_n = 6*S_(n-1) - S_(n-2) for square triangular numbers.

    It probably would be fruitless to explore my conjecture further in this mannor. A better approach is to find a proof. Any takers or suggestions.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Relate Mersenne Primes To Sq Triangular Nos.
  1. Mersenne prime (Replies: 1)

  2. Large Mersenne primes (Replies: 3)

Loading...