HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits

08302017, 12:20 PM
Post: #21




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
An iterative version (even if I favour the recursive one)
For the 49 and up, replace / IP by IQUOT Code: \<< Cheers, Werner 41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L,12C,16CE 

08302017, 01:02 PM
Post: #22




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
Slightly shorter version of Werner's programme:
Code: « "" SWAP 

08302017, 01:39 PM
Post: #23




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
(08302017 12:20 PM)Werner Wrote: An iterative version (even if I favour the recursive one) And here are Werner's timings on the 50g (don't have a 49g to give comparable values). In both cases I replaced / IP with IQUOT. 50000 runs with 50 as argument in 11.01 seconds on newRPL. 100 runs with 50 as argument in 26.66 seconds on 50g stock firmware. I thought this would've been a lot faster without using STO (especially on stock firmware, probably negligible difference on newRPL), but is not the case, perhaps doing MOD and IQUOT together in the main loop is hurting performance, maybe using IDIV2: Code: \<< It did improve to 10.13 sec. (from 11.01sec) on newRPL, and down to 23.33 sec. on stock firmware in exact mode, but slows down to 30.0 sec in approx mode (recompiled with reals, but why? perhaps IDIV2 needs to convert the reals back to integer?). I think for the 49g, and as long as it runs in exact mode, this is likely to be the winner entry (all credit to Werner of course), my entry clocked 24.2sec under the same conditions. Close, but slower. The weird part is my algorithm using IQUOT went even faster using reals in approx. mode, I can't understand why this algorithm (quite similar, actually) slows down with reals. So far it's a mystery to me. 

08302017, 02:06 PM
Post: #24




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
I forgot about IDIV2 ;)
And all the credit goes to Didier Lachieze, of course, the algorithm is the same. Werner 41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L,12C,16CE 

08302017, 02:08 PM
(This post was last modified: 08302017 02:11 PM by Claudio L..)
Post: #25




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
(08302017 01:02 PM)Gerald H Wrote: Slightly shorter version of Werner's programme: Even shorter when you use IDIV2: Code: « "" SWAP At only 65.5 bytes, this one gets the title for short code. This one clocked at 24.2 sec for 100 runs on a 50g, so it doesn't quite beat Werner. On newRPL, interestingly, it causes a 19x slowdown because of invoking the decompiler. Removing OBJ> makes it only 2.2x slower than plain Werner and 2.9x slower than mine. **EDIT**: This algorithm only runs in exact mode, BTW. In approx. mode the trailing dot in the reals messes up the string and OBJ> gives an error. 

08302017, 03:30 PM
Post: #26




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
Not as elegant & larger but quicker:
Code: « "" SWAP 0. OVER 

08312017, 10:57 AM
Post: #27




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
(08302017 02:08 PM)Claudio L. Wrote:(08302017 01:02 PM)Gerald H Wrote: Slightly shorter version of Werner's programme: For a version of this programme in Sys RPL see http://www.hpmuseum.org/forum/thread8941.html 

08312017, 12:49 PM
Post: #28




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
(08292017 04:02 PM)Didier Lachieze Wrote: My RPL is a bit rusty, so instead here is an HP Prime program: This is brilliant work. I've done some programming in many languages, but I've always had a mental block when it comes to recursion. I understand it, but am unable to employ it as a tool. It seems like cheating to get a solution that is dependent on a solution using the selfreferenced routine. As such, how this routine is derived, ensuring that all of the digits are odd, is nearly magic to me. I would've tried a deconstruction/digitchecking routine that would certainly have been much slower, and much more of a memory hog. Didier, is it possible for you to shed some light on how you approached this problem? It took me half an hour to understand how it works, and now that I do, I'm curious how you arrived at it. If you could dumb it down a bit, I'd be interested in the process. Kudos to you for such an elegant solution. Brad 

08312017, 09:32 PM
(This post was last modified: 08312017 09:37 PM by pier4r.)
Post: #29




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
So finally I was able to implement an idea similar to what I wanted to do.
I am happy because (a) I implemented my idea and (b) I heavily used community libraries that are awesome. The drawback is that the idea is very inefficient. It is also true that I wouldn't be able to get to the same level of some solutions already posted. Those are relatively refined compared to my skills. In particular with DOPERM I did not identify a way to create "ordered permutations" through which I could halt the execution earlier. Well does not matter, the first objective is to get the answer correct, if possible with a nice way. Then optimizations may be applied. Ah, 50th number asked (179), 190 seconds. Also I am not sure it can process some large number, like 8000. Code:
Wikis are great, Contribute :) 

