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


import strutils
 
func insequence(n: Positive): bool =
  ## Return true if "n" is in the sequence.
  if n < 10: return true
  var diff = 0
  var prev = n mod 10
  var n = n div 10
  while n != 0:
    let digit = n mod 10
    if digit < prev: inc diff
    elif digit > prev: dec diff
    prev = digit
    n = n div 10
  result = diff == 0
 
iterator a297712(): (int, int) =
  ## Yield the positions and the numbers of the sequence.
  var n = 1
  var pos = 0
  while true:
    if n.insequence:
      inc pos
      yield (pos, n)
    inc n
 
echo "First 200 numbers in the sequence:"
for (pos, n) in a297712():
  if pos <= 200:
    stdout.write ($n).align(3), if pos mod 20 == 0: '\n' else: ' '
  elif pos == 10_000_000:
    echo "\nTen millionth number in the sequence: ", n
    break