The Unofficial Macro Scheduler Puzzler #14

Anything Really. Just keep it clean!

Moderators: Dorian (MJT support), JRL

Post Reply
User avatar
JRL
Automation Wizard
Posts: 3467
Joined: Mon Jan 10, 2005 6:22 pm
Location: Iowa

The Unofficial Macro Scheduler Puzzler #14

Post by JRL » Fri Oct 07, 2022 9:51 pm

I just did a forum search and found zero references to this topic. It is an otherwise very well covered subject that I've personally never had much interest in. Almost everybody has heard of it and almost no one knows what its good for. I'm talking about prime numbers.

For puzzler #14 we wonder how best to generate a list of the first 10,000 prime numbers. By generate I mean create the list using a Macro Scheduler script that performs mathematical wizardry rather than a script that pulls the data from one of the (literally) one Billion web pages that Google finds if you search for "prime number list".

I have a script that takes about 20 minutes to generate the list. For reference the first prime number is "2" and according to my calculations, the ten thousandth prime number is "104,729". I'm using the brute force method I was taught in Junior High School roughly 57 years ago. Oddly, for something I've never used I recalled the method well enough to create an accurate list.

For general interest, the largest prime number has 24,862,048 digits. Lets not calculate that one.

Another point of general interest, this is the first puzzler in 7 years that has a real answer. We hope it has more than one answer. Unfortunately it will be the 6th puzzler for which I have no points to bestow upon the winner. Only my genuine respect and admiration. The winner, assuming there will be entrants, will be selected by our panel of judge from the scripts provided by said entrants.

If there are no worthy entries by the end of this month, The panel of judge will declare me to be the winner and I will post my magnificent winning script. Nobody wants that to happen.

hagchr
Automation Wizard
Posts: 317
Joined: Mon Jul 05, 2010 7:53 am
Location: Stockholm, Sweden

Re: The Unofficial Macro Scheduler Puzzler #14

Post by hagchr » Mon Oct 10, 2022 4:20 pm

Hi, here is my attempt... On my machine it runs in around 6-7 min. Let's see if it matches your numbers and then interesting to see what other people come up with. The SRT at the end is just there to join the array elements into a string.

Code: Select all

Timer>start
Let>max=104729

Let>ctPrimes=0
ArrayDim>Primes,ctPrimes

Let>i=1
While>i<=max
  Add>i,1

  Assigned>Sieve_%i%,isSieveAssigned

  If>isSieveAssigned=FALSE
    Add>ctPrimes,1
    ArrayDim>Primes,ctPrimes
    Let>Primes_%ctPrimes%=i

    Let>j={%i%*2 - %i%}
    While>j<=max
      Add>j,i
        Let>Sieve_%j%=TRUE
    EndWhile
  EndIf

EndWhile

// Join array elements in "Primes" to string "resPrimes"
GoSub>Join,"Primes",%CRLF%,0,"resPrimes"

Timer>end
Let>time={(%end%-%start%)/60000}
Let>time={(Round(%time%*100)/100)}

MDL>Time: %time% min%CRLF%=====%CRLF%%resPrimes%

//SRT Join,"Array Name",delimiter,ending delimiter 0/1,"Result Variable Name"
SRT>Join
    //Get the Array name w/o "" into Join_Arr_1
    RegEx>(?<=^").+(?="$),%Join_Var_1%,0,Join_Arr,Join_N,0
    ArrayCount>Join_Arr_1,Join_Arr_Count

    Let>Join_delimiter=%Join_Var_2%

    Let>Join_Res=
    Let>Join_ct=0
    While>Join_ct<Join_Arr_Count
        Let>Join_ct=%Join_ct%+1
        Let>Join_tmp=%Join_Arr_1%_%Join_ct%
        Let>Join_Res=%Join_Res%%Join_tmp%%Join_delimiter%
    EndWhile
    If>Join_Var_3=0
        RegEx>%Join_delimiter%(?=$),Join_Res,0,Matches,NumMatches,1,,Join_Res
    Endif

    //Get the Result Variable name w/o "" into Join_ResOut_1
    RegEx>(?<=^").+(?="$),%Join_var_4%,0,Join_ResOut,N,0

    Let>%Join_ResOut_1%=%Join_Res%
END>Join

User avatar
JRL
Automation Wizard
Posts: 3467
Joined: Mon Jan 10, 2005 6:22 pm
Location: Iowa

