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

[Didier Lachieze]

(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.

Brad

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.