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


% Find how many rises and falls a number has
rises_falls = proc (n: int) returns (int,int)
    rises: int := 0
    falls: int := 0
 
    while n >= 10 do
        dl: int := n//10
        n := n / 10
        dh: int := n//10
        if dh < dl then rises := rises + 1
        elseif dl < dh then falls := falls + 1
        end 
    end 
    return (rises, falls)
end rises_falls
 
% Generate all numbers with equal rises and falls
equal_rises_falls = iter () yields (int)
    n: int := 1
    rises, falls: int 
    while true do
        rises, falls := rises_falls(n)
        if rises = falls then yield (n) end
        n := n + 1
    end
end equal_rises_falls
 
% Show the first 200 and the 10,000,000th
start_up = proc ()
    po: stream := stream$primary_output()
    count: int := 0
 
    for n: int in equal_rises_falls() do
        count := count + 1
        if count <= 200 then
            stream$putright(po, int$unparse(n), 5)
            if count//10 = 0 then stream$putc(po, '\n') end
        elseif count = 10000000 then
            stream$putl(po, "\nThe 10,000,000th number is: " 
                         || int$unparse(n))
            break
        end
    end
end start_up