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

08282017, 02:21 PM
(This post was last modified: 08282017 02:22 PM by Gerald H.)
Post: #1




HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
Challenge is to write a fast User RPL programme to reproduce this series:
ie for input N returns Nth element of the sequence. https://oeis.org/A014261 which begins 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 31, 33, 35, 37, 39, 51, 53, 55, 57, 59, 71, 73, 75, 77, 79, 91, 93, 95, 97, 99, 111, 113, 115, 117, 119, 131, 133, 135, 137, 139, 151, 153, 155, 157, 159, 171, 173, 175, 177, 179, 191, 193, 195, 197, 199, 311 so you can imagine how it continues. The smaller the programme the better, but irrelevant for judgment of best programme, except in the case of a tie in speed. 

08282017, 04:21 PM
Post: #2




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
Nice one (I see that you are coming from the post in the software library).
I'll try as soon as I have time with lists/strings (and I'll integrate it as list challenge as well) since the library of David should have some neat command for this. Wikis are great, Contribute :) 

08282017, 10:07 PM
(This post was last modified: 08282017 10:09 PM by Claudio L..)
Post: #3




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
sabotaging your own challenge? or providing a reference implementation to compare?
EDIT: Nevermind, Pier beat me to it. 

08292017, 05:44 AM
Post: #4




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
No, not sabotage, perhaps assistance.
http://www.hpmuseum.org/forum/thread8922.html After all, if the evens are so easy mustn't the odds be easy too? 

08292017, 07:36 AM
Post: #5




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
(08292017 05:44 AM)Gerald H Wrote: After all, if the evens are so easy mustn't the odds be easy too? I have an idea (a bit clumsy) but yesterday I was too tired. I'll try tonight. Wikis are great, Contribute :) 

08292017, 08:06 AM
Post: #6




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
Seems like counting in base 5.
Beside the fun aspect, does this suite have any actual math usage? 

08292017, 09:23 AM
(This post was last modified: 08292017 09:49 AM by Gerald H.)
Post: #7




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
Just to start the ball rolling here my current attempt
Code: « DUP 1 < CKSUM ABED SIZE 228. TIMING: INPUT 50 TAKES 6 SECONDS TO RETURN 179 Edit: Sorry, not 6s but 18.3s 

08292017, 10:48 AM
Post: #8




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
(08292017 08:06 AM)Tugdual Wrote: Seems like counting in base 5. Exactly, but I have some edge cases (with 99, 199 and so on) that are unresolved. Just, I need time. This is also a great (a) list challenge and (b) string challenge, I'll include it in the other threads as soon as I solve it a bit. Wikis are great, Contribute :) 

08292017, 01:07 PM
Post: #9




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
A bit different than the actual challenge, this program returns all 155 numbers < 1000 in about 68 seconds. Requires DavidM's ListExt library and GoferLists.
Code: \<< 1 999 1 Seq John 

08292017, 04:02 PM
Post: #10




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
My RPL is a bit rusty, so instead here is an HP Prime program:
Code: EXPORT IntOdd(N) IntOdd(50) returns 179 in 0.5ms on my Prime. 

08292017, 04:29 PM
Post: #11




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: Very nice, Didier. Ihave translated the programme to the 49G thus: Code: INTODD which I trust meets with your approval. Time on 49G for input 50 is 0.81s & all answers have so far been correct. At the moment you lead the field. Bravo! 

08292017, 05:55 PM
(This post was last modified: 08292017 05:56 PM by Gerald H.)
Post: #12




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
But maybe I'm unfair to Didier, for if this is his programme
Code:
the 49G takes 0.33s for input 50. 

08292017, 07:08 PM
Post: #13




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
(08292017 01:07 PM)John Keith Wrote: A bit different than the actual challenge, this program returns all 155 numbers < 1000 in about 68 seconds. Requires DavidM's ListExt library and GoferLists. This would be likely one of the best solution as "list processing challenge". Wikis are great, Contribute :) 