Re: The Unofficial Macro Scheduler Puzzler #14

Post by JRL » Wed Oct 12, 2022 2:35 pm

hagchr,
Thanks for playing.
I like your concept. The only downside I see is that the request was for the first 10,000 prime numbers and you instead used the ten thousandth prime number as your limiter. Not difficult when the value is provided to you but when the request comes in for the first 1,000,000 prime numbers, you'll have to look up the numbers and figure it out. May not be as easy as it sounds.

On my computer which is an 8 year old i5-4590 with 8 Gb RAM, your script successfully provides all the prime numbers between 1 and 104730 in about 4 minutes and 30 seconds. I took liberties with your script and posted an amended version below. On my computer it successfully completes in 45 seconds.

It seemed to me you only needed one list. I made your sieve list an official array and removed the primes array. The sieve array contains an empty value for each prime number so used that info to generate the list.

As I said, I like your concept.

Code: Select all

Timer>start
Let>max=104729
ArrayDim>Sieve,max
Let>i=1
While>i<=max
  Add>i,1
  If>Sieve_%i%=
    Let>j=i
    While>j<=max
      Add>j,i
        Let>Sieve_%j%=TRUE
    EndWhile
  EndIf
EndWhile
// Join prime array elements to string "resPrimes"
Let>resPrimes=
Let>kk=0
While>%kk%<=%max%
  Add>kk,1
  Let>value=Sieve_%kk%
  If>value=
    Let>resPrimes=%resPrimes%%crlf%%kk%
  EndIf
EndWhile

Timer>end
Let>time={(%end%-%start%)/60000}
Let>time={(Round(%time%*100)/100)}

MDL>Time: %time% min%CRLF%=====%resPrimes%

hagchr
Automation Wizard
Posts: 317
Joined: Mon Jul 05, 2010 7:53 am
Location: Stockholm, Sweden

Re: The Unofficial Macro Scheduler Puzzler #14

Post by hagchr » Thu Oct 13, 2022 6:53 pm

Hi, I agree it is not optimal if you do not know the future primes you are looking for. However, there is a way to estimate how many numbers you need in order to get n prime numbers:

g(n) = nlog(n) + nlog(log(n)), where log is the natural logaritm and n the number of primes you want.

It is a slight overestimation so it should cover the numbers you are looking for.

I adjusted your version so it now asks for how many prime numbers you want, then (slightly over)estimates how many numbers to check and executes. The puzzler question of 10,000 primes took around 1 min. For 100,000 primes, my old pc it needed around 1/2h. The pc did not like the proposition of 1,000,000 - it run out of memory after a while. (I also adjusted so the primes start with 2,3, ... and not 1 as in the latest version).

It will be interesting to see alternative solutions. Can you solve it without looking through the history in each iteration or as in this version "looking through" the whole "future"?

Code: Select all

// Enter number of primes to generate
Label>start
Input>totPrimes,Enter number of primes (>5):,

If>totPrimes=
  Exit,r
EndIf


If>totPrimes<6
  Goto>start
EndIf

// Estimate number of numbers to check G(n) = n(log(n)+log(log(n)), where log is natural log
Let>tmp1={Ln(%totPrimes%)}
Let>max={Int(%totPrimes%*(%tmp1%+Ln(%tmp1%)))}

Timer>start
ArrayDim>Sieve,max
Let>i=1
While>i<=max
  Add>i,1
  If>Sieve_%i%=
    Let>j=i
    While>j<=max
      Add>j,i
        Let>Sieve_%j%=TRUE
    EndWhile
  EndIf
EndWhile

// Join prime array elements to string "resPrimes"
Let>resPrimes=
Let>kk=0
Let>ctPrimes=0
While>%kk%<=%max%
  Add>kk,1
  Let>value=Sieve_%kk%
  If>value=
    Let>resPrimes=%resPrimes%%crlf%%kk%
    Add>ctPrimes,1
    
    // Stop when requested number of primes reached
    If>ctPrimes={(%totPrimes%)+1}
      Goto>end
    EndIf
  EndIf
EndWhile

Label>end

// Clean off starting 1
RegEx>(?m-s)^1$\R,resPrimes,0,m,nm,1,,resPrimes

// Find the last prime number and compare with estimate
RegEx>(?m-s)^\d+$\Z,resPrimes,0,m,nm,0
Let>lastPrime=m_1
Let>difference={Round((%max%/%lastPrime%-1)*1000)/10}

