Fusc sequence

Fusc sequence is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Definitions

The   fusc   integer sequence is defined as:

•   fusc(0) = 0
•   fusc(1) = 1
•   for n>1,   the   n^th   term is defined as:

•   if   n   is even;     fusc(n) = fusc(n/2)
•   if   n   is  odd;     fusc(n) = fusc((n-1)/2)   +   fusc((n+1)/2)

Note that MathWorld's definition starts with unity, not zero.   this task will be using the OEIS' version   (above).

An observation

•   fusc(A) = fusc(B)

where   A   is some non-negative integer expressed in binary,   and where   B   is the binary value of   A   reversed.

Fusc numbers are also known as:

•   fusc function   (by Dijkstra, 1982)
•   Stern's Diatomic series
•   Stern-Brocot sequence

Task

•   show the first   61   fusc numbers (starting at zero) in a horizontal format.
•   show the fusc number (and its index) whose length is greater than any previous fusc number length.

•   (the length is the number of digits when the fusc number is expressed in decimal.)

•   show all numbers with commas   (if appropriate).
•   show all output here.

Also see

•   the MathWorld entry:   Stern's Diatomic Series.
•   the OEIS entry:   A2487.

REXX

<lang rexx>/*REXX program calculates and displays the fusc (or Stern's Diatomic) sequence. */ parse arg LO HI xw . /*obtain optional arguments from the CL*/ if LO== | LO=="," then LO= 0 /*Not specified? Then use the default.*/ if HI== | HI=="," then HI= 61 /* " " " " " " */ if xw== | xw=="," then xw= 0 /* " " " " " " */ list= xw<1 /*boolean value: LIST to show numbers*/ @.=; @.0= 0; @.1= 1 /*assign array default; assign low vals*/ mL= 0 /*the maximum length (digits) so far. */ $= /* " list of fusc numbers " " */

  do j=0  for HI+1                              /*process a bunch of integers from zero*/
  if j>1  then if j//2  then do;  _= (j-1) % 2;   p= (j+1) % 2;   @.j= @._ + @.p;   end
                        else do;  _= j % 2;                       @.j= @._;         end
  if list  then if j>=LO  then $= $ commas(@.j)                      /*add it to a list*/
                          else nop
           else do;   if length(@.j)<=mL  then iterate               /*still too small.*/
                      mL= length(@.j)                                /*found increase. */
                      if mL==1  then say '═══index═══   ═══fusc number═══'
                      say right( commas(j), 9)     right( commas(@.j), 14)
                      if mL==xw  then leave     /*Found max length?  Then stop looking.*/
                end                             /* [↑]  display fusc #s of maximum len.*/
  end   /*j*/

if $\== then say strip($) /*display a horizontal list of fusc #s.*/ exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg _; do c=length(_)-3 to 1 by -3; _=insert(',', _, c); end; return _</lang>

output   when using the default inputs:

0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 1 6 5 9 4 11 7 10 3 11 8 13 5 12 7 9 2 9 7 12 5 13 8 11 3 10 7 11 4 9

output   when using the inputs of:     0   999999999   5

═══index═══   ═══fusc number═══
        0              0
       37             11
    1,173            108
   35,499          1,076
  699,051         10,946