mini-challenge from UH contest
in [HP48]
|
Prev: StreamSmart
Next: UH calculator contest challenge
From: Virgil on 29 Nov 2009 19:58 In article <Virgil-E22CFB.13274629112009(a)bignews.usenetmonster.com>, Virgil <Virgil(a)home.esc> wrote: > In article > <7e4c4329-5097-4eb9-87d6-427cddbc8bf9(a)j24g2000yqa.googlegroups.com>, > Wes <wjltemp-gg(a)yahoo.com> wrote: > > > On Nov 29, 5:32 am, Virgil <Vir...(a)home.esc> wrote: > > > In article > > > <34135e51-4f7f-4c77-91c2-ed6d12b42...(a)k17g2000yqh.googlegroups.com>, > > > Wes <wjltemp...(a)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 > > 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. Now down to exactly 100 bytes, crc # 519Ch. TEVAL runtime on 2500 5 -> 519 was 105.6967 seconds.
From: Wes on 30 Nov 2009 15:49 On Nov 30, 3:58 am, Virgil <Vir...(a)home.esc> wrote: > In article <Virgil-E22CFB.13274629112...(a)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. > > > 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. > > 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
From: Virgil on 1 Dec 2009 00:50 In article <01604316-20b6-4d77-be06-1fb425920a01(a)j14g2000yqm.googlegroups.com>, Wes <wjltemp-gg(a)yahoo.com> wrote: > On Nov 30, 3:58 am, Virgil <Vir...(a)home.esc> wrote: > > In article <Virgil-E22CFB.13274629112...(a)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. > > > > > 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. > > > > 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 Now down to 87.5 bytes , crc # 27Dh, and 2500 5 -> 519 in 65.0577 seconds.
From: Wes on 1 Dec 2009 13:55 On Dec 1, 8:50 am, Virgil <Vir...(a)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. \<< 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
From: Virgil on 1 Dec 2009 15:24
In article <4b1a7e8a-8d7a-41cd-a8a6-190c7ce14126(a)m38g2000yqd.googlegroups.com>, Wes <wjltemp-gg(a)yahoo.com> wrote: > On Dec 1, 8:50�am, Virgil <Vir...(a)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. > > \<< > 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 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. |