user
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   (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
:   * Stern-Brocot sequence
    * Calkin-Wilf sequence.

Also see
:   :   * the MathWorld entry:   Stern's Diatomic Series.
        * the OEIS entry:   A2487.
assistant
(formerly Perl 6)

### Recurrence

```
my @Fusc = 0, 1, 1, { |(@Fusc[$_ - 1] + @Fusc[$_], @Fusc[$_]) given ++$+1 } ... *;

sub comma { $^i.flip.comb(3).join(',').flip }

put "First 61 terms of the Fusc sequence:\n{@Fusc[^61]}" ~
    "\n\nIndex and value for first term longer than any previous:";

for flat 'Index', 'Value', 0, 0, (1..4).map({
    my $l = 10**$_;
    @Fusc.first(* > $l, :kv).map: &comma
  }) -> $i, $v {
      printf "%15s : %s\n", $i, $v
}

```

Output:

```
First 61 terms of the Fusc sequence:
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

Index and value for first term longer than any previous:
          Index : Value
              0 : 0
             37 : 11
          1,173 : 108
         35,499 : 1,076
        699,051 : 10,946

```

### Recursive

Alternative version using Raku's multiple-dispatch feature. This version is significantly slower than the one above, but it's definitely prettier.

```
multi fusc( 0 ) { 0 }
multi fusc( 1 ) { 1 }
multi fusc( $n where $n %% 2 ) { fusc $n div 2 }
multi fusc( $n ) { [+] map *.&fusc, ( $n - 1 ) div 2, ( $n + 1 ) div 2 }
put map *.&fusc, 0..60;

```

Output:

```
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
```