Programming puzzle: Longest list of regular numbers?

[pier4r]

@Han, nice. But I do not see RPL or RPN keystroke programmign on the list! (neither casio basic, ti basic, ti lua ), time to fix it! Sure one can adapt algorithms.

(04-16-2017 09:05 PM)e_emil Wrote:  Challenge 2 - solved in 334 seconds on a 50g

According to my program, the 1429th number is 604661760

You algorithm is very interesting, I adapted one using the known algorithm how to solve it and still it is slower than yours (I'm not sure how much does it cost to put all the numbers in a list though).

378 seconds for 1429 numbers.

For the ti nspire I saw that you used Ti basic, have you tried with Lua? Should be a bit faster and more capable.

Edit_note: I wanted to put the list of 1429 numbers in a GROB and then print it, but the 50g does not have enough memory.

code for 50g.

Code:


  regNumC2v3
  @ using known algorithm
  @ not so original but goot to understand refined solutions if one does not
  @ find them by themselves.
  @ See Dijkstra
  @ www.reddit.com/r/dailyprogrammer/comments/60b63i/weekly_27_mini_challenges/df6hd31/
  @ the idea is that a "tree" is built, with branches emanating from 2,3 and 5.
  @ and since it is a tree, the branch emanates from the last useful value used by a
  @ certain factor. For more info, see the clues above.
  
  @ 141 seconds for 600 numbers
  @ 378 seconds for 1429 numbers.
  \<<
    @the idea using factors seems smarter than basic division, but it is not easy
    @to formalize, so for the moment, basic divisions or checking factors every time.
    
    1 @twoStackLvl
    1 @threeStackLvl
    1 @fiveStackLvl
    0 @newValue
    0 @numFound
    10 @uFbreak
    11 @uFbool
    \->
    @input
    upperLimit
    @local var
    twoStackLvl
    threeStackLvl
    fiveStackLvl
    newValue
    numFound
    uFbreak
    \<-uFbool
    \<<
      @TODO: save and restore flags.
    
      -3 SF
      -105 SF
        @faster with reals instead of exact mode.
    
      1
        @starting value on the stack
    
      WHILE
        numFound upperLimit <
      REPEAT
        
        @building the next regular number
        twoStackLvl PICK 2 *
        threeStackLvl 1 + PICK 3 *
          @ we need to compensate for the number just added on the stack
        MIN
        fiveStackLvl 1 + PICK 5 *
          @ we need to compensate for the number just added on the stack
        MIN
        
        DUP 'newValue' STO
        
        @ now the next regular number is on the stack
        @ so we need to update the values, especially
        @ stack pointers because everything is lifted by one.
        1 'numFound' STO+
        1 'twoStackLvl' STO+
        1 'threeStackLvl' STO+
        1 'fiveStackLvl' STO+
        
        @now we update the last usable value for the branches
        @relative to every factor compared to the last value
        twoStackLvl PICK 2 * newValue \<= 
        \<< 'twoStackLvl' 1 STO- \>>
        IFT
        
        threeStackLvl PICK 3 * newValue \<= 
        \<< 'threeStackLvl' 1 STO- \>>
        IFT
        
        fiveStackLvl PICK 5 * newValue \<= 
        \<< 'fiveStackLvl' 1 STO- \>>
        IFT
      END
      
      @create a list with the result.
      numFound \->LIST
    \>>
  \>>