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

[Gerald H]

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.

[pier4r]

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.

[Claudio L.]

sabotaging your own challenge? or providing a reference implementation to compare?

EDIT: Nevermind, Pier beat me to it.

[Gerald H]

No, not sabotage, perhaps assistance.

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

After all, if the evens are so easy mustn't the odds be easy too?

[pier4r]

(08-29-2017 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.

[Tugdual]

Seems like counting in base 5.
Beside the fun aspect, does this suite have any actual math usage?

[Gerald H]

Just to start the ball rolling here my current attempt

Code:

« DUP 1 <
  IF
  THEN DROP 0
  ELSE 1
    « DUP 10 MOD 9 <
      IF
      THEN DUP 2 MOD +
      ELSE 10 IQUOT ←G EVAL 10 *
      END 1 +
    »
    « OVER 1 ==
      IF
      THEN NIP
      ELSE SWAP 1 - SWAP ←G EVAL ←H EVAL
      END
    »  → ←G ←H
    « ←H EVAL
    »
  END
»

CKSUM ABED

SIZE 228.

TIMING:

INPUT 50 TAKES 6 SECONDS TO RETURN 179
Edit: Sorry, not 6s but 18.3s

[pier4r]

(08-29-2017 08:06 AM)Tugdual Wrote:  Seems like counting in base 5.
Beside the fun aspect, does this suite have any actual math usage?

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.

[John Keith]

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
    \<< I\->NL LPROD 2 MOD 
    />> Filter
\>>

John

[Didier Lachieze]

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.

[Gerald H]

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

Very nice, Didier.

Ihave translated the programme to the 49G thus:

Code:

INTODD

« → N
  « N 5 ≤
    IF
    THEN 0
    ELSE N 1 - 5
IQUOT INTODD
    END 10 * 1 + N
1 - 5 MOD 2 * +
  »
»

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!

[Gerald H]

But maybe I'm unfair to Didier, for if this is his programme

Code:


NINTODD

« → N
  « N 5. ≤
    IF
    THEN 0.
    ELSE N 1. - 5.
/ IP NINTODD
    END 10. * 1. +
N 1. - 5. MOD 2. *
+
  »
»

the 49G takes 0.33s for input 50.

[pier4r]

(08-29-2017 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.

Code:

\<< 1 999 1 Seq
    \<< I\->NL LPROD 2 MOD 
    />> Filter
\>>

John

This would be likely one of the best solution as "list processing challenge".

[Claudio L.]

My take:

Code:


«
  1 10 → 
    RES M « 1 - DUP 2
    * 'RES' STO+ WHILE
    DUP 5 ≥ REPEAT
      5 - 5 IQUOT DUP
      M * 'RES' STO+ 10
      'M' STO* 
    END
    DROP RES 
  »
»

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.

[Gilles59]

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

Your RPL is not so bad :

Code:

'IntOdd(n)=10*IFTE(n<=5,0,IntOdd(IP((n-1)/5)))+2*((n-1) MOD 5)+1' 
 DEFINE

Works fine but this recursive approach is slow with the HP50G

[Claudio L.]

(08-29-2017 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...

[Joe Horn]

(08-29-2017 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^19-1 INTODD --> 7777777777777777777 in 2.48 seconds!

[pier4r]

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)

[Didier Lachieze]

(08-30-2017 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:
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)

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…

[pier4r]

(08-30-2017 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.