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

[Werner]

An iterative version (even if I favour the recursive one)
For the 49 and up, replace / IP by IQUOT

Code:

\<<
    0 SWAP
    DO
      1 - DUP 5 MOD DUP + 1 +
      ROT 1 + ROT 5 / IP
    UNTIL DUP NOT
    END
    1 ROT START 10 * + NEXT
\>>

Cheers, Werner

[Gerald H]

Slightly shorter version of Werner's programme:

Code:

« "" SWAP
  DO 1 - DUP 5 MOD
DUP + 1 + ROT +
SWAP 5 IQUOT DUP
NOT
  UNTIL
  END DROP OBJ→
»

[Claudio L.]

(08-30-2017 12:20 PM)Werner Wrote:  An iterative version (even if I favour the recursive one)
For the 49 and up, replace / IP by IQUOT

Code:

\<<
    0 SWAP
    DO
      1 - DUP 5 MOD DUP + 1 +
      ROT 1 + ROT 5 / IP
    UNTIL DUP NOT
    END
    1 ROT START 10 * + NEXT
\>>

Cheers, Werner

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:

\<<
    0 SWAP
    DO
      1 - 5 IDIV2 DUP + 1 +
      ROT 1 + ROT 
    UNTIL DUP NOT
    END
    1 ROT START 10 * + NEXT
\>>

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.

[Werner]

I forgot about IDIV2 ;-)
And all the credit goes to Didier Lachieze, of course, the algorithm is the same.
Werner

[Claudio L.]

(08-30-2017 01:02 PM)Gerald H Wrote:  Slightly shorter version of Werner's programme:

Code:

« "" SWAP
  DO 1 - DUP 5 MOD
DUP + 1 + ROT +
SWAP 5 IQUOT DUP
NOT
  UNTIL
  END DROP OBJ→
»

Even shorter when you use IDIV2:

Code:

« "" SWAP
  DO 1 - 5 IDIV2
DUP + 1 + ROT +
SWAP DUP
NOT
  UNTIL
  END DROP OBJ→
»

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.

[Gerald H]

Not as elegant & larger but quicker:

Code:

« "" SWAP 0. OVER
I→R LN
1.60943791243 / .1
-
  START 1 - 5 IDIV2
DUP + 1 + ROT +
SWAP
  NEXT DROP OBJ→
»

[Gerald H]

(08-30-2017 02:08 PM)Claudio L. Wrote:  

(08-30-2017 01:02 PM)Gerald H Wrote:  Slightly shorter version of Werner's programme:

Code:

« "" SWAP
  DO 1 - DUP 5 MOD
DUP + 1 + ROT +
SWAP 5 IQUOT DUP
NOT
  UNTIL
  END DROP OBJ→
»

Even shorter when you use IDIV2:

Code:

« "" SWAP
  DO 1 - 5 IDIV2
DUP + 1 + ROT +
SWAP DUP
NOT
  UNTIL
  END DROP OBJ→
»

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.

For a version of this programme in Sys RPL see

http://www.hpmuseum.org/forum/thread-8941.html

[Brad Barton]

(08-29-2017 04:02 PM)Didier Lachieze Wrote:  My RPL is a bit rusty, so instead here is an HP Prime program:

Code:

EXPORT IntOdd(N)  
BEGIN  
    10*IFTE(N<=5,0,IntOdd(IP((N-1)/5)))+2*((N-1) MOD 5)+1;
END;

IntOdd(50) returns 179 in 0.5ms on my Prime.

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 self-referenced 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/digit-checking 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

[pier4r]

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:


OEISA014261
  @see www.hpmuseum.org/forum/thread-8928.html
  @in practice we should generate all the positive integers not containing
  @even digits.
  @Those small challenegs are nice because are not overwhelming and still can be
  @approached in many ways.
  
  @listExt of DavidM
  @LSORT from hpcalc
  \<<
    @Input: N
    @Output: Nth number in the sequence.
  
    @Plan
    @ combining digits 1 3 5 7 9 in increasing way.
    
    @so making heavy use of the awesome list library of david.
    @I can just generate tuples and sort them.
    
    { 1 3 5 7 9 } "baseList" DROP
    { } "currentIterBaseList" DROP
    {} "currentIterationList" DROP
    1 "digitsInIteration" DROP
    0 "mthGeneratedNumber" DROP
    0 "skippedNumbers" DROP
    
    \->
    @input
    valueN
    
    @local var
    baseList
    currentIterBaseList
    currentIterationList
    digitsInIteration
    mthGeneratedNumber
    skippedNumbers
    \<<
      IF
        valueN 1 > NOT
      THEN
        0
      ELSE
        WHILE
          valueN 5 digitsInIteration ^
          >
        REPEAT
          'skippedNumbers' 5 digitsInIteration ^ STO+
          'digitsInIteration' 1 STO+
        END

        @generate a source list with enough digits 
        @(small limits of the current version of the list library of davidM)
        @in general to generate 111 we need 3 "1" in the list, so
        baseList digitsInIteration LMRPT 'currentIterBaseList' STO
          @can we use sorted? so we have the numbers generated in order?
          @nu. Generating a list from sorted input list and then removing duplicates
          @does not help. This may be a request for another command similar to DOPERM
        
        @generate all the permutations of the elements, turn them in numbers
        @clear the equal ones
        currentIterBaseList digitsInIteration 
        \<< NL\->I \>> 
        DOPERM
        LDDUP
        :2:LSORT EVAL
        
        @then we pick the right element
        valueN skippedNumbers -
        GET
      END
    \>>
  \>>

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

[pier4r]

(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):

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.

[Brad Barton]

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

[David Hayden]

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:

«
  «
  1 -
  IF DUP 4 >
  THEN
    5 IDIV2 SWAP ←P EVAL @ Get the value for N/5
  ELSE
    0
  END
  10 * @ 10 * F(N/5)
  SWAP 2 * 1 +  @ F(N % 5)
  +
  » → ←P « ←P EVAL »
»

[Didier Lachieze]

(09-01-2017 02:55 PM)Brad Barton Wrote:  Again, many thanks for an excellent explanation. I know it was time consuming for you to format and share.
Brad

My pleasure. I've learned so much from the brilliant people on this forum that I'm glad if I can contribute a little bit.