mini-challenge from UH contest
in [HP48]
|
Prev: StreamSmart
Next: UH calculator contest challenge
From: Yann on 1 Dec 2009 15:32 you may also start from a higher value than 1. 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.
From: Wes on 1 Dec 2009 15:49 On Dec 1, 9:55 pm, Wes <wjltemp...(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. > > 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 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
From: Yann on 1 Dec 2009 15:58 Virgil's version with trivial speed-oriented modifications : 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 \>>
From: Wes on 1 Dec 2009 16:03 On Dec 1, 11:24 pm, Virgil <Vir...(a)home.esc> wrote: > In article > <4b1a7e8a-8d7a-41cd-a8a6-190c7ce14...(a)m38g2000yqd.googlegroups.com>, > > > > Wes <wjltemp...(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. 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
From: Wes on 1 Dec 2009 16:06
On Dec 2, 12:03 am, Wes <wjltemp...(a)yahoo.com> wrote: > On Dec 1, 11:24 pm, Virgil <Vir...(a)home.esc> wrote: > > > > > In article > > <4b1a7e8a-8d7a-41cd-a8a6-190c7ce14...(a)m38g2000yqd.googlegroups.com>, > > > Wes <wjltemp...(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. > > 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 make that 2 STEP instead of 2. STEP (no decimal) -wes |