Prime numbers problem

[Mithrandir]

Hi, I wrote a script to solve a discrete maths problem: Is it true that P₁ * P₂* ... * P_n + 1 -where P_i i= 1..n is the i-th prime number ie P₁=2, P₂=3, P₃=5 and so on- is always a prime number?

A teacher suggested it isn't true so I made this script to find the first one which is not prime:

expandcollapse popup

#include <Array.au3>

Global $arrayprimos[4] = [3, 2, 3, 5], $n ;note that arrayprimos is an array where the first cell counts the number of elements stored in it

Func _RFLTA_AddToList(ByRef $asList, $sValue)
    ;Credits to Melba23 :)
    ; Increase list count
    $asList[0] += 1
    ; Double list size if too small (fewer ReDim needed)
    If UBound($asList) <= $asList[0] Then ReDim $asList[UBound($asList) * 2]
    ; Add value
    $asList[$asList[0]] = $sValue

EndFunc   ;==>_RFLTA_AddToList

Func _EsPrimo(ByRef $array, $numero)
    ;function that receives an array by reference and returns whether $numero is a prime number
    Local $i = 1, $alreadythere = False
    If $numero < 2 Then;1 is not considered a prime number
        Return False
    Else
        While $i < UBound($array) And Not $alreadythere
            If $numero = $array[$i] Then
                $alreadythere = True;check that it isn't a prime already in the array
            ElseIf $array[$i] <> "" And Mod($numero, $array[$i]) = 0 Then
                Return False
            EndIf
            $i += 1
        WEnd
        Return True
    EndIf
EndFunc   ;==>_EsPrimo

$n = 1;variable to to keep count of the product of n primes
For $j = 1 To $arrayprimos[0];I inicialize the value of n
    $n = $n * $arrayprimos[$j]
Next

_ArrayDisplay($arrayprimos)
MsgBox(0, "$n", $n)

$num = $arrayprimos[$arrayprimos[0]] + 1;I inicialize the value of num in 1 more than the last prime of the array
$m = $num - 1;I inicialize m with a prime value to enter the while

While _EsPrimo($arrayprimos, $m);I loop until I find the first $m that is not a prime

    While Not _EsPrimo($arrayprimos, $num) And $num <> $arrayprimos[$arrayprimos[0]];search for the next prime to add to the array
        $num = $num + 1
    WEnd
    If $num > $arrayprimos[$arrayprimos[0]] Then
        _RFLTA_AddToList($arrayprimos, $num)
    EndIf

    $n = $n * $arrayprimos[$arrayprimos[0]];update the value of $n (n= p1 * p2 * ... * pn)
    $m = $n + 1; update the value of $m to evaluate it in the while (m= p1 * p2 * ... *pn + 1)
    MsgBox(0, "$n = ", $n)
    MsgBox(0, "$m = ", $m)
    MsgBox(0, "$num = ", $num)
    _ArrayDisplay($arrayprimos)
    $num += 1

WEnd

_ArrayDisplay($arrayprimos)
MsgBox(0, "The first m that is not a prime is: ", $m)
$handle = FileOpen(@ScriptDir & "\m.txt", 2)
FileWrite($handle, $m)

However, it goes up to the prime number 53 and it returns as m the number -4304329670229058501 which I guess it's because it has gone over the max range. Or is there another thing wrong? How can I solve this? Thanks for your help!!

Edited April 13, 2011 by Mithrandir

[UEZ]

The number exceeds the int32 range. 0x00000000 until 0x7FFFFFFF are positive values and from 0x80000000 until 0xFFFFFFFF are the negative ones.

You can use strings instead of numbers, e.g. $arrayprimos[4] = ["3", "2", "3", "5"].

Maybe you can play with structs to create int64 values...

Br,

UEZ

[jchd]

There is a bug somewhere in your code (not much time to dig into it) as it's well known there are early gaps in this sequence.

The sequence of product of prime(first N primes + 1) is called the Primorial primes. More information on it here (OEIS is the bible when it comes to integral sequences).

To come back to your question "find first rejection off Primorial primes", you don't have to use large integers to compute it:

Mathematica easy to understand example code:

In[1]:=
<< NumberTheory`NumberTheoryFunctions`
For [
    n = 2; p = 1; l = {},
    PrimeQ[n p + 1],
    n = NextPrime[n],
    l = Join[l, {{n, n p + 1}}]; p = n p;
    ];
l
{n, n p + 1, FactorInteger[n p + 1]}
Out[3]=
{{2, 3}, {3, 7}, {5, 31}, {7, 211}, {11, 2311}}
Out[4]=
{13, 30031, {{59, 1}, {509, 1}}}

shows that the prime your want is 13. 2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 = 59 * 509

[MvGulik]

To bypass the int64 limit you could try:

and/or

BigInteger UDF (autoit.de)

[Mithrandir]

Thanks to everyone! The udfs to work with large integers may be useful in the future.

There is a bug somewhere in your code (not much time to dig into it) as it's well known there are early gaps in this sequence.

The sequence of product of prime(first N primes + 1) is called the Primorial primes. More information on it here (OEIS is the bible when it comes to integral sequences).

To come back to your question "find first rejection off Primorial primes", you don't have to use large integers to compute it:

Mathematica easy to understand example code:

In[1]:=
<< NumberTheory`NumberTheoryFunctions`
For [
    n = 2; p = 1; l = {},
    PrimeQ[n p + 1],
    n = NextPrime[n],
    l = Join[l, {{n, n p + 1}}]; p = n p;
    ];
l
{n, n p + 1, FactorInteger[n p + 1]}
Out[3]=
{{2, 3}, {3, 7}, {5, 31}, {7, 211}, {11, 2311}}
Out[4]=
{13, 30031, {{59, 1}, {509, 1}}}

shows that the prime your want is 13. 2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 = 59 * 509

Thanks for that resource and also for pointing me in the right direction, I think I realise where is the error in my code, I will update the post with the code fixed this weekend.