08292017, 08:28 PM
(This post was last modified: 08292017 10:11 PM by Claudio L..)
Post: #14




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
My take:
Code:
168 bytes on newRPL (can somebody test this on userRPL?) Returns a(10^6) = 335777779 as per the original sequence link, so I think it's correct. Does 1000 runs with 1e6 as argument in 0.953 seconds (<< 1 1000 START 1E6 NODD NEXT >>). Would be nice if somebody can measure in userRPL. EDIT: For comparison, with 50 as argument it returns 179, and does 1000 runs in 0.603 seconds. ** EDIT AGAIN **: I got caught by my own design :), turns out newRPL runs at 6MHz the first 300 msec, therefore doing 1000 runs is not representative of the true speed. Another run now with 50000 times took 7.94 seconds, so roughly it takes 0.16 msec to compute with an argument of 50, and 0.45 msec with an argument of 1e6. 

08292017, 09:14 PM
(This post was last modified: 08292017 09:40 PM by Gilles59.)
Post: #15




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: Your RPL is not so bad : Code: 'IntOdd(n)=10*IFTE(n<=5,0,IntOdd(IP((n1)/5)))+2*((n1) MOD 5)+1' Works fine but this recursive approach is slow with the HP50G 

08292017, 09:56 PM
(This post was last modified: 08292017 10:00 PM by Claudio L..)
Post: #16




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
(08292017 08:28 PM)Claudio L. Wrote: (can somebody test this on userRPL?) I finally was able to take my other 50g with stock firmware and here it is: Compiled in approx. mode, with dots on all numbers: 156 bytes Does 100 runs with 50 as argument in 23.8 seconds Compiled in exact mode, without any dots: 148 bytes 24.2 seconds for 100 rounds. PS: A pure stack version can probably cut this time in half on userRPL... 

08302017, 01:19 AM
Post: #17




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
(08292017 09:14 PM)Gilles59 Wrote: Works fine but this recursive approach is slow with the HP50G Are you sure? It seems blazingly fast to me: 5^191 INTODD > 7777777777777777777 in 2.48 seconds! <0ɸ0> Joe 

08302017, 09:06 AM
(This post was last modified: 08302017 09:06 AM by pier4r.)
Post: #18




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
So I have in mind two approaches (way poorer than the approaches already posted)
 one that is simulating exactly how the sequence is create through keeping which number is in which position. For example given the list { 1 3 5 7 9 } 37 > { 2 4 } > (1st digit from the left, pick the second element, 2nd digit from the left, pick the 4th element) Then I increment the list and I get { 2 5 } that is equal to 39. Then the next increment would lead to { 3 1 } and so on. this of course would be pretty slow but it should work. (and as you can see, it is like list processing)  the other idea is to get the Nth number, convert it in base 5. And then substitute the digits (having the number seen as string) with a mapping. So for example: 13th number, in base 5 it is 23, substitute 2 with 3 (2nd element in the list) and 3 with 5 (5th element in the list). So I get 35. (as you can see, it is like string processing) This may be slow but it is more interesting for me. I am trying to get it work but still I have problems with placing the 9 instances, because every time I have a carry with that. Lesson learned from this challenge: while others may find very nice math relationships or algorithms, trying to follow an idea that is neither small nor fast but interesting may be enough for personal experience. An idea that exists because the challenge was posed, so great input! Thanks Gerald. (this also slows down other projects where I am committed, damn me and my "let's do it!" approach) Wikis are great, Contribute :) 

08302017, 10:53 AM
Post: #19




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
(08302017 09:06 AM)pier4r Wrote:  the other idea is to get the Nth number, convert it in base 5. And then substitute the digits (having the number seen as string) with a mapping. So for example: I had initially the same idea but failed to implement it, for example the 24th number is 77, 24 in base 5 is 44 so you can easily convert it to 77, however if you look at the next one, the 25th should be 79 but 25 in base 5 is 100 and you start to have issues to convert that to 79… 

08302017, 10:59 AM
(This post was last modified: 08302017 12:35 PM by pier4r.)
Post: #20




RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
(08302017 10:53 AM)Didier Lachieze Wrote: I had initially the same idea but failed to implement it, for example the 24th number is 77, 24 in base 5 is 44 so you can easily convert it to 77, however if you look at the next one, the 25th should be 79 but 25 in base 5 is 100 and you start to have issues to convert that to 79… Indeed I am blocked by those. Not yet solved but still I do not feel defeated. When I feel defeated, I ask for help normally and if the help is not available I return on the problem in some time. In this case there are plenty of solutions in this thread already. Wikis are great, Contribute :) 

« Next Oldest  Next Newest »

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