Timer>end
Let>time={(%end%-%start%)/60000}
Let>time={(Round(%time%*100)/100)}
MDL>Estimated Number: %max%%CRLF%Actual Number: %lastPrime%%CRLF%Difference: %difference%%%CRLF%%CRLF%Time: %time% min%CRLF%=====%resPrimes%

User avatar
JRL
Automation Wizard
Posts: 3467
Joined: Mon Jan 10, 2005 6:22 pm
Location: Iowa

Re: The Unofficial Macro Scheduler Puzzler #14

Post by JRL » Fri Oct 14, 2022 9:26 pm

@hagchr,
I've not yet examined your latest offering. Hopefully get to it before Monday.

@The World
Here is what I started with. It is as I was taught when these were done longhand using paper and pencil. I believe prime number discovery was an excuse to have a reason to learn how to decipher square roots. The script actually starts at 3 because 2 is an even number and starting there means I either have to prove 2 to be a prime and three to be a prime or I have to check every number rather than every odd number. Shorter code to just say we know they are primes and start with them on the list.
hagchr wrote:It will be interesting to see alternative solutions. Can you solve it without looking through the history in each iteration or as in this version "looking through" the whole "future"?
I agree. It would be interesting to know if there is a math magic formula for discovering prime numbers.

This script "looks through history". It saves a list of prime numbers then checks each upcoming number by dividing it by all the previous prime numbers to see if one of the previous primes is an even divisor. If, after checking all the previous prime numbers, the number is not divisible by any of them without a remainder, the number is prime, and added to the list.

The process is shortened considerably if you first acquire the square root of the number being tested. There is no point in dividing a number by any prime number greater than its square root. You would be testing all the numbers that would have been the answer to a previous division. Waste of time.

Code: Select all

Let>NumberOfPrimes=10000
Let>Msg_Width=300
Message>Looking for the first %NumberOfPrimes% prime numbers:%crlf%%crlf%Please Wait...

//We know these two are prime and it saves a lot of code
//The place them in the list ahead of time.
Let>vPrimeList=2%crlf%3%crlf%
Let>kk=3
Let>vIntCount=2
While>%vIntCount%<NumberOfPrimes
  Add>kk,2
  Separate>vPrimeList,crlf,vInt
  //Sub>VInt_Count,1
  Let>pp=1
  Repeat>pp
    Add>pp,1
    Let>value=vInt_%pp%
    If>%pp%<>%vInt_Count%
      Let>vAns={%kk% mod %value%}
    EndIf
    If>%vAns%=0
      Let>pp=done
    Else
      //If>%pp%=%vInt_Count%
      If>{%value%>(sqrt(%kk%))}
        Let>vPrimeList=%vPrimeList%%kk%%crlf%
        Let>vLastPrime=kk
        Let>pp=done
      EndIf
    EndIf
  Until>pp=done
  Let>vIntCount={%vInt_Count%-1}
  Timer>now
  Let>now={%now%/1000}
  //Enabling the next line gives a readout but takes about 10% longer to run.
  SetControlText>Macro Scheduler Message,TMemo,1,Testing %kk%%crlf%Last Found %vLastPrime%%crlf%Total Found %vIntCount%%crlf%Elapsed seconds %now%
EndWhile

MDL>%now% Seconds%crlf%%crlf%%vPrimeList%

User avatar
JRL
Automation Wizard
Posts: 3467
Joined: Mon Jan 10, 2005 6:22 pm
Location: Iowa

Re: The Unofficial Macro Scheduler Puzzler #14

Post by JRL » Tue Nov 01, 2022 9:37 pm

Somebody wrote:I believe prime number discovery was an excuse to have a reason to learn how to decipher square roots.
Or was that square root deciphering was a reason to have a book full of prime numbers?

Here we are at the end of October or more precisely the start of November. Its time to announce the "winner" of this well thought out puzzler. This puzzler's accolades go to the only forumite willing to take the time to make and present a prime number generating script. And it is a fine example of prime number generation I might add. Short, fast and accurate. Qualities to which we all aspire.

hagchr!!!

Hopefully, somebody, will at some time in the future, happen across this series of posts and find a use for the script hagchr has presented. And just as important I hope hagchr learned something during his quest. I know I did.

Well done hagchr!!! Thank you once again for your participation!

Post Reply
cron
Sign up to our newsletter for free automation tips, tricks & discounts