RPL exercise  Last Digits of Primes (HP 49G, G+, 50g)

06012019, 03:07 AM
(This post was last modified: 06012019 03:11 AM by Gerson W. Barbosa.)
Post: #1




RPL exercise  Last Digits of Primes (HP 49G, G+, 50g)
Here are the first forty prime numbers greater than 5:
{ 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 } How many of them end with 1, 3, 7 and 9? Since these tend to be distributed evenly among the sample, we would expect finding about ten of each one. Indeed, upon careful counting we find 10, 10, 11 and 9, respectively. Write a UserRPL program that given the number of the first prime numbers greater than 5 returns a list containing the number of occurrences, in order. For example, 40 > {10 10 11 9} 120 > {29 31 32 28} What is the result for 1000? Optionally, write a program that does the same for primes greater than 2 in base 8. In this case, the last digits are 1, 3, 5 and 7. 40 > {7 12 11 10} 120 > {27 33 30 30} 1000 > ? Optimize programs for speed. Currently less than 160 seconds for 1000 primes (both programs, real HP 50g), but probably still not optimal. Have fun! 

06012019, 04:13 AM
Post: #2




RE: RPL exercise  Last Digits of Primes (HP 49G, G+, 50g)
.
Hi, Gerson, (06012019 03:07 AM)Gerson W. Barbosa Wrote: Currently less than 160 seconds for 1000 primes (both programs, real HP 50g), but probably still not optimal. Really ? 160 sec. (almost 3 min.) for just 1000 primes ? Only 6 primes/sec ? Seems I had the wrong idea about these calcs' speed ... Regards. V. . 

06012019, 04:43 AM
(This post was last modified: 06012019 04:47 AM by Gerson W. Barbosa.)
Post: #3




RE: RPL exercise  Last Digits of Primes (HP 49G, G+, 50g)
(06012019 04:13 AM)Valentin Albillo Wrote: . Yes, 155.4 seconds (base 10), or 155.4 ms per prime, but that’s not linear. For 100 primes it takes 7.38 seconds or about 13.5 primes per second. Anyway, that’s an improvement over my first attempt. Hopefully there’s still a better way. For these primes calculations, perhaps the Prime is more suitable, but I am not willing to try it. Best regards, Gerson. 

06012019, 05:02 AM
Post: #4




RE: RPL exercise  Last Digits of Primes (HP 49G, G+, 50g)
(06012019 04:43 AM)Gerson W. Barbosa Wrote: Yes, 155.4 seconds (base 10), or 155.4 ms per prime, but that’s not linear. For 100 primes it takes 7.38 seconds or about 13.5 primes per second. Anyway, that’s an improvement over my first attempt. Hopefully there’s still a better way. Here's a fairly bruteforce method: Code: \<< The result for an input of 1000. is { 245. 253. 256. 246. }, and on my 50g takes about 41s to complete. Note that I'm using approximate numbers here instead of exact to shorten the time a bit. 

06012019, 05:29 AM
(This post was last modified: 06012019 06:03 AM by Gilles.)
Post: #5




RE: RPL exercise  Last Digits of Primes (HP 49G, G+, 50g)
(06012019 05:02 AM)DavidM Wrote: The result for an input of 1000. is { 245. 253. 256. 246. }, and on my 50g takes about 41s to complete. Note that I'm using approximate numbers here instead of exact to shorten the time a bit. Hi David, with exactly the same program (without the R>I, not needed in newRPL) it takes in 0.51 sec to complete in newRPL on my H50g hdw for 10'000, I get { 2485 2515 2500 2492 } in 0.97sec for 100'000, I get { 24968 25008 25015 25000 } in 80.11 sec (and 0.76s on the simulator) 

06012019, 05:44 AM
Post: #6




