HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
09-01-2017, 02:55 PM
Post: #32
 Brad Barton Member Posts: 194 Joined: Jan 2014
RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
(09-01-2017 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((N-1)/5) and the unit number b=(N-1) MOD 5, then I converted the unit number to the sequence 1,3,5,7,9:

Applying the offset (N-1), 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.

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.

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.