mini-challenge from UH contest
in [HP48]
|
Prev: StreamSmart
Next: UH calculator contest challenge
From: Wes on 28 Nov 2009 18:10 I know Joe usually puts forth the challenges, but there's a problem 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
From: Virgil on 28 Nov 2009 21:32 In article <34135e51-4f7f-4c77-91c2-ed6d12b4206a(a)k17g2000yqh.googlegroups.com>, Wes <wjltemp-gg(a)yahoo.com> wrote: > I know Joe usually puts forth the challenges, but there's a problem > 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 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.
From: Dave Hayden on 29 Nov 2009 00:58 I have a program that gives the right answer for the two given examples. 120.5 bytes CRC= #2936h
From: Wes on 29 Nov 2009 03:27 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
From: Virgil on 29 Nov 2009 15:27
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. |