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

[Gerson W. Barbosa]

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!
  

[Valentin Albillo]

.
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.
.

[Gerson W. Barbosa]

(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.

[DavidM]

(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.

[Gilles]

(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)

[Gerson W. Barbosa]

(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.

[Carsen]

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.

[Albert Chan]

(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}

[grsbanks]

(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.

[Valentin Albillo]

.
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.
.

[Gerson W. Barbosa]

(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.

[Gerson W. Barbosa]

(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.

[Gerson W. Barbosa]

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 - +
\>>

[DavidM]

(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.

[Gerson W. Barbosa]

(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!

[Valentin Albillo]

 
 
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.
 

[Dave Britten]

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).

[John Keith]

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 }

[Gerson W. Barbosa]

(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<? A
018 GTO 00
019 TICKS
020 RCL- 02
021 SDR 001
022 RTN
023 LBL 01
024 INC 04
025 RCL X
026 # 010
027 MOD
028 INC→X
029 R↓
030 END

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

[Gilles]

Here a newRPL version :

Code:


«
  0 9 NDUPN →LIST → stat 
  « 
   5 SWAP 1 SWAP START
      NEXTPRIME DUP 0 0 DIGITS 'stat' SWAP DUP2 GET 1 + PUT 
    NEXT
    { 1 3 7 9 } « 'stat' SWAP GET  »  MAP 
  »
»

With the simulator on my PC :

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)