HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
09-01-2017, 07:48 AM (This post was last modified: 09-01-2017 09:28 AM by Didier Lachieze.)
Post: #30
 Didier Lachieze Senior Member Posts: 1,641 Joined: Dec 2013
RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits
(08-31-2017 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.

Kudos to you for such an elegant solution.

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)  1     1  2     3  3     5  4     7  5     9  6    11  7    13  8    15  9    17 10    19 11    31 …     …

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  1     1       1  2     3       2   3     5       3   4     7       4  5     9      10   6    11      11   7    13      12  8    15      13  9    17      14 10    19      20 11    31      21 …     …

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 (N-1)b5 :
Code:
 N    A(N)    (N-1)b5  1     1       0  2     3       1   3     5       2  4     7       3  5     9       4   6    11      10   7    13      11  8    15      12  9    17      13 10    19      14 11    31      20 …     …

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:
Code:
 N    A(N)    (N-1)b5   a  b   2*b+1  1     1       0        0  0     1  2     3       1        0  1     3    3     5       2        0  2     5   4     7       3        0  3     7  5     9       4        0  4     9  6    11      10        1  0     1  7    13      11        1  1     3  8    15      12        1  2     5  9    17      13        1  3     7 10    19      14        1  4     9 11    31      20        2  0     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 (N-1)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)   BEGIN   LOCAL a,b;     a:= IP((N-1)/5);     b:= (N-1) MOD 5;     IF (N <= 5) THEN           RETURN (2*b+1);      ELSE         RETURN (10* IntOdd(a) + 2*b+1);     END;   END;

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)   BEGIN       10*IFTE(N<=5,0,IntOdd(IP((N-1)/5)))+2*((N-1) MOD 5)+1; END;

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.

 « Next Oldest | Next Newest »

 Messages In This Thread HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - Gerald H - 08-28-2017, 02:21 PM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - pier4r - 08-28-2017, 04:21 PM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - Claudio L. - 08-28-2017, 10:07 PM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - Gerald H - 08-29-2017, 05:44 AM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - pier4r - 08-29-2017, 07:36 AM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - Tugdual - 08-29-2017, 08:06 AM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - pier4r - 08-29-2017, 10:48 AM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - Gerald H - 08-29-2017, 09:23 AM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - John Keith - 08-29-2017, 01:07 PM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - pier4r - 08-29-2017, 07:08 PM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - Didier Lachieze - 08-29-2017, 04:02 PM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - Gerald H - 08-29-2017, 04:29 PM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - Gilles59 - 08-29-2017, 09:14 PM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - Joe Horn - 08-30-2017, 01:19 AM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - Brad Barton - 08-31-2017, 12:49 PM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - Didier Lachieze - 09-01-2017 07:48 AM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - pier4r - 09-01-2017, 08:11 AM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - Brad Barton - 09-01-2017, 02:55 PM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - Didier Lachieze - 09-02-2017, 06:51 AM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - Gerald H - 08-29-2017, 05:55 PM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - Claudio L. - 08-29-2017, 08:28 PM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - Claudio L. - 08-29-2017, 09:56 PM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - pier4r - 08-30-2017, 09:06 AM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - Didier Lachieze - 08-30-2017, 10:53 AM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - pier4r - 08-30-2017, 10:59 AM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - Werner - 08-30-2017, 12:20 PM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - Gerald H - 08-30-2017, 01:02 PM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - Claudio L. - 08-30-2017, 02:08 PM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - Gerald H - 08-31-2017, 10:57 AM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - Claudio L. - 08-30-2017, 01:39 PM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - Werner - 08-30-2017, 02:06 PM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - Gerald H - 08-30-2017, 03:30 PM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - pier4r - 08-31-2017, 09:32 PM RE: HP 49G Programming Challenge: OEIS A014261, Integers with exclusively Odd Digits - David Hayden - 09-01-2017, 09:12 PM

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