RE: RPL exercise  Last Digits of Primes (HP 49G, G+, 50g)
(06012019 05:02 AM)DavidM Wrote:(06012019 04:43 AM)Gerson W. Barbosa Wrote: Yes, 155.4 seconds (base 10), or 155.4 ms per prime, but that’s not linear. For 100 primes it takes 7.38 seconds or about 13.5 primes per second. Anyway, that’s an improvement over my first attempt. Hopefully there’s still a better way. Very nice! 53.3 seconds even using exact numbers. '155.4/41' = 3.79, this ratio used to be about 10 (that is, my programs used to take 10 times as much, compared to the optimal ones by Valentin and others). I’ve used a somewhat unorthodox method which surely doesn’t obey the “KISS” rule. Also, my program is about 50% longer. 

06012019, 08:51 AM
Post: #7




RE: RPL exercise  Last Digits of Primes (HP 49G, G+, 50g)
Hi Everyone.
Here's my take on the challenge. The algorithm is very straightforward. Get the next prime number, put it in a string, retrieve the last digit in the string, test if the digit is a 1, 3, 7, 9, or none of the above, & then add it to the list. Code:
Not great performance in Exact mode, hitting 151.9 seconds with 1000 primes starting with 7. However, in Approx. mode, I get a decent time of 86.5 seconds. Thanks for the challenge Gerson. I had fun. 

06012019, 12:42 PM
(This post was last modified: 06012019 12:57 PM by Albert Chan.)
Post: #8




RE: RPL exercise  Last Digits of Primes (HP 49G, G+, 50g)
(06012019 05:29 AM)Gilles Wrote: for 10'000, I get { 2485 2515 2500 2492 } in 0.97sec Hi, Gilles Since OP started with "first" prime of 7, prime last digits must be 1,3,7,9 In other words, sum of the distributions must add up back to number of primes. We can even optimize the code by counting only 1,3,7's, and derive count of 9's For 10,000: 1,3,7,9's should be {2485 2515 2508 2492} For 100,000: 1,3,7,9's should be {24968 25008 25015 25009} 

06012019, 12:48 PM
Post: #9




RE: RPL exercise  Last Digits of Primes (HP 49G, G+, 50g)
(06012019 08:51 AM)Carsen Wrote: ...test if the digit is a 1, 3, 7, 9, or none of the above How could it be none of the above? It can't be 5 because the number would then be divisible by 5 and it can't be any of 0, 2, 4, 6, or 8 or the number is divisible by 2. It *has* to be one of those 4. You can simply extract the last digit and not bother with the test. 

06012019, 02:38 PM
Post: #10




RE: RPL exercise  Last Digits of Primes (HP 49G, G+, 50g)
.
Hi, Carsen, (06012019 08:51 AM)Carsen Wrote: Here's my take on the challenge. The algorithm is very straightforward. Get the next prime number, put it in a string, retrieve the last digit in the string [...] That's too inefficient, you don't need to deal with strings to extract the last digit of a nonnegative integer number, just do a MOD 10, which will be much simpler and many times faster. Also, once you have the last digit you don't need to do any comparisons, just use that last digit as the index to elements in an array which holds the counts for each last digit and keep a tally by simply incrementing the corresponding array element having that index (the last digit). I'd post one line of trivial HP71B code using that approach but this challenge is for RPL machines and I don't want to intrude. Regards and have a nice weekend. V. . 

06012019, 03:17 PM
Post: #11




