mini-challenge from UH contest
Wes
that I think falls into the spirit of such. In the Univ. of Houston
Calculator contest that has been discussed in another thread, there is
the following question:
19) Give the number of positive integers that are no larger than 1,100
and are not
divisible by any of the first 25 prime numbers.
The way I did this was harder than it needed to be. I didn't notice
till later that the answer will simply be equal to 184 (the number of
primes below 1100) - 25 (the first 25 primes) + 1 (the number 1
itself) = 160. The problem would have been more interesting if the
upper value (1100) had been large enough, or the number of prime
numbers (25) had been small enough, so as to include some composite
numbers.
Here's the revised challenge:
Write a UserRPL program that takes two numeric arguments (I'll call
them N and P) and gives the number of positive integers that are no
larger than N and are not divisible by any of the first P prime
numbers. You may give the two arguments in any order you wish. The
program may not make use of any pre-generated values or lists, nor
leave anything extra on the stack. Smallest program wins.
Examples:
1100 25 -> 160
40 2 -> 13 (the 13 values include 2 composites: 1 5 7 11 13 17 19 23
25 29 31 35 37 )
(I don't want to give away my smallest size, but the crc is 83C1h just
in case somebody matches it.)
Enjoy,
-wes
Virgil
<34135e51-4f7f-4c77...@k17g2000yqh.googlegroups.com>,
Wes <wjlte...@yahoo.com> wrote:
I have a program of 127 bytes, crc #4ADFh, which seems to work (it gives
the same result as your two examples), but is very slow, especially for
larger values. The 1100 25 example took several minutes, eventually
producing that 160 desired result.
Dave Hayden
examples. 120.5 bytes CRC= #2936h
Wes
> In article
> <34135e51-4f7f-4c77-91c2-ed6d12b42...@k17g2000yqh.googlegroups.com>,
> Wes <wjltemp...@yahoo.com> wrote:
> > Here's the revised challenge:
> > Write a UserRPL program that takes two numeric arguments (I'll call
> > them N and P) and gives the number of positive integers that are no
> > larger than N and are not divisible by any of the first P prime
> > numbers. You may give the two arguments in any order you wish. The
> > program may not make use of any pre-generated values or lists, nor
> > leave anything extra on the stack. Smallest program wins.
>
> > Examples:
> > 1100 25 -> 160
> > 40 2 -> 13
> > (the 13 values include 2 composites: 1 5 7 11 13 17 19 23 25 29 31 35 37 )
>
> > (I don't want to give away my smallest size, but the crc is 83C1h just
> > in case somebody matches it.)
>
> > Enjoy,
> > -wes
>
> I have a program of 127 bytes, crc #4ADFh, which seems to work (it gives
> the same result as your two examples), but is very slow, especially for
> larger values. The 1100 25 example took several minutes, eventually
> producing that 160 desired result.
Perhaps we should have another category for smallest size*runtime for
a given input that may take a while to complete, say:
2500. 5. -> 519.
-wes
Virgil
<7e4c4329-5097-4eb9...@j24g2000yqa.googlegroups.com>,
Wes <wjlte...@yahoo.com> wrote:
I have a new one which increases the speed considerably and diminishes
the size to 109.5 bytes, crc #14A0h, and I suspect I can do better.
Virgil
Virgil <Vir...@home.esc> wrote:
Now down to exactly 100 bytes, crc # 519Ch.
TEVAL runtime on 2500 5 -> 519 was 105.6967 seconds.
Wes
> In article <Virgil-E22CFB.13274629112...@bignews.usenetmonster.com>,
> > > Perhaps we should have another category for smallest size*runtime for
> > > a given input that may take a while to complete, say:
>
> > > 2500. 5. -> 519.
>
> > the size to 109.5 bytes, crc #14A0h, and I suspect I can do better.
>
> Now down to exactly 100 bytes, crc # 519Ch.
>
> TEVAL runtime on 2500 5 -> 519 was 105.6967 seconds.
= 10.3 KB*sec
I look forward to seeing how you got the runtime down so small.
My entry weighs in at 82.5 bytes (crc #83C1h) with a run time of
292.7327 sec
= 23.6 KB*sec
-wes
Virgil
<01604316-20b6-4d77...@j14g2000yqm.googlegroups.com>,
Wes <wjlte...@yahoo.com> wrote:
Now down to 87.5 bytes , crc # 27Dh, and 2500 5 -> 519 in 65.0577
seconds.
Wes
> Now down to 87.5 bytes , crc # 27Dh, and 2500 5 -> 519 in 65.0577
> seconds.
That looks good. I'm still going to toy around with these, but here
are my current entries:
My smallest: 82 bytes (#6EA3h), 105.4209 sec
2500. 5. -> 519.
\<<
2
2. PICK3 START
SWAP OVER NEXTPRIME
NEXT
SWAP \->LIST
0.
1. 4. ROLL
FOR I
I PICK3 MOD 0. POS NOT +
2. STEP
NIP
\>>
Looks like I can't touch Virgil's 65 second program. My fastest is
the same as above with a small change at the start.
My fastest: 87 bytes (#AEE1h), 93.0436 sec
\<<
1. -
3.
2. PICK3 START
SWAP OVER NEXTPRIME
NEXT
SWAP \->LIST
0.
1. 4. ROLL
FOR I
I PICK3 MOD 0. POS NOT +
2. STEP
NIP
\>>
I'm convinced it would be faster to use MOD inside a DO or WHILE loop
instead of using MOD with the whole list of the primes, but I haven't
been successful at implementing it. Also, I think there must be a way
to determine the composites directly instead of searching for them,
but I keep getting bogged down with that too.
-wes
Virgil
<4b1a7e8a-8d7a-41cd...@m38g2000yqd.googlegroups.com>,
Wes <wjlte...@yahoo.com> wrote:
My smallest and fastest: # C27Ah at 85 bytes
and 2500 5 -> 519 in 65.9287 seconds is
\<<
1 DUPDUP 4 ROLL
START
NEXTPRIME SWAP OVER * SWAP
NEXT DROP
0 1 4 ROLL
FOR X
X PICK3 GCD 1 == +
NEXT NIP
\>>
The key to my program is noting that the Greatest Common Divisor of a
number we want to count and the product of our primes is 1
so product-of-primes GCD 1 ==" returns 1 for numbers we want to count
and 0 the ones we don't want to count.
Yann
After all, you already calculated the first P prime,
so you know, by definition, that all values before the last prime are
not part of the solution.
another speed trick : do not calculate for I/3 , this saves another
1/3 of computation.
Wes
> On Dec 1, 8:50 am, Virgil <Vir...@home.esc> wrote:
>
> > Now down to 87.5 bytes , crc # 27Dh, and 2500 5 -> 519 in 65.0577
> > seconds.
>
> That looks good. I'm still going to toy around with these, but here
> are my current entries:
>
> My smallest: 82 bytes (#6EA3h), 105.4209 sec
> 2500. 5. -> 519.
>
> the same as above with a small change at the start.
>
> My fastest: 87 bytes (#AEE1h), 93.0436 sec
Here's a different approach, bigger but faster.
127.5 bytes (#9179h) 59.4471 seconds
\<< @ n p
1. -
@ generate list of primes
3. @ n p 3(first odd prime)
2. PICK3 @ n p 3 2 p
START @ n p 3
SWAP OVER NEXTPRIME @ n 3 p 5
NEXT @ n 3 5 7 ... p lastprime
SWAP @ n 3 5 7 ... lastprime p
\->LIST @ n { 3 5 7 ... }
0. @ n {} count
1. 4. ROLL @ {} count 1 n
FOR I @ {} count
OVER 1. @ {} count {} index
0. @ {} count {} index FILLER
DO
DROP @ {} count {} index
GETI @ {} count {} index p
UNTIL
I SWAP MOD NOT DUP -64. FS? OR
END @ {} count {} index flag
NIP NIP @ {} count flag
NOT + @ {} newcount
2. STEP @ just check odds
NIP
\>>
and probably room for improvement.
-wes
Yann
down to 25.69 sec (90.5 bytes, #D361h)
\<<
1 DUPDUP 4 ROLL
START
NEXTPRIME SWAP OVER * SWAP
NEXT
0 SWAP NEXTPRIME 4 ROLL
FOR X
X PICK3 GCD 1 == +
2 STEP NIP
\>>
Wes
> In article
This is sweet. I've got to think about that GCD thing. And better
yet, change
FOR X
X PICK3 GCD 1 == +
NEXT
to
FOR X
X PICK3 GCD 1 == +
2. STEP
and you should be able to cut the time in half. (no need to check the
even numbers).
-wes
Wes
make that
2 STEP
instead of
2. STEP
(no decimal)
-wes
Virgil
<0dde68ee-7733-4500...@g12g2000yqa.googlegroups.com>,
Yann <kdo...@gmail.com> wrote:
I cannot get the above to work at all.
Are you sure that you didn't mean
\<<
1 DUPDUP 4 ROLL
START
NEXTPRIME SWAP OVER * SWAP
NEXT DROP
0 1 4 ROLL
FOR X
X PICK3 GCD 1 == +
2 STEP NIP
\>>
in which the only change is to replace my "NEXT" with "2 STEP"?
Wes
> I cannot get the above to work at all.
> 0 SWAP NEXTPRIME 4 ROLL
Perhaps he meant
1 SWAP NEXTPRIME 4 ROLL
Besides "2 NEXT", here are a couple of more small tweaks:
If you don't mind using LASTARG, you can save a 2.5 byte instruction
if you replace
NEXTPRIME SWAP OVER * SWAP
with
NEXTPRIME * LASTARG NIP
and if you don't mind putting the 2.5 bytes back,
1 DUPDUP 4 ROLL
can be replace with
1 2 DUP 4 ROLL
for a tiny speedup. This leaves 2 out of your product, but if you're
using "2 STEP" then you're not checking even numbers anyway, and I
figure GCD might be slightly faster with a smaller value.
Here's a summary of what I think are the best combinations of code.
Hats off to Virgil for his clever algorithm.
@ best size*runtime: 85 bytes, 30.0192 seconds = 2.49 KB*sec
\<<
1 DUPDUP 4 ROLL
START
NEXTPRIME * LASTARG NIP
NEXT DROP
0 1 4 ROLL
FOR X
X PICK3 GCD 1 == +
2 STEP
NIP
\>>
@ fastest: 90.5 bytes, 29.8118 seconds = 2.63 KB*sec
\<<
1 2 DUP 4 ROLL
START
NEXTPRIME * LASTARG NIP
NEXT
1 SWAP NEXTPRIME 4 ROLL
FOR X
X PICK3 GCD 1 == +
2 STEP
NIP
\>>
@ smallest: 79.5 bytes, 187.9637 sec = 14.59 KB*sec
\<<
2. 2. PICK3
START
SWAP OVER NEXTPRIME
NEXT
SWAP \->LIST 0. 1. 4. ROLL
FOR I
I PICK3 MOD 0. POS NOT +
NEXT
NIP
\>>
-wes
Wes
> @ best size*runtime: 85 bytes, 30.0192 seconds = 2.49 KB*sec
Hang on, I see another improvement on two of these. Use Virgil's GCD
idea, but instead of using a FOR loop in the 2nd half of the program,
use SEQ and process the list. For really large values, this list
might take up a lot of memory, but it seems to run pretty well with
the test values.
@ best size*runtime: 82.5 bytes(#929Eh), 28.1229 seconds = 2.27 KB*sec
\<<
1 DUPDUP 4 ROLL
START
NEXTPRIME * LASTARG NIP
NEXT
DROP RCLVX DUP 1 5 ROLL 2 SEQ
GCD 1 - NOT \GSLIST
\>>
@ fastest: 93 bytes(#18B7h), 27.7733 seconds = 2.52 KB*sec
\<<
1 2 DUP 4 ROLL
START
NEXTPRIME * LASTARG NIP
NEXT
NEXTPRIME RCLVX DUP ROT 5 ROLL 2 SEQ
GCD 1 - NOT \GSLIST 1 +
\>>
-wes