RPL exercise - Last Digits of Primes (HP 49G, G+, 50g) - Printable Version +- HP Forums (https://www.hpmuseum.org/forum) +-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html) +--- Forum: General Forum (/forum-4.html) +--- Thread: RPL exercise - Last Digits of Primes (HP 49G, G+, 50g) (/thread-13054.html) Pages: 1 2 RPL exercise - Last Digits of Primes (HP 49G, G+, 50g) - Gerson W. Barbosa - 06-01-2019 03:07 AM 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!    RE: RPL exercise - Last Digits of Primes (HP 49G, G+, 50g) - Valentin Albillo - 06-01-2019 04:13 AM . Hi, Gerson, (06-01-2019 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. . RE: RPL exercise - Last Digits of Primes (HP 49G, G+, 50g) - Gerson W. Barbosa - 06-01-2019 04:43 AM (06-01-2019 04:13 AM)Valentin Albillo Wrote:  . Hi, Gerson, (06-01-2019 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 ... 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. RE: RPL exercise - Last Digits of Primes (HP 49G, G+, 50g) - DavidM - 06-01-2019 05:02 AM (06-01-2019 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 brute-force method: Code: ```\<<    0. 9. NDUPN \->ARRY    5    ROT    1 SWAP START       NEXTPRIME       SWAP OVER       I\->R 10. MOD       DUP2       GET 1. + PUT       SWAP    NEXT    DROP    DUP 1. GET SWAP    DUP 3. GET SWAP    DUP 7. GET SWAP    9. GET    4. \->LIST \>>``` 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. RE: RPL exercise - Last Digits of Primes (HP 49G, G+, 50g) - Gilles - 06-01-2019 05:29 AM (06-01-2019 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) RE: RPL exercise - Last Digits of Primes (HP 49G, G+, 50g) - Gerson W. Barbosa - 06-01-2019 05:44 AM (06-01-2019 05:02 AM)DavidM Wrote:   (06-01-2019 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 brute-force method: Code: ```\<<    0. 9. NDUPN \->ARRY    5    ROT    1 SWAP START       NEXTPRIME       SWAP OVER       I\->R 10. MOD       DUP2       GET 1. + PUT       SWAP    NEXT    DROP    DUP 1. GET SWAP    DUP 3. GET SWAP    DUP 7. GET SWAP    9. GET    4. \->LIST \>>``` 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. 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. RE: RPL exercise - Last Digits of Primes (HP 49G, G+, 50g) - Carsen - 06-01-2019 08:51 AM 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: ``` <<   { 0 0 0 0 }  5 ROT 1 SWAP START NEXTPRIME DUP ->STR DUP SIZE DUP SUB STR-> CASE DUP 1 == THEN { 1 0 0 0 } END DUP 3 == THEN { 0 1 0 0 } END DUP 7 == THEN { 0 0 1 0 } END DUP 9 == THEN { 0 0 0 1 } END DUP == THEN { 0 0 0 0 } END END NIP ROT ADD SWAP NEXT DROP >>``` 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. RE: RPL exercise - Last Digits of Primes (HP 49G, G+, 50g) - Albert Chan - 06-01-2019 12:42 PM (06-01-2019 05:29 AM)Gilles Wrote:  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) 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} RE: RPL exercise - Last Digits of Primes (HP 49G, G+, 50g) - grsbanks - 06-01-2019 12:48 PM (06-01-2019 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. RE: RPL exercise - Last Digits of Primes (HP 49G, G+, 50g) - Valentin Albillo - 06-01-2019 02:38 PM . Hi, Carsen, (06-01-2019 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 non-negative 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 HP-71B 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. . RE: RPL exercise - Last Digits of Primes (HP 49G, G+, 50g) - Gerson W. Barbosa - 06-01-2019 03:17 PM (06-01-2019 08:51 AM)Carsen Wrote:  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: ``` <<   { 0 0 0 0 }  5 ROT 1 SWAP START NEXTPRIME DUP ->STR DUP SIZE DUP SUB STR-> CASE DUP 1 == THEN { 1 0 0 0 } END DUP 3 == THEN { 0 1 0 0 } END DUP 7 == THEN { 0 0 1 0 } END DUP 9 == THEN { 0 0 0 1 } END DUP == THEN { 0 0 0 0 } END END NIP ROT ADD SWAP NEXT DROP >>``` 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. 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. RE: RPL exercise - Last Digits of Primes (HP 49G, G+, 50g) - Gerson W. Barbosa - 06-01-2019 03:29 PM (06-01-2019 02:38 PM)Valentin Albillo Wrote:   (06-01-2019 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 non-negative integer number, just do a MOD 10, which will be much simpler and many times faster. 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. (06-01-2019 02:38 PM)Valentin Albillo Wrote:  I'd post one line of trivial HP-71B 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 built-in (not sure about the HP-71B or its Math ROM). Best regards, Gerson. RE: RPL exercise - Last Digits of Primes (HP 49G, G+, 50g) - Gerson W. Barbosa - 06-01-2019 03:41 PM Thank you all for your participation and for the interesting and efficient solutions. Here are my rather convoluted ones: Base 10: Code: ``` %%HP: T(3)A(R)F(,); \<< DUP { } SWAP 5 1 ROT   START NEXTPRIME SWAP OVER \->STR DUP SIZE DUP SUB OBJ\-> + SWAP   NEXT DROP 2 * 1 - \PILIST FACTOR \->STR "*" "''" SREPL DROP OBJ\-> 3 \->LIST LN { 5 13 17 } LN / EXPAND SWAP OVER \GSLIST - SWAP + \>>``` 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: ``` %%HP: T(3)A(R)F(,); \<< DUP OCT { } SWAP 2 1 ROT   START NEXTPRIME SWAP OVER R\->B \->STR DUP SIZE 1 - DUP SUB OBJ\-> + SWAP   NEXT DROP 8 - NEG \PILIST FACTOR \->STR "*" "''" SREPL DROP OBJ\-> 3 \->LIST LN { 3 5 7 } LN / EXPAND REVLIST SWAP OVER \GSLIST - + \>>``` RE: RPL exercise - Last Digits of Primes (HP 49G, G+, 50g) - DavidM - 06-01-2019 04:08 PM (06-01-2019 03:41 PM)Gerson W. Barbosa Wrote:  Thank you all for your participation and for the interesting and efficient solutions. Here are my rather convoluted ones: ... 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: ```\<<    0. DUPDUP DUP    5    6. ROLL 1 SWAP START       NEXTPRIME       DUP I\->R 10. MOD       { 0. 9. 7. 3. 1. } SWAP POS       DUP 1. +       ROLL 1. +       SWAP ROLLD    NEXT    DROP    4. \->LIST \>>``` 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 stack-based attempt that uses a case structure for determining which counter to update: Code: ```\<<    0. DUPDUP DUP    5    6. ROLL 1 SWAP START       NEXTPRIME       DUP I\->R 10. MOD       CASE          1. OVER SAME          THEN             DROP             5. ROLL             1. +             5. ROLLD          END          3. OVER SAME          THEN             DROP             4. ROLL             1. +             4. ROLLD          END          7. OVER SAME          THEN             DROP             ROT             1. +             UNROT          END          DROP          SWAP          1. +          SWAP       END    NEXT    DROP    4. \->LIST \>>``` 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: ```::    CK1NOLASTWD    CK&DISPATCH1    real ::       BINT0 DUPDUP DUP       Z5_       6ROLL COERCE ZERO_DO (DO)          FLASHPTR Prime+          DUP FLASHPTR Z>R %10 %MOD          ::             %1 EQcasedrop :: 5ROLL #1+ 5UNROLL ;             %3 EQcasedrop :: 4ROLL #1+ 4UNROLL ;             %7 EQcasedrop :: ROT #1+ UNROT ;             ( otherwise %9 )             DROP SWAP #1+ SWAP          ;       LOOP       DROP       BINT4 ZERO_DO (DO)          UNCOERCE          4UNROLL       LOOP       BINT4 {}N    ; ;``` It essentially uses the same approach as the previous program, but finishes in about 19s. RE: RPL exercise - Last Digits of Primes (HP 49G, G+, 50g) - Gerson W. Barbosa - 06-01-2019 09:11 PM (06-01-2019 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!). (06-01-2019 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 stack-based attempt that uses a case structure for determining which counter to update: Code: ```\<<    0. DUPDUP DUP    5    6. ROLL 1 SWAP START       NEXTPRIME       DUP I\->R 10. MOD       CASE          1. OVER SAME          THEN             DROP             5. ROLL             1. +             5. ROLLD          END          3. OVER SAME          THEN             DROP             4. ROLL             1. +             4. ROLLD          END          7. OVER SAME          THEN             DROP             ROT             1. +             UNROT          END          DROP          SWAP          1. +          SWAP       END    NEXT    DROP    4. \->LIST \>>``` While the code size jumped up considerably, the performance actually improved using this method by a few seconds (29s). 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! RE: RPL exercise - Last Digits of Primes (HP 49G, G+, 50g) - Valentin Albillo - 06-01-2019 09:59 PM     Hi again, Gerson: (06-01-2019 03:29 PM)Gerson W. Barbosa Wrote:   (06-01-2019 02:38 PM)Valentin Albillo Wrote:  I'd post one line of trivial HP-71B 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 built-in (not sure about the HP-71B or its Math ROM). Ok, thanks. Since you asked for it, this is my HP-71B 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.   RE: RPL exercise - Last Digits of Primes (HP 49G, G+, 50g) - Dave Britten - 06-01-2019 11:05 PM 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 well-known mod 30 sieve to check for primes. Code: ```00 { 53-Byte Prgm } 01▸LBL "PRMDGT" 02 CLRG 03 STO 06 04 5 05 STO 05 06▸LBL 00 07 2 08 STO+ 05 09▸LBL 01 10 RCL 05 11 XEQ "PRIME?" 12 FC? 01 13 GTO 00 14 RCL 05 15 10 16 MOD 17 1 18 STO+ IND ST Y 19 DSE 06 20 GTO 00 21 RCL 01 22 RCL 03 23 RCL 07 24 RCL 09 25 CF 01 26 END 00 { 96-Byte Prgm } 01▸LBL "PRIME?" 02 STO 00 03 SF 01 04 0 05 STO 02 06 2 07 XEQ 02 08 1 09 XEQ 02 10 2 11 XEQ 02 12 2 13 XEQ 02 14▸LBL 01 15 RCL 00 16 RCL 02 17 X↑2 18 X>Y? 19 RTN 20 4 21 XEQ 02 22 2 23 XEQ 02 24 4 25 XEQ 02 26 2 27 XEQ 02 28 4 29 XEQ 02 30 6 31 XEQ 02 32 2 33 XEQ 02 34 6 35 XEQ 02 36 GTO 01 37▸LBL 02 38 STO+ 02 39 RCL 00 40 RCL 02 41 X=Y? 42 RTN 43 MOD 44 X=0? 45 CF 01 46 RTN 47 END``` This finds and tallies 1000 primes in about 25 seconds on my DM42 when running in fast mode (i.e. connected to external power). RE: RPL exercise - Last Digits of Primes (HP 49G, G+, 50g) - John Keith - 06-02-2019 04:39 PM 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: ``` \<< 5 # 1d # 1000d   START NEXTPRIME DUP I\->R 10. MOD SWAP   NEXT DROP 1000. \->LIST LSORT LRPCT EVAL SWAP \->TAG \>>``` 24.3 seconds; 181 seconds for 5000. Output for 5000: { 1: 1243 3: 1259 7: 1252 9: 1246 } RE: RPL exercise - Last Digits of Primes (HP 49G, G+, 50g) - Gerson W. Barbosa - 06-02-2019 06:10 PM (06-01-2019 11:05 PM)Dave Britten Wrote:  ... This finds and tallies 1000 primes in about 25 seconds on my DM42 when running in fast mode (i.e. connected to external power). 100 000 primes in 143.01 seconds on my smartphone. Here is a wp34s version: Code: ``` 001 LBL A 002 STO A 003 CLx 004 FILL 005 STOS 01 006 STOS 06 007 # 005 008 TICKS 009 STO 02 010 LBL 00 011 R↓ 012 INC X 013 INC X 014 PRIME? 015 XEQ 01 016 RCL 04 017 x { 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)