

Definitions

The   fusc   integer sequence is defined as:

   fusc(0) = 0
   fusc(1) = 1
   for n>1,   the   nth   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   (named by Dijkstra, 1982)
   Stern's Diatomic series   (although it starts with unity, not zero)
   Stern-Brocot sequence   (although it starts with unity, not zero)


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 decimal digits when the fusc number is expressed in base ten.)
   show all numbers with commas   (if appropriate).
   show all output here.


Related task

   RosettaCode Stern-Brocot sequence


Also see

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


\ Gforth 0.7.9_20211014
 
: fusc ( n -- n)                     \  input n -- output fusc(n)
  dup  dup  0= swap  1 = or          \  n = 0 or 1
  if  exit                           \  return n
  else dup 2 mod 0=                  \  test even
       if 2/ recurse                 \  even fusc(n)= fusc(n/2)
       else dup  1- 2/ recurse       \  odd  fusc(n) = fusc((n-1)/2) +
            swap 1+ 2/ recurse  +    \                 fusc((n+1)/2)
       then
  then
;
 
: cntDigits ( n -- n )               \ returns the numbers of digits
  0 begin 1+ swap
        10 /
        swap  over
  0= until
  swap drop
;
 
: fuscLen ( n -- )                    \ count until end index
  cr 1   swap  0
  do
    i fusc cntDigits
    over > if 1+
                  ." fusc( " i . ." ) : "
                  i fusc  . cr
           then
  loop
;
 
: firstFusc ( n -- )                  \ show  fusc(i)   until  limit
   dup ." First " . ." fusc(n) : " cr
   0 do  I fusc .  loop cr
;
 
61 firstFusc
 
20 1000 1000 * * fuscLen
 
bye
 