09012017, 07:48 AM
(This post was last modified: 09012017 09:28 AM by Didier Lachieze.)
Post: #30




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
(08312017 12:49 PM)Brad Barton Wrote: Didier, is it possible for you to shed some light on how you approached this problem? It took me half an hour to understand how it works, and now that I do, I'm curious how you arrived at it. If you could dumb it down a bit, I'd be interested in the process. Thanks for your nice words. It’s not so complex but recursion can be difficult to grasp. Here is the way I approached this problem (it’s a bit long and I hope it’s not too boring to go in all these details): I first made a table of the first terms to get a sense of the series: Code: N A(N) There is clearly a link to counting in Base 5 but with the digits 0,1,2,3,4 replaced by 1,3,5,7,9 So I added a column with N in Base 5: Code: N A(N) Nb5 But A(N) and Nb5 are not correctly aligned, this comes from the fact N is starting from 1 and not 0, so I moved down Nb5 by one row, transforming it to (N1)b5 : Code: N A(N) (N1)b5 Then I split the base 5 number in the quotient of division by 5 a=IP((N1)/5) and the unit number b=(N1) MOD 5, then I converted the unit number to the sequence 1,3,5,7,9: Code: N A(N) (N1)b5 a b 2*b+1 This way for each N I have 10*a+2*b+1 which has the right unit digit, so I need now to apply the same formula to a, and so on, to convert each digit of (N1)b5 to the sequence 1,3,5,7,9. This is where the recursion comes to play: I have a formula that breaks my number in two parts and I have to apply this same formula to one of the parts. As for any recursion you need a stop condition, in this case it’s when a=0 which translates to N<=5. This is how I came with the first version of the program: Code: EXPORT IntOdd(N) Then it was just a matter of code optimization to get rid of the local variables and fit everything on a single line: Code: EXPORT IntOdd(N) Some problems lend naturally to a recursive function which I found quite elegant, but there are some drawbacks in performance and memory size. A recursive function is generally slower and requires more memory that a loop. I’ve not a pure analytical mind and it helps me a lot when I can visualize the operations. For the recursion mechanism as in the program above I like to think to it as if I were in a room in a big tower with the number in my hands and a hole in the centre of the room with stairs going down. So I break my number in two parts, drop the right part (2*b+1) on the floor and go down with the left part (a), I then arrive in a similar looking room and I break again my number, leave the right part on the floor, go down and repeat until I have no number anymore in my hand. From there I go up collecting the different parts I’ve dropped on each level and building up the result by multiplying the number in my hand by 10 and adding the number on the floor until I’m back to the starting floor with the result in my hand. But every mind is different and what works well for me may not work for others. "There's more than one way to skin a cat." EDIT: here is a picture showing on the left the different recursive calls going down with the number dropped at each level, and on the right the process to go up through the different returns while building the result by collecting the numbers dropped at each level. 

09012017, 08:11 AM
Post: #31




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
(09012017 07:48 AM)Didier Lachieze Wrote: Here is the way I approached this problem (it’s a bit long and I hope it’s not too boring to go in all these details): Thanks for sharing. Several passes where similar to mine, I did not thought about the 2b+1 though. Also my idea is: always better be a bit boring but clear, rather than using a style  that I perceived in many books that for me were written like showing off  to write in short way but cryptic. So I enjoyed your explanation. Wikis are great, Contribute :) 

09012017, 02:55 PM
Post: #32




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
(09012017 07:48 AM)Didier Lachieze Wrote: Here is the way I approached this problem (it’s a bit long and I hope it’s not too boring to go in all these details): Absolutely NOT boring, and the details are much appreciated. Quote:There is clearly a link to counting in Base 5... Hadn't thought of using a different base, but once it's written down, it is a bit embarrassingly obvious. Thanks for this tool. Quote:Then I split the base 5 number in the quotient of division by 5 a=IP((N1)/5) and the unit number b=(N1) MOD 5, then I converted the unit number to the sequence 1,3,5,7,9: Applying the offset (N1), dividing the result into and IP and remainder, then using 2b+1 to convert the Base5 remainders back to the odd sequence is a pretty slick way to do it. Nice. Quote:This is where the recursion comes to play: I have a formula that breaks my number in two parts and I have to apply this same formula to one of the parts. As for any recursion you need a stop condition, in this case it’s when a=0 which translates to N<=5. So you just continue to apply IntOdd to the left over pieces until a=0 then gather up the results and add 2b+1 back in. I see... Quote:For the recursion mechanism as in the program above I like to think to it as if I were in a room in a big tower with the number in my hands and a hole in the centre of the room with stairs going down. So I break my number in two parts, drop the right part (2*b+1) on the floor and go down with the left part (a), I then arrive in a similar looking room and I break again my number, leave the right part on the floor, go down and repeat until I have no number anymore in my hand. This explanation along with the figure you provided are very helpful. Thanks so much for taking the time to explain, in very clear terms, the method you've used here. I feel like it's a very useful tool that even I can grasp. I'm sure there are many nuances to work out, but for now I'll look for some series problems where I'm eager to apply it. Again, many thanks for an excellent explanation. I know it was time consuming for you to format and share. Brad 

09012017, 09:12 PM
Post: #33




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
Here's a recursive version. The recursive program is stored in the local ←P variable. It finds the 50th number in 0.23s and the 1E6'th in 0.77s on a 50g.
Code: « 

09022017, 06:51 AM
Post: #34




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits  
« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)