RE: RPL exercise  Last Digits of Primes (HP 49G, G+, 50g)
(06012019 08:51 AM)Carsen Wrote: Hi Everyone. I am glad you had fun. That was the idea, hence an 'exercise', not a 'challenge'. Just two remarks: 1) The STR> before should be an OBJ> (just a manual listing mistake); 2) You can omit the optional case clause, DUP == THEN { 0 0 0 0 } END (see grsbanks's comment below in this thread). Thus your byte count will be under 200 and you can save about three seconds in Exact Mode. I had considered testing this CASE structure, but I didn't. Thanks for doing it. I would get about the same running times, but at least I could have tried Approximate Mode, which is not possible in my programs. Gerson. 

06012019, 03:29 PM
Post: #12




RE: RPL exercise  Last Digits of Primes (HP 49G, G+, 50g)
(06012019 02:38 PM)Valentin Albillo Wrote:(06012019 08:51 AM)Carsen Wrote: Here's my take on the challenge. The algorithm is very straightforward. Get the next prime number, put it in a string, retrieve the last digit in the string [...] I had tried MOD 10 too, especially because it would reduce the byte count, but for a reason I can't explain the running time changed from 155.4 seconds to 1677.1 seconds. (06012019 02:38 PM)Valentin Albillo Wrote: I'd post one line of trivial HP71B code using that approach but this challenge is for RPL machines and I don't want to intrude. Please do it if you wish, that's no intrusion. I mentioned RPL and those particular models because they have ISPRIME builtin (not sure about the HP71B or its Math ROM). Best regards, Gerson. 

06012019, 03:41 PM
Post: #13




RE: RPL exercise  Last Digits of Primes (HP 49G, G+, 50g)
Thank you all for your participation and for the interesting and efficient solutions.
Here are my rather convoluted ones: Base 10: Code:
I had tried 10 MOD instead of \>STR DUP SIZE DUP SUB OBJ\> above, but akwardly the running time would increase from 155.4 s to 1677.1 s, for 1000 primes. Base 8: Code:


06012019, 04:08 PM
Post: #14




RE: RPL exercise  Last Digits of Primes (HP 49G, G+, 50g)
(06012019 03:41 PM)Gerson W. Barbosa Wrote: Thank you all for your participation and for the interesting and efficient solutions. That's an interesting approach, Gerson. I'm a little surprised it did as well as it did, considering the jumps into CAS commands you've got going on. MOD with approximate numbers is generally faster than MOD with exact integers on the 50g, which is the main reason I used the I→R 10. MOD construct in my original (and subsequent) programs. Yet another UserRPL take on this that is both shorter and faster: Code: \<< It definitely dives into the more obscure end of the pool, though. It keeps the counters on the stack instead of contained in composite, and converts the remainder directly into a stack level to determine which counter to increment. This one completes an input of 1000. in about 32s. Carsen's use of the case statement inspired me to take another look at the performance using that type of construct. I use case structures a lot in SysRPL, but tend not to in UserRPL because they always feel verbose in that environment for some reason. I made another stackbased attempt that uses a case structure for determining which counter to update: Code: \<< While the code size jumped up considerably, the performance actually improved using this method by a few seconds (29s). I also wanted to see how a SysRPL version would perform: Code: :: It essentially uses the same approach as the previous program, but finishes in about 19s. 

06012019, 09:11 PM
Post: #15




RE: RPL exercise  Last Digits of Primes (HP 49G, G+, 50g)
(06012019 04:08 PM)DavidM Wrote: MOD with approximate numbers is generally faster than MOD with exact integers on the 50g, which is the main reason I used the old I→R 10. MOD construct in my original (and subsequent) programs. That did the trick, thanks! By using 10. MOD R→I the running time fell down to 147.1 seconds (previously 1677.1 seconds!). (06012019 04:08 PM)DavidM Wrote: Carsen's use of the case statement inspired me to take another look at the performance using that type of construct. I use case structures a lot in SysRPL, but tend not to in UserRPL because they always feel verbose in that environment for some reason. I made another stackbased attempt that uses a case structure for determining which counter to update: Wow! On my smartphone I get { 24968. 25008. 25015. 25009. } in 86 seconds and { 249934. 250109. 250017. 249940. } in about two and a half hours! Thanks again! 

06012019, 09:59 PM
Post: #16




RE: RPL exercise  Last Digits of Primes (HP 49G, G+, 50g)
Hi again, Gerson: (06012019 03:29 PM)Gerson W. Barbosa Wrote:(06012019 02:38 PM)Valentin Albillo Wrote: I'd post one line of trivial HP71B code using that approach but this challenge is for RPL machines and I don't want to intrude. Ok, thanks. Since you asked for it, this is my HP71B code. All the work is done by the one line in the middle (45 bytes), the first line is just initialization and the last line is just for outputting results and timing: 1 DESTROY ALL @ DIM T(9) @ INPUT N @ SETTIME 0 @ P=5 2 FOR I=1 TO N @ P=FPRIM(P+2) @ L=MOD(P,10) @ T(L)=T(L)+1 @ NEXT I 3 FOR I=1 TO 9 STEP 2 @ DISP T(I); @ NEXT I @ DISP TIME As I told Carsen in my previous post above, there's no need for strings and there's no need for comparisons, cases, or whatever unneeded complexities, using the last digit as an index to increment that digit's count is all it takes to keep the tally. Running my code in go71b on an budget Android tablet I get this results and timings: >RUN ? 100 > 24, 26, 26, 24 in 0.07 sec. ? 1000 > 245, 253, 256, 246 in 1.05 sec. ? 10000 > 2485, 2515, 2508, 2492 in 18.21 sec. ? 100000 > 24968, 25008, 25015, 25009 in 443.91 sec. Best regards and have a nice weekend. V. 

06012019, 11:05 PM
(This post was last modified: 06012019 11:06 PM by Dave Britten.)
Post: #17




RE: RPL exercise  Last Digits of Primes (HP 49G, G+, 50g)
I don't have my 48 handy at the moment, but here's a 42S/DM42 version. Input the number of primes greater than 5 to look for, and XEQ "PRMDGT". The number of primes ending in 1, 3, 7, and 9 will be in stack T, Z, Y, and X respectively. This uses the wellknown mod 30 sieve to check for primes.
Code: 00 { 53Byte Prgm } This finds and tallies 1000 primes in about 25 seconds on my DM42 when running in fast mode (i.e. connected to external power). 

06022019, 04:39 PM
(This post was last modified: 06022019 04:49 PM by John Keith.)
Post: #18




RE: RPL exercise  Last Digits of Primes (HP 49G, G+, 50g)
Here is my (somewhat cheating) version, using two external commands. I think it is the fastest user RPL version so far, but only because it leverages David's and Werner's assembly programming.
Code:
24.3 seconds; 181 seconds for 5000. Output for 5000: { 1: 1243 3: 1259 7: 1252 9: 1246 } 

06022019, 06:10 PM
(This post was last modified: 06022019 09:34 PM by Gerson W. Barbosa.)
Post: #19




RE: RPL exercise  Last Digits of Primes (HP 49G, G+, 50g)
(06012019 11:05 PM)Dave Britten Wrote: ... 100 000 primes in 143.01 seconds on my smartphone. Here is a wp34s version: Code:
Running time in seconds in register X. Last digits counts in registers 01, 03, 07 and 09. 100 000 primes in 14.3 seconds on the smartphone 1000 primes in 73.5 seconds on the wp34s. P.S.: 10 000 0000 primes in about 45 minutes on the smartphone. 1: 2 499 756 3: 2 500 208 7: 2 500 284 9: 2 499 752 

06022019, 09:18 PM
(This post was last modified: 06022019 10:12 PM by Gilles.)
Post: #20




RE: RPL exercise  Last Digits of Primes (HP 49G, G+, 50g)
Here a newRPL version :
Code:
10'000 > { 2485 2515 2508 2492 } in 0.01s 100'000 > { 24968 25008 25015 25009 } in 0.78s 1'000'000 > { 249934 250109 250017 249940 } in 23.2 s 10'000'000 > { 2499756 2500208 2500284 2499752 } in 963s I notice that in newRPL :  LIST is little faster than ARRAY  Local variable is faster than big juggles with the stack  MAP is little faster than DOSUBS (MAP is very slow in UserRPL)  There is a problem with this program on my HP50g hdw (reported to Claudio)  Albert Chan suggest in a post to optimise by counting only 1,3,7's, and derive the count of 9's, but this need a test and there is no significant gain. ( I probably do a typo error in my previous post for the output , I will verify) 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)