When a number is written in base 10,   adjacent digits may "rise" or "fall" as the number is read   (usually from left to right).



Definition

Given the decimal digits of the number are written as a series   d:

   A   rise   is an index   i   such that    d(i)  <  d(i+1)
   A   fall    is an index   i   such that    d(i)  >  d(i+1)


Examples

   The number   726,169   has   3   rises and   2   falls,   so it isn't in the sequence.
   The number     83,548   has   2   rises and   2   falls,   so it   is   in the sequence.


Task

   Print the first   200   numbers in the sequence 
   Show that the   10 millionth   (10,000,000th)   number in the sequence is   41,909,002


See also

   OEIS Sequence  A296712   describes numbers whose digit sequence in base 10 have equal "rises" and "falls".


Related tasks

   Esthetic numbers


      PROGRAM A296712
          INTEGER IDX, NUM, I
*         Index and number start out at zero
          IDX = 0
          NUM = 0 
*         Find and write the first 200 numbers
          WRITE (*,'(A)') 'The first 200 numbers are: '
          DO 100 I = 1, 200
              CALL NEXT NUM(IDX, NUM)
              WRITE (*,'(I4)',ADVANCE='NO') NUM
              IF (MOD(I,20).EQ.0) WRITE (*,*)
  100     CONTINUE
*         Find the 10,000,000th number
          WRITE (*,*)
          WRITE (*,'(A)',ADVANCE='NO') 'The 10,000,000th number is: '
  200     CALL NEXT NUM(IDX, NUM)
          IF (IDX.NE.10000000) GOTO 200
          WRITE (*,'(I8)') NUM
          STOP
      END    
 
*     Given index and current number, retrieve the next number
*     in the sequence.
      SUBROUTINE NEXT NUM(IDX, NUM) 
          INTEGER IDX, NUM
          LOGICAL IN SEQ
  100     NUM = NUM + 1
          IF (.NOT. IN SEQ(NUM)) GOTO 100
          IDX = IDX + 1           
      END
 
*     See whether N is in the sequence
      LOGICAL FUNCTION IN SEQ(N)
          INTEGER N, DL, DR, VAL, HEIGHT
*         Get first digit and divide value by 10
          DL = MOD(N, 10)
          VAL = N / 10
          HEIGHT = 0
  100     IF (VAL.NE.0) THEN
*             Retrieve digits by modulo and division
              DR = DL
              DL = MOD(VAL, 10)
              VAL = VAL / 10
*             Record rise or fall
              IF (DL.LT.DR) HEIGHT = HEIGHT + 1
              IF (DL.GT.DR) HEIGHT = HEIGHT - 1
              GOTO 100
          END IF
*         N is in the sequence if the final height is 0
          IN SEQ = HEIGHT.EQ.0
          RETURN
      END 