Sign in to follow this  
Followers 0
Mithrandir

Prime numbers problem

5 posts in this topic

#1 ·  Posted (edited)

Hi, I wrote a script to solve a discrete maths problem: Is it true that P1 * P2* ... * Pn + 1 -where Pi i= 1..n is the i-th prime number ie P1=2, P2=3, P3=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:

#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 by Mithrandir

Share this post


Link to post
Share on other sites



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


Please don't send me any personal message and ask for support! I will not reply!

Selection of finest graphical examples at Codepen.io

The own fart smells best!
Her 'sikim hıyar' diyene bir avuç tuz alıp koşma!
¯\_(ツ)_/¯  ٩(●̮̮̃•̃)۶ ٩(-̮̮̃-̃)۶ૐ

Share this post


Link to post
Share on other sites

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


This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites

To bypass the int64 limit you could try:

and/or

BigInteger UDF (autoit.de)


"Straight_and_Crooked_Thinking" : A "classic guide to ferreting out untruths, half-truths, and other distortions of facts in political and social discussions."
"The Secrets of Quantum Physics" : New and excellent 2 part documentary on Quantum Physics by Jim Al-Khalili. (Dec 2014)

"Believing what you know ain't so" ...

Knock Knock ...
 

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0