HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's & 0's

[John Keith]

Hi Gerald,

Thanks for posting this intriguing challenge.

Here is my attempt which returns a list of A004290(n) from 0 to n. It will only work on numbers up to 98 because A(99) has more than 12 digits. I opted to use approximate numbers because MOD is slow for exact integers and R->B is limited to 12 digits anyway.

The program is still not very fast, taking almost 10 minutes for an input of 98. It could be extended to larger input values with exact integers and some ListExt commands but it would be slower still.

Update: I tried an exact integer version for A(99) and it ran for over 10 minutes on EMU48 without completing. I don't think that my program is incorrect since it worked on smaller numbers.

I then ran Chai Wah Wu's Python program from the OEIS page and it returned A(99) in less than one second. I then tried A(9990) on the Python program and it took over 15 minutes to complete.

I therefor conclude that numbers above 98 are impractical on the HP49/50 without a faster algorithm.

Code:


@ spoiler alert!










\<< PUSH BIN I\->R \-> n
  \<< 0. 1. 2. n
    FOR k 1. 4095.
      FOR m m R\->B \->STR 3. OVER SIZE
1. - SUB OBJ\-> DUP k MOD
        IF NOT
        THEN 4096. 'm' STO
        ELSE DROP
        END
      NEXT
    NEXT n 1. + \->LIST POP
  \>>
\>>