I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# Fusc sequence

Fusc sequence
You are encouraged to solve this task according to the task description, using any language you may know.

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)

•   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.

Also see

## 11l

Translation of: Kotlin
`F fusc(n)   V res =  * n   res = 1   L(i) 2 .< n      res[i] = I i % 2 == 0 {res[i I/ 2]} E res[(i-1) I/ 2] + res[(i+1) I/ 2]   R res print(‘First 61 terms:’)print(fusc(61)) print()print(‘Points in the sequence where an item has more digits than any previous items:’)V f = fusc(20'000'000)V max_len = 0L(i) 0 .< f.len   I String(f[i]).len > max_len      max_len = String(f[i]).len      print((i, f[i]))`
Output:
```First 61 terms:
[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]

Points in the sequence where an item has more digits than any previous items:
(0, 0)
(37, 11)
(1173, 108)
(35499, 1076)
(699051, 10946)
(19573419, 103682)
```

`with Ada.Text_IO;with Ada.Integer_Text_IO; procedure Show_Fusc is    generic      Precalculate : Natural;   package Fusc_Sequences is      function Fusc (N : in Natural) return Natural;   end Fusc_Sequences;    package body Fusc_Sequences is       Precalculated_Fusc : array (0 .. Precalculate) of Natural;       function Fusc_Slow (N : in Natural) return Natural is      begin         if N = 0 or N = 1 then            return N;         elsif N mod 2 = 0 then            return Fusc_Slow (N / 2);         else            return Fusc_Slow ((N - 1) / 2) + Fusc_Slow ((N + 1) / 2);         end if;      end Fusc_Slow;       function Fusc (N : in Natural) return Natural is      begin         if N <= Precalculate then            return Precalculated_Fusc (N);         elsif N mod 2 = 0 then            return Fusc (N / 2);         else            return Fusc ((N - 1) / 2) + Fusc ((N + 1) / 2);         end if;      end Fusc;    begin      for N in Precalculated_Fusc'Range loop         Precalculated_Fusc (N) := Fusc_Slow (N);      end loop;   end Fusc_Sequences;     package Fusc_Sequence is      new Fusc_Sequences (Precalculate => 200_000);    function Fusc (N : in Natural) return Natural     renames Fusc_Sequence.Fusc;     procedure Print_Small_Fuscs is      use Ada.Text_IO;   begin      Put_Line ("First 61 numbers in the fusc sequence:");      for N in 0 .. 60 loop         Put (Fusc (N)'Image);         Put (" ");      end loop;      New_Line;   end Print_Small_Fuscs;     procedure Print_Large_Fuscs (High : in Natural) is      use Ada.Text_IO;      use Ada.Integer_Text_IO;      subtype N_Range is Natural range Natural'First .. High;      F       : Natural;      Len     : Natural;      Max_Len : Natural := 0;      Placeholder : String := "       n      fusc(n)";      Image_N     : String renames Placeholder (1  .. 8);      Image_Fusc  : String renames Placeholder (10 .. Placeholder'Last);   begin      New_Line;      Put_Line ("Printing all largest Fusc numbers upto " & High'Image);      Put_Line (Placeholder);       for N in N_Range loop         F   := Fusc (N);         Len := F'Image'Length;           if Len > Max_Len then             Max_Len := Len;             Put (Image_N,    N);             Put (Image_Fusc, F);             Put (Placeholder);             New_Line;          end if;       end loop;   end Print_Large_Fuscs; begin   Print_Small_Fuscs;   Print_Large_Fuscs (High => 20_000_000);end Show_Fusc;`
Output:
```First 61 numbers in 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

Printing all largest Fusc numbers upto  20000000
n      fusc(n)
0            0
37           11
1173          108
35499         1076
699051        10946
19573419       103682```

## ALGOL 68

`BEGIN    # calculate some members of the fusc sequence              #    #    f0 = 0, f1 = 1, fn = f(n/2)                 if n even #    #                       = f(n-1)/2) + f((n+1)/2) if n odd  #     # constructs an array of the first n elements of the fusc sequence #    PROC fusc sequence = ( INT n )[]INT:         BEGIN            [ 0 : n ]INT a;            IF n > 0 THEN                a[ 0 ] := 0;                IF n > 1 THEN                    a[ 1 ] := 1;                    INT i2 := 1;                    FOR i FROM 2 BY 2 TO n - 1 DO                        a[ i     ] := a[ i2 ];                        a[ i + 1 ] := a[ # j - i # i2 ] + a[ # ( j + 1 ) OVER 2 # i2 + 1 ];                        i2 +:= 1                    OD                FI            FI;            a[ 0 : n - 1 AT 0 ]         END ; # fusc #     []INT f = fusc sequence( 800 000 );    FOR i FROM 0 TO 60 DO print( ( " ", whole( f[ i ], 0 ) ) ) OD;    print( ( newline ) );    # find the lowest elements of the sequence that have 1, 2, 3, etc. digits #    print( ( "Sequence elements where number of digits of the value increase:", newline ) );    print( ( "       n    fusc(n)", newline ) );    INT digit power := 0;    FOR i FROM LWB f TO UPB f DO        IF f[ i ] >= digit power THEN            # found the first number with this many digits #            print( ( whole( i, -8 ), " ", whole( f[ i ], -10 ), newline ) );            IF digit power = 0 THEN digit power := 1 FI;            digit power *:= 10        FI    ODEND`
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
Sequence elements where number of digits of the value increase:
n    fusc(n)
0          0
37         11
1173        108
35499       1076
699051      10946
```

## AppleScript

`on fusc(n)    if (n < 2) then        return n    else if (n mod 2 is 0) then        return fusc(n div 2)    else        return fusc((n - 1) div 2) + fusc((n + 1) div 2)    end ifend fusc set sequence to {}set longestSoFar to 0repeat with i from 0 to 60    set fuscNumber to fusc(i)    set end of sequence to fuscNumber    set len to (count (fuscNumber as text))    if (len > longestSoFar) then        set longestSoFar to len        set firstLongest to fuscNumber        set indexThereof to i + 1 -- AppleScript indices are 1-based.    end ifend repeat return {sequence:sequence, firstLongest:firstLongest, indexThereof:indexThereof}`
Output:
`{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}, firstLongest:11, indexThereof:38}`

Or defining generators, both for a non-finite stream of Fusc terms, and for the sequence of the first Fusc terms of each decimal magnitude:

`-- fusc :: [Int]on fusc()    -- Terms of the Fusc sequence    -- OEIS A2487     script go        on |λ|(step)            set {isEven, n, xxs} to step            set x to item 1 of xxs             if isEven then                set nxt to n + x                {not isEven, nxt, xxs & {nxt}}            else                {not isEven, x, rest of xxs & {x}}            end if        end |λ|    end script     appendGen(gen({0, 1}), ¬        fmapGen(my snd, iterate(go, {true, 1, {1}})))end fusc -------------------------- TEST ---------------------------on run    unlines({¬        "First 61 terms:", ¬        showList(take(61, fusc())), ¬        "", ¬        "First term of each decimal magnitude:", ¬        "(Index, Term):"} & ¬        map(showTuple, take(4, firstFuscOfEachMagnitude())))end run  ---------- FIRST FUSC OF EACH DECIMAL MAGNITUDE ----------- -- firstFuscOfEachMagnitude :: [(Int, Int)]on firstFuscOfEachMagnitude()    -- [(Index, Term)] list of of the first Fusc     -- terms of each decimal magnitude.    script        property e : -1        property i : 0        on |λ|()            set e to 1 + e            set p to 10 ^ e            set v to fuscTerm(i)            repeat until p ≤ v                set i to 1 + i                set v to fuscTerm(i)            end repeat            {i, v}        end |λ|    end scriptend firstFuscOfEachMagnitude  -- fuscTerm :: Int -> Inton fuscTerm(n)    -- Nth term (zero-indexed) of the Fusc series.    script go        on |λ|(i)            if 0 = i then                {1, 0}            else                set {x, y} to |λ|(i div 2)                if 0 = i mod 2 then                    {x + y, y}                else                    {x, x + y}                end if            end if        end |λ|    end script     tell go        if 1 > n then            0        else            item 1 of |λ|(n - 1)        end if    end tellend fuscTerm   -------------------- GENERIC FUNCTIONS -------------------- -- appendGen (++) :: Gen [a] -> Gen [a] -> Gen [a]on appendGen(xs, ys)    script        property vs : xs        on |λ|()            set v to |λ|() of vs            if missing value is not v then                v            else                set vs to ys                |λ|() of ys            end if        end |λ|    end scriptend appendGen  -- fmapGen <\$> :: (a -> b) -> Gen [a] -> Gen [b]on fmapGen(f, gen)    script        property g : mReturn(f)        on |λ|()            set v to gen's |λ|()            if v is missing value then                v            else                g's |λ|(v)            end if        end |λ|    end scriptend fmapGen  -- intercalate :: String -> [String] -> Stringon intercalate(delim, xs)    set {dlm, my text item delimiters} to ¬        {my text item delimiters, delim}    set s to xs as text    set my text item delimiters to dlm    send intercalate  -- iterate :: (a -> a) -> a -> Gen [a]on iterate(f, x)    script        property v : missing value        property g : mReturn(f)'s |λ|        on |λ|()            if missing value is v then                set v to x            else                set v to g(v)            end if            return v        end |λ|    end scriptend iterate  -- map :: (a -> b) -> [a] -> [b]on map(f, xs)    -- The list obtained by applying f    -- to each element of xs.    tell mReturn(f)        set lng to length of xs        set lst to {}        repeat with i from 1 to lng            set end of lst to |λ|(item i of xs, i, xs)        end repeat        return lst    end tellend map  -- mReturn :: First-class m => (a -> b) -> m (a -> b)on mReturn(f)    -- 2nd class handler function lifted into 1st class script wrapper.     if script is class of f then        f    else        script            property |λ| : f        end script    end ifend mReturn  -- gen :: [a] -> Gen aon gen(xs)    script go        property lng : length of xs        property i : 0        on |λ|()            if i ≥ lng then                missing value            else                set i to 1 + i                item i of xs            end if        end |λ|    end scriptend gen  -- showList :: [a] -> Stringon showList(xs)    "[" & intercalate(", ", my map(my str, xs)) & "]"end showList  -- showTuple :: (,) -> Stringon showTuple(xs)    "(" & intercalate(", ", my map(my str, xs)) & ")"end showTuple  -- snd :: (a, b) -> bon snd(tpl)    if class of tpl is record then        |2| of tpl    else        item 2 of tpl    end ifend snd  -- str :: a -> Stringon str(x)    x as stringend str  -- take :: Int -> [a] -> [a]-- take :: Int -> String -> Stringon take(n, xs)    set c to class of xs    if list is c then        if 0 < n then            items 1 thru min(n, length of xs) of xs        else            {}        end if    else if string is c then        if 0 < n then            text 1 thru min(n, length of xs) of xs        else            ""        end if    else if script is c then        set ys to {}        repeat with i from 1 to n            set v to |λ|() of xs            if missing value is v then                return ys            else                set end of ys to v            end if        end repeat        return ys    else        missing value    end ifend take  -- unlines :: [String] -> Stringon unlines(xs)    -- A single string formed by the intercalation    -- of a list of strings with the newline character.    set {dlm, my text item delimiters} to ¬        {my text item delimiters, linefeed}    set s to xs as text    set my text item delimiters to dlm    send unlines`
Output:
```First 61 terms:
[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]

First term of each decimal magnitude:
(Index, Term):
(0, 0)
(37, 11)
(1173, 108)
(35499, 1076)```

## Arturo

Translation of: Nim
`fusc: function [n][    if? or? n=0 n=1 -> n    else [        if? 0=n%2 -> fusc n/2        else -> (fusc (n-1)/2) + fusc (n+1)/2    ]] print "The first 61 Fusc numbers:"print map 0..61 => fusc print "\nThe Fusc numbers whose lengths are greater than those of previous Fusc numbers:"print "        n   fusc(n)"print "--------- ---------"maxLength: 0 loop 0..40000 'i [    f: fusc i    l: size to :string f    if l > maxLength [        maxLength: l        print [            pad to :string i 9            pad to :string f 9        ]    ]]`
Output:
```The first 61 Fusc numbers:
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

The Fusc numbers whose lengths are greater than those of previous Fusc numbers:
n   fusc(n)
--------- ---------
0         0
37        11
1173       108
35499      1076```

## AWK

` # syntax: GAWK -f FUSC_SEQUENCE.AWK# converted from CBEGIN {    for (i=0; i<61; i++) {      printf("%d ",fusc(i))    }    printf("\n")    print("fusc numbers whose length is greater than any previous fusc number length")    printf("%9s %9s\n","fusc","index")    for (i=0; i<=700000; i++) {      f = fusc(i)      leng = num_leng(f)      if (leng > max_leng) {        max_leng = leng        printf("%9s %9s\n",commatize(f),commatize(i))      }    }    exit(0)}function commatize(x,  num) {    if (x < 0) {      return "-" commatize(-x)    }    x = int(x)    num = sprintf("%d.",x)    while (num ~ /^[0-9][0-9][0-9][0-9]/) {      sub(/[0-9][0-9][0-9][,.]/,",&",num)    }    sub(/\.\$/,"",num)    return(num)}function fusc(n) {    if (n == 0 || n == 1) {      return(n)    }    else if (n % 2 == 0) {      return fusc(n/2)    }    else {      return fusc((n-1)/2) + fusc((n+1)/2)    }}function num_leng(n,  sum) {    sum = 1    while (n > 9) {      n = int(n/10)      sum++    }    return(sum)} `
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
fusc numbers whose length is greater than any previous fusc number length
fusc     index
0         0
11        37
108     1,173
1,076    35,499
10,946   699,051
```

## BQN

Works in: CBQN

`Fusc` computes fusc numbers iteratively.

`Fusc ← {  {   𝕩∾+´(⍷(⌈∾⌊)2÷˜≠𝕩)⊑¨<𝕩  }⍟(𝕩-2)↕2} •Show Fusc 61 •Show >⟨"Index"‿"Number"⟩∾{((1+↕4)⊐˜(⌊1+10⋆⁼1⌈|)¨𝕩){𝕨∾𝕨⊑𝕩}¨<𝕩} Fusc 99999`
`⟨ 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" "Number"  0       0  37      11  1173    108  35499   1076                   ┘`

## C

` #include<limits.h>#include<stdio.h> int fusc(int n){        if(n==0||n==1)                return n;        else if(n%2==0)                return fusc(n/2);        else                return fusc((n-1)/2) + fusc((n+1)/2);} int numLen(int n){        int sum = 1;         while(n>9){                n = n/10;                sum++;        }         return sum;} void printLargeFuscs(int limit){        int i,f,len,maxLen = 1;         printf("\n\nPrinting all largest Fusc numbers upto %d \nIndex-------Value",limit);         for(i=0;i<=limit;i++){                f = fusc(i);                len = numLen(f);                 if(len>maxLen){                        maxLen = len;                        printf("\n%5d%12d",i,f);                }        }}  int main(){        int i;         printf("Index-------Value");        for(i=0;i<61;i++)                printf("\n%5d%12d",i,fusc(i));        printLargeFuscs(INT_MAX);        return 0;} `

Prints first 61 Fusc numbers followed by the largest numbers :

```Index-------Value
0           0
1           1
2           1
3           2
4           1
5           3
6           2
7           3
8           1
9           4
10           3
11           5
12           2
13           5
14           3
15           4
16           1
17           5
18           4
19           7
20           3
21           8
22           5
23           7
24           2
25           7
26           5
27           8
28           3
29           7
30           4
31           5
32           1
33           6
34           5
35           9
36           4
37          11
38           7
39          10
40           3
41          11
42           8
43          13
44           5
45          12
46           7
47           9
48           2
49           9
50           7
51          12
52           5
53          13
54           8
55          11
56           3
57          10
58           7
59          11
60           4

Printing all largest Fusc numbers upto 2147483647
Index-------Value
37          11
1173         108
35499        1076
699051      10946
103682   19573419
1010747  615164587
```

## C#

`using System;using System.Collections.Generic; static class program{    static int n = 61;    static List<int> l = new List<int>() { 0, 1 };     static int fusc(int n)    {        if (n < l.Count) return l[n];        int f = (n & 1) == 0 ? l[n >> 1] : l[(n - 1) >> 1] + l[(n + 1) >> 1];        l.Add(f); return f;    }     static void Main(string[] args)    {        bool lst = true; int w = -1, c = 0, t;        string fs = "{0,11:n0}  {1,-9:n0}", res = "";        Console.WriteLine("First {0} numbers in the fusc sequence:", n);        for (int i = 0; i < int.MaxValue; i++)        {            int f = fusc(i); if (lst)            {                if (i < 61) Console.Write("{0} ", f);                else                {                    lst = false;                    Console.WriteLine();                    Console.WriteLine("Points in the sequence where an item has more digits than any previous items:");                    Console.WriteLine(fs, "Index\\", "/Value"); Console.WriteLine(res); res = "";                }            }            if ((t = f.ToString().Length) > w)            {                w = t; res += (res == "" ? "" : "\n") + string.Format(fs, i, f);                if (!lst) { Console.WriteLine(res); res = ""; } if (++c > 5) break;            }        }        l.Clear();    }}`
Output:
```First 61 numbers in 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
Points in the sequence where an item has more digits than any previous items:
Index\  /Value
0  0
37  11
1,173  108
35,499  1,076
699,051  10,946
19,573,419  103,682 ```

## C++

Translation of: C#
`#include <iomanip>#include <iostream>#include <limits>#include <sstream>#include <vector> const int n = 61;std::vector<int> l{ 0, 1 }; int fusc(int n) {    if (n < l.size()) return l[n];    int f = (n & 1) == 0 ? l[n >> 1] : l[(n - 1) >> 1] + l[(n + 1) >> 1];    l.push_back(f);    return f;} int main() {    bool lst = true;    int w = -1;    int c = 0;    int t;    std::string res;    std::cout << "First " << n << " numbers in the fusc sequence:\n";    for (int i = 0; i < INT32_MAX; i++) {        int f = fusc(i);        if (lst) {            if (i < 61) {                std::cout << f << ' ';            } else {                lst = false;                std::cout << "\nPoints in the sequence where an item has more digits than any previous items:\n";                std::cout << std::setw(11) << "Index\\" << "  " << std::left << std::setw(9) << "/Value\n";                std::cout << res << '\n';                res = "";            }        }        std::stringstream ss;        ss << f;        t = ss.str().length();        ss.str("");        ss.clear();        if (t > w) {            w = t;            res += (res == "" ? "" : "\n");            ss << std::setw(11) << i << "  " << std::left << std::setw(9) << f;            res += ss.str();            if (!lst) {                std::cout << res << '\n';                res = "";            }            if (++c > 5) {                break;            }        }    }    return 0;}`
Output:
```First 61 numbers in 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
Points in the sequence where an item has more digits than any previous items:
Index\  /Value
0  0
37  11
1173  108
35499  1076
699051  10946
19573419  103682```

## D

`import std.conv;import std.format;import std.stdio; enum n = 61;int[] l = [0, 1]; int fusc(int n) {    if (n < l.length) {        return l[n];    }    int f = (n & 1) == 0 ? l[n >> 1] : l[(n - 1) >> 1] + l[(n + 1) >> 1];    l ~= f;    return f;} void main() {    bool lst = true;    int w = -1;    int c = 0;    int t;    string fs = "%11s  %-9s";    string res = "";    for (int i = 0; i < int.max; i++) {        int f = fusc(i);        if (lst) {            if (i < 61) {                write(f, ' ');            } else {                lst = false;                writeln;                writeln("Points in the sequence where an item has more digits than any previous items:");                writefln(fs, "Index\\", "/Value");                writeln(res);                res = "";            }        }        t = f.to!string.length;        if (t > w) {            w = t;            res ~= (res == "" ? "" : "\n") ~ format(fs, i, f);            if (!lst) {                writeln(res);                res = "";            }            if (++c > 5) {                break;            }        }    }    l.length = 0;}`
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
Points in the sequence where an item has more digits than any previous items:
Index\  /Value
0  0
37  11
1173  108
35499  1076
699051  10946
19573419  103682```

See Pascal.

## F#

### The Function

` // Generate the fusc sequence. Nigel Galloway: March 20th., 2019let fG n=seq{for (n,g) in Seq.append n  |> Seq.pairwise do yield n; yield n+g}let fusc=seq{yield 0; yield! Seq.unfold(fun n->Some(n,fG n))(seq)|>Seq.concat}|> Seq.mapi(fun n g->(n,g)) `

Print first 62 elements
` fusc |> Seq.take 61 |> Seq.iter(fun(_,g)->printf "%d " g); printfn "" `
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
```
Show the fusc number (and its index) whose length is greater than any previous fusc number length

The first 6 take only 10 secs so let me be more ambitious

` let fN=let mutable n=0 in (fun (_,g)->if g>=n then n<-pown 10 (string g).Length; true else false)fusc |> Seq.filter fN |> Seq.take 7 |> Seq.iter(fun(n,g)->printfn "fusc %d -> %d" n g) `
Output:
```fusc 0 -> 0
fusc 37 -> 11
fusc 1173 -> 108
fusc 35499 -> 1076
fusc 699051 -> 10946
fusc 19573419 -> 103682
fusc 615164587 -> 1010747
Real: 00:06:03.801, CPU: 00:06:03.140, GC gen0: 21336, gen1: 0
```

## Factor

`USING: arrays assocs formatting io kernel make math math.parsermath.ranges namespaces prettyprint sequencestools.memory.private ;IN: rosetta-code.fusc <PRIVATE : (fusc) ( n -- seq )    [ 2 ] dip [a,b) [        0 , 1 , [            [ building get ] dip dup even?            [ 2/ swap nth ]            [ [ 1 - 2/ ] [ 1 + 2/ ] 2bi [ swap nth ] [email protected] + ]            if ,        ] each    ] { } make ; : increases ( seq -- assoc )    [ 0 ] dip [        [            2array 2dup first number>string length <            [ [ 1 + ] [ , ] bi* ] [ drop ] if        ] each-index    ] { } make nip ; PRIVATE> : fusc ( n -- seq )    dup 3 < [ { 0 1 } swap head ] [ (fusc) ] if ; : fusc-demo ( -- )    "First 61 fusc numbers:" print 61 fusc [ pprint bl ] each    nl nl    "Fusc numbers with more digits than all previous ones:"    print "Value   Index\n======  =======" print    1,000,000 fusc increases   [ [ commas ] [email protected] "%-6s  %-7s\n" printf ] assoc-each ; MAIN: fusc-demo`
Output:
```First 61 fusc numbers:
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

Fusc numbers with more digits than all previous ones:
Value   Index
======  =======
0       0
11      37
108     1,173
1,076   35,499
10,946  699,051
```

## FreeBASIC

`' version 01-03-2019' compile with: fbc -s console #Define max 20000000 Dim Shared As UInteger f(max) Sub fusc     f(0) = 0    f(1) = 1     For n As UInteger = 2 To max        If n And 1 Then            f(n) = f((n -1) \ 2) + f((n +1) \ 2)        Else            f(n) = f(n \ 2)        End If    Next End Sub ' ------=< MAIN >=------ Dim As UInteger i, dDim As String fs fusc For i = 0 To 60    Print f(i); " ";Next Print : PrintPrint "       Index       Value"For i = 0 To max    If f(i) >= d Then        Print Using "###########," ; i; f(i)        If d = 0 Then d = 1        d *= 10    End IfNext ' empty keyboard bufferWhile Inkey <> "" : WendPrint : Print "hit any key to end program"SleepEnd`
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

Index       Value
0           0
37          11
1,173         108
35,499       1,076
699,051      10,946
19,573,419     103,682```

## Fōrmulæ

Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition.

Programs in Fōrmulæ are created/edited online in its website, However they run on execution servers. By default remote servers are used, but they are limited in memory and processing power, since they are intended for demonstration and casual use. A local server can be downloaded and installed, it has no limitations (it runs in your own computer). Because of that, example programs can be fully visualized and edited, but some of them will not run if they require a moderate or heavy computation/memory resources, and no local server is being used.

## Go

`package main import (    "fmt"    "strconv") func fusc(n int) []int {    if n <= 0 {        return []int{}    }    if n == 1 {        return []int{0}    }        res := make([]int, n)    res = 0    res = 1    for i := 2; i < n; i++ {        if i%2 == 0 {            res[i] = res[i/2]        } else {            res[i] = res[(i-1)/2] + res[(i+1)/2]        }    }    return res} func fuscMaxLen(n int) []int {    maxLen := -1    maxFusc := -1    f := fusc(n)    var res []int    for i := 0; i < n; i++ {        if f[i] <= maxFusc {            continue // avoid expensive strconv operation where possible        }        maxFusc = f[i]        le := len(strconv.Itoa(f[i]))        if le > maxLen {            res = append(res, int{i, f[i]})            maxLen = le        }    }    return res} func commatize(n int) string {    s := fmt.Sprintf("%d", n)    if n < 0 {        s = s[1:]    }    le := len(s)    for i := le - 3; i >= 1; i -= 3 {        s = s[0:i] + "," + s[i:]    }    if n >= 0 {        return s    }    return "-" + s} func main() {    fmt.Println("The first 61 fusc numbers are:")    fmt.Println(fusc(61))    fmt.Println("\nThe fusc numbers whose length > any previous fusc number length are:")    res := fuscMaxLen(20000000)  // examine first twenty million numbers say    for i := 0; i < len(res); i++ {        fmt.Printf("%7s (index %10s)\n", commatize(res[i]), commatize(res[i]))    }}`
Output:
```The first 61 fusc numbers are:
[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]

The fusc numbers whose length > any previous fusc number length are:
0 (index          0)
11 (index         37)
108 (index      1,173)
1,076 (index     35,499)
10,946 (index    699,051)
103,682 (index 19,573,419)
```

## Groovy

Translation of: Java
`class FuscSequence {    static void main(String[] args) {        println("Show the first 61 fusc numbers (starting at zero) in a horizontal format")        for (int n = 0; n < 61; n++) {            printf("%,d ", fusc[n])        }         println()        println()        println("Show the fusc number (and its index) whose length is greater than any previous fusc number length.")        int start = 0        for (int i = 0; i <= 5; i++) {            int val = i != 0 ? (int) Math.pow(10, i) : -1            for (int j = start; j < FUSC_MAX; j++) {                if (fusc[j] > val) {                    printf("fusc[%,d] = %,d%n", j, fusc[j])                    start = j                    break                }            }        }    }     private static final int FUSC_MAX = 30000000    private static int[] fusc = new int[FUSC_MAX]     static {        fusc = 0        fusc = 1        for (int n = 2; n < FUSC_MAX; n++) {            int n2 = (int) (n / 2)            int n2m = (int) ((n - 1) / 2)            int n2p = (int) ((n + 1) / 2)            fusc[n] = n % 2 == 0                ? fusc[n2]                : fusc[n2m] + fusc[n2p]        }    }}`
Output:
```Show the first 61 fusc numbers (starting at zero) in a horizontal format
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

Show the fusc number (and its index) whose length is greater than any previous fusc number length.
fusc = 0
fusc = 11
fusc[1,173] = 108
fusc[35,499] = 1,076
fusc[699,051] = 10,946
fusc[19,573,419] = 103,682```

`fusc :: Int -> Intfusc i  | 1 > i = 0  | otherwise = fst \$ go (pred i)  where    go n      | 0 == n = (1, 0)      | even n = (x + y, y)      | otherwise = (x, x + y)      where        (x, y) = go (div n 2) widths :: [(Int, Int)]widths = (\(_, i, x) -> (i, x)) <\$> iterate nxtWidth (2, 0, 0) nxtWidth :: (Int, Int, Int) -> (Int, Int, Int)nxtWidth (w, i, v) =  let fi = (,) <*> fusc      (j, x) = until ((w <=) . length . show . snd) (fi . succ . fst) (fi i)  in (succ w, j, x) main :: IO ()main = do  putStrLn "First 61 terms:"  print \$ fusc <\$> [0 .. 60]  putStrLn "\n(Index, Value):"  mapM_ print \$ take 5 widths`
Output:
```First 61 terms:
[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, Value):
(0,0)
(37,11)
(1173,108)
(35499,1076)
(699051,10946)```

Another version using infinite list:

`zipWithLazy :: (a -> b -> c) -> [a] -> [b] -> [c]zipWithLazy f ~(x:xs) ~(y:ys) = f x y : zipWithLazy f xs ys fuscs :: [Integer]fuscs = 0 : s where  s = 1 : concat (zipWithLazy f s (tail s))  f x y = [x, x+y] widths :: [(Int, Integer)]widths = map head \$ scanl f (zip [0..] fuscs) [2..] where  f fis w = dropWhile ((< w) . length . show . snd) fis main :: IO ()main = do  putStrLn "First 61 terms:"  print \$ take 61 fuscs  putStrLn "\n(Index, Value):"  mapM_ print \$ take 5 widths`
Output:
```First 61 terms:
[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, Value):
(0,0)
(37,11)
(1173,108)
(35499,1076)
(699051,10946)
```

## J

` fusc_term =: ({~ -:@#)`([: +/ ({~ ([: -: _1 1 + #)))@.(2 | #)fusc =: (, fusc_term)@:]^:[ 0 1"_    NB. show the first 61 fusc numbers (starting at zero) in a horizontal format.   61 {. fusc 700 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!:17]2 2 NB. specify bottom right position in box    FUSC =: fusc 99999   DIGITS =: ; ([: # 10&#.inv)&.> FUSC    (;: 'index value') ,. <"0(,: {&A) DIGITS i. 1 2 3 4┌─────┬─┬──┬────┬─────┐│index│0│37│1173│35499│├─────┼─┼──┼────┼─────┤│value│0│11│ 108│ 1076│└─────┴─┴──┴────┴─────┘  `

## Java

`  public class FuscSequence {     public static void main(String[] args) {        System.out.println("Show the first 61 fusc numbers (starting at zero) in a horizontal format");        for ( int n = 0 ; n < 61 ; n++ ) {            System.out.printf("%,d ", fusc[n]);        }         System.out.printf("%n%nShow the fusc number (and its index) whose length is greater than any previous fusc number length.%n");        int start = 0;        for (int i = 0 ; i <= 5 ; i++ ) {            int val = i != 0 ? (int) Math.pow(10, i) : -1;            for ( int j = start ; j < FUSC_MAX ; j++ ) {                if ( fusc[j] > val ) {                    System.out.printf("fusc[%,d] = %,d%n", j, fusc[j] );                    start = j;                    break;                }            }        }    }     private static final int FUSC_MAX = 30000000;    private static int[] fusc = new int[FUSC_MAX];     static {        fusc = 0;        fusc = 1;        for ( int n = 2 ; n < FUSC_MAX ; n++ ) {            fusc[n] = (n % 2 == 0 ? fusc[n/2] : fusc[(n-1)/2] + fusc[(n+1)/2]);        }    }} `
Output:
```Show the first 61 fusc numbers (starting at zero) in a horizontal format
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

Show the fusc number (and its index) whose length is greater than any previous fusc number length.
fusc = 0
fusc = 11
fusc[1,173] = 108
fusc[35,499] = 1,076
fusc[699,051] = 10,946
fusc[19,573,419] = 103,682
```

## JavaScript

### Functional

Translation of: Python

A composition of pure generic functions:

`(() => {    'use strict';     const main = () => {         // fusc :: Int -> Int        const fusc = i => {            const go = n =>                0 === n ? (                    [1, 0]                ) : (() => {                    const [x, y] = go(quot(n, 2));                    return even(n) ? (                        [x + y, y]                    ) : [x, x + y];                })();            return 1 > i ? (                0            ) : fst(go(i - 1));        };          // firstWidths :: Int -> [(Int, Int)]        const firstWidths = n => {            const nxtWidth = xs => {                const                    fi = fanArrow(fusc, id),                    [w, i, v] = head(xs),                    [x, j] = Array.from(until(                        v => w <= fst(v).toString().length,                        v => fi(succ(snd(v))),                        fi(i)                    ));                return cons(                    [succ(w), j, x],                    xs                );            };            return until(                x => n < fst(fst(x)),                nxtWidth,                [[2, 0, 0]]            );        };         return unlines([            'First 61 terms:',            '[' + map(fusc, enumFromTo(0, 60)).join(',') + ']',            '',            '(Index, Value):',            unlines(map(                ([i, x]) => '(' + i + ', ' + x + ')',                foldl(                    (a, x) => cons(tail(x), a),                    [],                    firstWidths(5)                )            ))        ]);    };     // GENERIC FUNCTIONS ----------------------------     // Tuple (,) :: a -> b -> (a, b)    const Tuple = (a, b) => ({        type: 'Tuple',        '0': a,        '1': b,        length: 2    });     // cons :: a -> [a] -> [a]    const cons = (x, xs) =>        Array.isArray(xs) ? (            [x].concat(xs)        ) : 'GeneratorFunction' !== xs.constructor.constructor.name ? (            x + xs        ) : ( // Existing generator wrapped with one additional element            function*() {                yield x;                let nxt = xs.next()                while (!nxt.done) {                    yield nxt.value;                    nxt = xs.next();                }            }        )();     // enumFromTo :: Enum a => a -> a -> [a]    const enumFromTo = (m, n) => {        const [x, y] = [m, n].map(fromEnum),            b = x + ('number' !== typeof m ? 0 : m - x);        return Array.from({            length: 1 + (y - x)        }, (_, i) => toEnum(m)(b + i));    };     // even :: Int -> Bool    const even = n => 0 === n % 2;     // Compose a function from a simple value to a tuple of    // the separate outputs of two different functions     // fanArrow (&&&) :: (a -> b) -> (a -> c) -> (a -> (b, c))    const fanArrow = (f, g) => x => Tuple(f(x), g(x));     // foldl :: (a -> b -> a) -> a -> [b] -> a    const foldl = (f, a, xs) => xs.reduce(f, a);     // fromEnum :: Enum a => a -> Int    const fromEnum = x =>        typeof x !== 'string' ? (            x.constructor === Object ? (                x.value            ) : parseInt(Number(x))        ) : x.codePointAt(0);     // fst :: (a, b) -> a    const fst = tpl => tpl;     // head :: [a] -> a    const head = xs => xs.length ? xs : undefined;     // id :: a -> a    const id = x => x;     // map :: (a -> b) -> [a] -> [b]    const map = (f, xs) =>        (Array.isArray(xs) ? (            xs        ) : xs.split('')).map(f);     // quot :: Int -> Int -> Int    const quot = (n, m) => Math.floor(n / m);     // snd :: (a, b) -> b    const snd = tpl => tpl;     // succ :: Enum a => a -> a    const succ = x => {        const t = typeof x;        return 'number' !== t ? (() => {            const [i, mx] = [x, maxBound(x)].map(fromEnum);            return i < mx ? (                toEnum(x)(1 + i)            ) : Error('succ :: enum out of range.')        })() : x < Number.MAX_SAFE_INTEGER ? (            1 + x        ) : Error('succ :: Num out of range.')    };     // tail :: [a] -> [a]    const tail = xs => 0 < xs.length ? xs.slice(1) : [];     // The first argument is a sample of the type    // allowing the function to make the right mapping     // toEnum :: a -> Int -> a    const toEnum = e => x => {        const            m = e.enum,            f = {                'number': Number,                'string': String.fromCodePoint,                'boolean': Boolean            } [typeof e];        return f ? (            f(x)        ) : m[m[x]];    };     // unlines :: [String] -> String    const unlines = xs => xs.join('\n');     // until :: (a -> Bool) -> (a -> a) -> a -> a    const until = (p, f, x) => {        let v = x;        while (!p(v)) v = f(v);        return v;    };     // MAIN ---    return main();})();`
Output:
```First 61 terms:
[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, Value):
(0, 0)
(37, 11)
(1173, 108)
(35499, 1076)
(699051, 10946)```

## Julia

`using Memoize, Formatting @memoize function sternbrocot(n)    if n < 2        return n    elseif iseven(n)        return sternbrocot(div(n, 2))    else        m = div(n - 1, 2)        return sternbrocot(m) + sternbrocot(m + 1)    endend function fusclengths(N=100000000)    println("sequence number : fusc value")    maxlen = 0    for i in 0:N        x = sternbrocot(i)        if (len = length(string(x))) > maxlen            println(lpad(format(i, commas=true), 15), " : ", format(x, commas=true))            maxlen = len        end    endend println("The first 61 fusc numbers are: ", [sternbrocot(x) for x in 0:60])fusclengths() `
Output:
```The first 61 fusc numbers are: [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]
sequence number : fusc value
0 : 0
37 : 11
1,173 : 108
35,499 : 1,076
699,051 : 10,946
19,573,419 : 103,682
```

## Kotlin

Translation of: Go
`// Version 1.3.21 fun fusc(n: Int): IntArray {    if (n <= 0) return intArrayOf()    if (n == 1) return intArrayOf(0)    val res = IntArray(n)    res = 1    for (i in 2 until n) {        if (i % 2 == 0) {            res[i] = res[i / 2]        } else {            res[i] = res[(i - 1) / 2] + res[(i + 1) / 2]        }    }    return res} fun fuscMaxLen(n: Int): List<Pair<Int, Int>> {    var maxLen = -1    var maxFusc = -1    val f = fusc(n)    val res = mutableListOf<Pair<Int, Int>>()    for (i in 0 until n) {        if (f[i] <= maxFusc) continue // avoid string conversion        maxFusc = f[i]        val len = f[i].toString().length        if (len > maxLen) {            res.add(Pair(i, f[i]))            maxLen = len        }    }    return res} fun main() {    println("The first 61 fusc numbers are:")    println(fusc(61).asList())    println("\nThe fusc numbers whose length > any previous fusc number length are:")    val res = fuscMaxLen(20_000_000)  // examine first 20 million numbers say    for (r in res) {        System.out.printf("%,7d (index %,10d)\n", r.second, r.first)    }}`
Output:
```The first 61 fusc numbers are:
[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]

The fusc numbers whose length > any previous fusc number length are:
0 (index          0)
11 (index         37)
108 (index      1,173)
1,076 (index     35,499)
10,946 (index    699,051)
103,682 (index 19,573,419)
```

## Lua

Translation of: C
`function fusc(n)    n = math.floor(n)    if n == 0 or n == 1 then        return n    elseif n % 2 == 0 then        return fusc(n / 2)    else        return fusc((n - 1) / 2) + fusc((n + 1) / 2)    endend function numLen(n)    local sum = 1    while n > 9 do        n = math.floor(n / 10)        sum = sum + 1    end    return sumend function printLargeFuscs(limit)    print("Printing all largest Fusc numbers up to " .. limit)    print("Index-------Value")    local maxLen = 1    for i=0,limit do        local f = fusc(i)        local le = numLen(f)        if le > maxLen then            maxLen = le        print(string.format("%5d%12d", i, f))        end    endend function main()    print("Index-------Value")    for i=0,60 do        print(string.format("%5d%12d", i, fusc(i)))    end    printLargeFuscs(math.pow(2, 31) - 1)end main()`
Output:
```Index-------Value
0           0
1           1
2           1
3           2
4           1
5           3
6           2
7           3
8           1
9           4
10           3
11           5
12           2
13           5
14           3
15           4
16           1
17           5
18           4
19           7
20           3
21           8
22           5
23           7
24           2
25           7
26           5
27           8
28           3
29           7
30           4
31           5
32           1
33           6
34           5
35           9
36           4
37          11
38           7
39          10
40           3
41          11
42           8
43          13
44           5
45          12
46           7
47           9
48           2
49           9
50           7
51          12
52           5
53          13
54           8
55          11
56           3
57          10
58           7
59          11
60           4
Printing all largest Fusc numbers up to 2147483647
Index-------Value
37          11
1173         108
35499        1076
699051       10946```

## Mathematica / Wolfram Language

`ClearAll[Fusc]Fusc := 0Fusc := 1Fusc[n_] := Fusc[n] = If[EvenQ[n], Fusc[n/2], Fusc[(n - 1)/2] + Fusc[(n + 1)/2]]Fusc /@ Range[0, 60]res = {{0, 1}};i = 0;PrintTemporary[Dynamic[{res, i}]];While[Length[res] < 6,  f = Fusc[i];  If[IntegerLength[res[[-1, -1]]] < IntegerLength[f],   AppendTo[res, {i, f}]   ];  i++;  ];res`
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}
{{0, 1}, {37, 11}, {1173, 108}, {35499, 1076}, {699051, 10946}, {19573419, 103682}}```

## Nim

### Using recursive procedure

This is the simplest way to compute the sequence, but not very efficient here as we compute several times the same values. The algorithm could be improved by using a cache to keep the values.

`import strformat func fusc(n: int): int =  if n == 0 or n == 1:    n  elif n mod 2 == 0:    fusc(n div 2)  else:    fusc((n - 1) div 2) + fusc((n + 1) div 2) echo "The first 61 Fusc numbers:"for i in 0..61:  write(stdout, fmt"{fusc(i)} ")echo "\n\nThe Fusc numbers whose lengths are greater than those of previous Fusc numbers:"echo fmt"        n   fusc(n)"echo    "--------- ---------"var maxLength = 0for i in 0..700_000:  var f = fusc(i)  var length = len(\$f)  if length > maxLength:    maxLength = length    echo fmt"{i:9} {f:9}"`
Output:
```The first 61 Fusc numbers:
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

The Fusc numbers whose lengths are greater than those of previous Fusc numbers:
n   fusc(n)
--------- ---------
0         0
37        11
1173       108
35499      1076
699051     10946
```

### Using iterators and double queues (deques)

Translation of: Python

This is a translation of the Python procedural algorithm, using iterators instead of generators. It allows to compute the seven first Fusc numbers whose lengths are greater than those of previous Fusc numbers.

`import deques, strformat  iterator fusc(): int =  var q = .toDeque()  yield 0  yield 1   while true:    var val = q.popFirst()    q.addLast(val)    yield val     val += q    q.addLast(val)    yield val  iterator longestFusc(): tuple[idx, val: int] =  var sofar = 0  var i = -1  for f in fusc():    inc i    if f >= sofar:      yield (i, f)      sofar = if sofar == 0: 10 else: 10 * sofar  #——————————————————————————————————————————————————————————————————————————————————————————————————— const  MaxFusc = 61  LongestCount = 7 echo &"First {MaxFusc}:"var i = -1for f in fusc():  inc i  stdout.write f  if i == MaxFusc:    echo ""    break  stdout.write ' ' echo "\nLength records:"var count = 0for (i, f) in longestFusc():  inc count  echo &"fusc({i}) = {f}"  if count == LongestCount:    break`
Output:
```First 61:
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

Length records:
fusc(0) = 0
fusc(37) = 11
fusc(1173) = 108
fusc(35499) = 1076
fusc(699051) = 10946
fusc(19573419) = 103682
fusc(615164587) = 1010747```

## Pascal

Works with: Free Pascal

Using dynamic array.To speed things up using Pointer. Found the indices of a specific base to oszillating.Tried power of phi with more success 11 ~ phi^5

`program fusc;uses  sysutils;const{\$IFDEF FPC}  MaxIdx = 1253 * 1000 * 1000; //19573420; // must be even{\$ELSE}  // Dynamics arrays in Delphi cann't be to large  MaxIdx = 19573420; {\$ENDIF} type  tFuscElem = LongWord;  tFusc = array of tFuscElem;var  FuscField : tFusc; function commatize(n:NativeUint):string;var  l,i : NativeUint;begin  str(n,result);  l := length(result);  //no commatize  if l < 4 then    exit;  //new length  i := l+ (l-1) DIV 3;  setlength(result,i);  //copy chars to the right place  While i <> l do  Begin    result[i]:= result[l];result[i-1]:= result[l-1];    result[i-2]:= result[l-2];result[i-3]:= ',';    dec(i,4);dec(l,3);  end;end; procedure OutFusc(StartIdx,EndIdx :NativeInt;const FF:tFusc);Begin  IF StartIdx < Low(FF) then StartIdx :=Low(FF);  IF EndIdx > High(FF) then EndIdx := High(FF);  For StartIdx := StartIdx to EndIdx do    write(FF[StartIdx],' ');  writeln;end; procedure FuscCalc(var FF:tFusc);var  pFFn,pFFi : ^tFuscElem;  i,n,sum : NativeUint;Begin  FF:= 0;  FF:= 1;  n := 2;  i := 1;  pFFn := @FF[n];  pFFi := @FF[i];  sum := pFFi^;  while n <= MaxIdx-2 do  begin    //even    pFFn^ := sum;//FF[n] := FF[i];    //odd    inc(pFFi);//FF[i+1]    inc(pFFn);//FF[n+1]    sum := sum+pFFi^;    pFFn^:= sum; //FF[n+1] := FF[i]+FF[i+1];    sum := pFFi^;    inc(pFFn);    inc(n,2);    //inc(i);  end;end; procedure OutHeader(base:NativeInt);begin  writeln('Fusc numbers with more digits in base ',base,' than all previous ones:');  writeln('Value':10,'Index':10,'  IndexNum/IndexNumBefore');  writeln('======':10,' =======':14);end; procedure CheckFuscDigits(const FF:tFusc;Base:NativeUint);var  pFF : ^tFuscElem;  Dig,  i,lastIdx: NativeInt;Begin  OutHeader(base);  Dig := -1;  i := 0;  lastIdx := 0;  pFF := @FF;// aka FF[i]  repeat    //search in tight loop speeds up    repeat      inc(pFF);      inc(i);    until pFF^ >Dig;     if i>= MaxIdx then      BREAK;    //output    write(commatize(pFF^):10,commatize(i):14);//,DIG:10);    IF lastIdx> 0 then      write(i/lastIdx:12:7);    writeln;    lastIdx := i;    IF Dig >0 then      Dig := Dig*Base+Base-1    else     Dig := Base-1;  until false;  writeln;end; BEGIN  setlength(FuscField,MaxIdx);  FuscCalc(FuscField);  writeln('First 61 fusc numbers:');  OutFusc(0,60,FuscField);   CheckFuscDigits(FuscField,10);  CheckFuscDigits(FuscField,11); //11 ~phi^5  1.6180..^5 = 11,09  setlength(FuscField,0);  {\$IFDEF WIN}readln;{\$ENDIF}END.`
Output:
```First 61 fusc numbers:
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
Fusc numbers with more digits in base 10 than all previous ones:
Value     Index  IndexNum/IndexNumBefore
======       =======
1             1
11            37  37.0000000
108         1,173  31.7027027
1,076        35,499  30.2634271
10,946       699,051  19.6921322
103,682    19,573,419  27.9999871
1,010,747   615,164,587  31.4285709

Fusc numbers with more digits in base 11 than all previous ones:
Value     Index  IndexNum/IndexNumBefore
======       =======
1             1
11            37  37.0000000
123         1,195  32.2972973
1,364        38,229  31.9907950
15,127     1,223,339  32.0002877
167,761    39,146,837  31.9999910
1,860,498 1,252,698,795  32.0000003

real  0m1,968s  user  0m1,594s  sys 0m0,373s```

## Perl

Borrowing from the Stern-Brocot sequence task.

`use strict;use warnings;use feature 'say'; sub comma { reverse ((reverse shift) =~ s/(.{3})/\$1,/gr) =~ s/^,//r } sub stern_diatomic {  my (\$p,\$q,\$i) = (0,1,shift);  while (\$i) {    if (\$i & 1) { \$p += \$q; } else { \$q += \$p; }    \$i >>= 1;  }  \$p;} say "First 61 terms of the Fusc sequence:\n" . join ' ', map { stern_diatomic(\$_) } 0..60;say "\nIndex and value for first term longer than any previous:"; my \$i =  0;my \$l = -1;while (\$l < 5) {    my \$v = stern_diatomic(\$i);    printf("%15s : %s\n", comma(\$i), comma(\$v)) and \$l = length \$v if length \$v > \$l;     \$i++;}`
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:
0 : 0
37 : 11
1,173 : 108
35,499 : 1,076
699,051 : 10,946```

## Phix

Note that phix is 1-indexed. While there are no commas in the first 61 entries, it felt more in line with the task requirements to forego the standard comma-separated %v output.

```constant limit = 20_000_000
sequence fuscs = repeat(0,limit); -- NB 1-based indexing; fusc(0)===fuscs
fuscs = 1                                        -- ie fusc(1):=1
for n=3 to limit do
fuscs[n] = iff(remainder(n-1,2)?fuscs[n/2]+fuscs[n/2+1]:fuscs[(n+1)/2])
end for
--printf(1,"First 61 terms of the Fusc sequence:\n%v\n",{fuscs[1..61]})
string s = ""
for n=1 to 61 do s&=sprintf("%,d ",fuscs[n]) end for
printf(1,"First 61 terms of the Fusc sequence:\n%s\n\n",{s})
printf(1,"Elements with more digits than any previous items:\n")
printf(1,"          Index : Value\n")
integer d = 0
for n=1 to length(fuscs) do
if fuscs[n]>=d then
printf(1,"%,15d : %,d\n",{n-1,fuscs[n]})
d = iff(d=0?10:d*10)
end if
end for
```
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

Elements with more digits than any previous items:
Index : Value
0 : 0
37 : 11
1,173 : 108
35,499 : 1,076
699,051 : 10,946
19,573,419 : 103,682
```

## Processing

`void setup() {  println("First 61 terms:");  for (int i = 0; i < 60; i++) {    print(fusc(i) + " ");  }  println(fusc(60));  println();  println("Sequence elements where number of digits of the value increase:");  int max_len = 0;  for (int i = 0; i < 700000; i++) {    int temp = fusc(i);    if (str(temp).length() > max_len) {      max_len = str(temp).length();      println("(" + i + ", " + temp + ")");    }  }} int fusc(int n) {  if (n <= 1) {    return n;  } else if (n % 2 == 0) {    return fusc(n / 2);  } else {    return fusc((n - 1) / 2) + fusc((n + 1) / 2);  }}`
Output:
```First 61 terms:
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

Sequence elements where number of digits of the value increase:
(0, 0)
(37, 11)
(1173, 108)
(35499, 1076)
(699051, 10946)```

## Prolog

Works with: SWI Prolog
`:- dynamic fusc_cache/2. fusc(0, 0):-!.fusc(1, 1):-!.fusc(N, F):-    fusc_cache(N, F),    !.fusc(N, F):-    0 is N mod 2,    !,    M is N//2,    fusc(M, F),    assertz(fusc_cache(N, F)).fusc(N, F):-    N1 is (N - 1)//2,    N2 is (N + 1)//2,    fusc(N1, F1),    fusc(N2, F2),    F is F1 + F2,    assertz(fusc_cache(N, F)). print_fusc_sequence(N):-    writef('First %w fusc numbers:\n', [N]),    print_fusc_sequence(N, 0),    nl. print_fusc_sequence(N, M):-    M >= N,    !.print_fusc_sequence(N, M):-    fusc(M, F),    writef('%w ', [F]),    M1 is M + 1,    print_fusc_sequence(N, M1). print_max_fusc(N):-    writef('Fusc numbers up to %w that are longer than any previous one:\n', [N]),    print_max_fusc(N, 0, 0). print_max_fusc(N, M, _):-    M >= N,    !.print_max_fusc(N, M, Max):-    fusc(M, F),    (F >= Max ->        writef('n = %w, fusc(n) = %w\n', [M, F]), Max1 = max(10, Max * 10)        ;        Max1 = Max    ),    M1 is M + 1,    print_max_fusc(N, M1, Max1). main:-    print_fusc_sequence(61),    print_max_fusc(1000000).`
Output:
```First 61 fusc numbers:
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
Fusc numbers up to 1000000 that are longer than any previous one:
n = 0, fusc(n) = 0
n = 37, fusc(n) = 11
n = 1173, fusc(n) = 108
n = 35499, fusc(n) = 1076
n = 699051, fusc(n) = 10946
```

## Python

### Procedural

`from collections import dequefrom itertools import islice, count  def fusc():    q = deque()    yield 0    yield 1     while True:        x = q.popleft()        q.append(x)        yield x         x += q        q.append(x)        yield x  def longest_fusc():    sofar = 0    for i, f in zip(count(), fusc()):        if f >= sofar:            yield(i, f)            sofar = 10 * sofar or 10  print('First 61:')print(list(islice(fusc(), 61))) print('\nLength records:')for i, f in islice(longest_fusc(), 6):    print(f'fusc({i}) = {f}') `
Output:
```First 61:
[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]

Length records:
fusc(0) = 0
fusc(37) = 11
fusc(1173) = 108
fusc(35499) = 1076
fusc(699051) = 10946
fusc(19573419) = 103682```

### Functional

By composition of pure functions, avoiding mutable variables, and confining any unavoidables to the internals of well-tested primitives:

`'''Fusc sequence''' from itertools import chain, count, islicefrom operator import itemgetter  # As an infinite stream of terms, # infiniteFusc :: [Int]def infiniteFusc():    '''Fusc sequence.       OEIS A2487    '''    def go(step):        isEven, n, xxs = step        x, xs = xxs, xxs[1:]        if isEven:            nxt = n + x            return not isEven, nxt, xxs + [nxt]        else:            return not isEven, x, xs + [x]     return chain(        [0, 1],        map(            itemgetter(1),            iterate(go)(                (True, 1, )            )        )    )  # Or as a function over an integer: # fusc :: Int -> Intdef fusc(i):    '''Fusc sequence'''    def go(n):        if 0 == n:            return (1, 0)        else:            x, y = go(n // 2)            return (x + y, y) if 0 == n % 2 else (                x, x + y            )    return 0 if 1 > i else (        go(i - 1)    )  # firstFuscOfEachMagnitude ::def firstFuscOfEachMagnitude():    '''Non-finite stream of each term       in OEIS A2487 that requires an       unprecedented quantity of decimal digits.    '''    a2487 = enumerate(map(fusc, count()))     def go(e):        limit = 10 ** e        return next(            (i, x) for i, x in a2487            if limit <= x        )    return (        chain([(0, 0)], map(go, count(1)))    )  # --------------------------TEST---------------------------# main :: IO ()def main():    '''Tests'''     print('First 61 terms:')    print(showList(        take(61)(            map(fusc, count())        )    ))     print('\nFirst term of each decimal magnitude:')    print('(Index, Term):')    ixs = firstFuscOfEachMagnitude()    for _ in range(0, 5):        print(next(ixs))  # -------------------------GENERIC------------------------- # iterate :: (a -> a) -> a -> Gen [a]def iterate(f):    '''An infinite list of repeated       applications of f to x.    '''    def go(x):        v = x        while True:            yield v            v = f(v)    return lambda x: go(x)  # showList :: [a] -> Stringdef showList(xs):    '''Compact stringification of a list.'''    return '[' + ','.join(repr(x) for x in xs) + ']'  # take :: Int -> [a] -> [a]# take :: Int -> String -> Stringdef take(n):    '''The prefix of xs of length n,       or xs itself if n > length xs.    '''    return lambda xs: (        xs[0:n]        if isinstance(xs, (list, tuple))        else list(islice(xs, n))    )  # MAIN ---if __name__ == '__main__':    main()`
Output:
```First 61 terms:
[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]

First term of each decimal magnitude:
(Index, Term):
(0, 0)
(37, 11)
(1173, 108)
(35499, 1076)
(699051, 10946)```

## Quackery

`   [ 1 & ]                is odd       ( n --> b )   [ 0 swap   [ dip 1+     10 / dup     0 = until ]    drop ]               is digits    ( n --> n )   [ dup dup size    dup odd iff      [ dup 1 - 2 /        dip          [ 1 + 2 / peek            over ]        peek + ]    else      [ 2 / peek ]    join ]               is nextfusc  ( [ --> [ )   say "First 61 terms." cr  ' [ 0 1 ]  59 times nextfusc  witheach [ echo sp ]  cr cr  say "Terms where the digit count increases." cr  say "fusc(0) = 0" cr  1 ' [ 0 1 ]  [ nextfusc    dup -1 peek digits    rot 2dup > iff      [ drop swap        say "fusc("        dup -1 peek echo        say ") = "        dup size 1 - echo cr ]    else [ nip swap ]    dup size 1000000 = until ]  2drop`
Output:
```First 61 terms.
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

Terms where the digit count increases.
fusc(0) = 0
fusc(11) = 37
fusc(108) = 1173
fusc(1076) = 35499
fusc(10946) = 699051```

## R

I believe that this code demonstrates a great truth of R: It is amazing with numbers, but terrible with strings. There is really no good reason why checking how long a number is and printing it nicely should be hardest parts of this task.

Our first step is to adapt the 0-indexed definition to our 1-indexed language, letting us complete the first task.

`firstNPlus1FuscNumbers<-function(n){  if(n==0){return(0)}else{fusc<-c(0,1)}  for(i in (2+seq_len(n-1)))  {    if(i %% 2 == 0){fusc[i]<-fusc[i/2]+fusc[(i+2)/2]}    else{fusc[i]<-fusc[(i+1)/2]}  }  fusc}first61<-firstNPlus1FuscNumbers(60)print(first61)`

The second task's requirements are somewhat strange. It asks for the number, implying that there is only one, but it is clear that there are several. If we only want the first such number, then the task is trivial. As we have already seen it in the n=60 output, we don't even have to be smart. Indeed, if we were being smart, we'd say that the answer was trivial: 0 at index 1.

A proper solution that only gives one non-trivial result is as follows:

`index<-which.max(nchar(first61)==2)number<-first61[index]cat("The first fusc number that is longer than all previous fusc numbers is",number,    "and it occurs at index",index)`

Regardless, as many of the other solutions have displayed many such numbers (e.g. the 6 digit case), we will do the same. This complicates matters in some unexpected ways. For example, nchar misbehaves once its inputs get large enough for R to default to scientific notation. One nice solution is to use format, which also allows us to add the required commas:

`twentyMillion<-firstNPlus1FuscNumbers(2*10^7-1)twentyMillionCountable<-format(twentyMillion,scientific = FALSE,trim = TRUE)indices<-sapply(2:6, function(x) which.max(nchar(twentyMillionCountable)==x))numbers<-twentyMillion[indices]cat("Some fusc numbers that are longer than all previous fusc numbers are:\n",    paste0(format(twentyMillion[indices],scientific = FALSE,trim = TRUE,big.mark = ","),          " (at index ",format(indices,trim = TRUE,big.mark = ","),")\n"))`
Output:
```> print(first61)
  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
> cat("The first fusc number that is longer than all previous fusc numbers is",number,
+     "and it occurs at index",index)
The first fusc number that is longer than all previous fusc numbers is 11 and it occurs at index 38
> cat("Some fusc numbers that are longer than all previous fusc numbers are:\n",
+     paste0(format(twentyMillion[indices],scientific = FALSE,trim = TRUE,big.mark = ","),
+           " (at index ",format(indices,trim = TRUE,big.mark = ","),")\n"))
Some fusc numbers that are longer than all previous fusc numbers are:
11 (at index 38)
108 (at index 1,174)
1,076 (at index 35,500)
10,946 (at index 699,052)
103,682 (at index 19,573,420)```

## Racket

`#lang racket (require racket/generator) (define (memoize f)  (define table (make-hash))  (λ args (hash-ref! table args (thunk (apply f args))))) (define fusc  (memoize   (λ (n)     (cond       [(<= n 1) n]       [(even? n) (fusc (/ n 2))]       [else (+ (fusc (/ (sub1 n) 2)) (fusc (/ (add1 n) 2)))])))) (define (comma x)  (string-join   (reverse    (for/list ([digit (in-list (reverse (string->list (~a x))))] [i (in-naturals)])      (cond        [(and (= 0 (modulo i 3)) (> i 0)) (string digit #\,)]        [else (string digit)])))   "")) ;; Task 1(displayln (string-join (for/list ([i (in-range 61)]) (comma (fusc i))) " "))(newline) ;; Task 2(define gen  (in-generator   (let loop ([prev 0] [i 0])     (define result (fusc i))     (define len (string-length (~a result)))     (cond       [(> len prev)        (yield (list i result))        (loop len (add1 i))]       [else (loop prev (add1 i))])))) (for ([i (in-range 5)] [x gen])  (match-define (list index result) x)  (printf "~a: ~a\n" (comma index) (comma result)))`
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

0: 0
37: 11
1,173: 108
35,499: 1,076
699,051: 10,946
```

## Raku

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

## REXX

### version 1, standard formatting

`/*REXX program  calculates and displays the   fusc   (or  Stern's Diatomic)   sequence. */parse arg st # xw .                              /*obtain optional arguments from the CL*/if st=='' | st==","  then st=  0                 /*Not specified?  Then use the default.*/if  #=='' |  #==","  then  #= 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 #                                 /*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>=st  then \$= \$ commas(@.j)                      /*add it to a list*/                           else nop                                   /*NOP≡placeholder.*/            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*/                                                 /*\$   has a superfluous leading blank. */if \$\==''  then say strip(\$)                     /*display a horizontal list of fusc #s.*/exit 0                                           /*stick a fork in it,  we're all done. *//*──────────────────────────────────────────────────────────────────────────────────────*/commas:  parse arg ?;  do _=length(?)-3  to 1  by -3; ?=insert(',', ?, _); end;   return ?`
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
```
output   when using the default inputs:     ,   999999999   5
```═══index═══   ═══fusc number═══
0              0
37             11
1,173            108
35,499          1,076
699,051         10,946
```

### version 2, formatted with rows re─starting whenever a 1 (unity) appears

`/*REXX program  calculates and displays the   fusc   (or  Stern's Diatomic)   sequence. */parse arg st # xw .                              /*obtain optional arguments from the CL*/if st=='' | st==","  then st=   0                /*Not specified?  Then use the default.*/if  #=='' |  #==","  then  #= 256                /* "      "         "   "   "     "    */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 #                                 /*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>=st  then \$= \$ commas(@.j)                      /*add it to a list*/                           else nop                                   /*NOP≡placeholder.*/            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*/                                                 /*\$   has a superfluous leading blank. */if \$==''  then exit 0                            /*display a horizontal list of fusc #s.*/row= -1                                          /*output will be starting ar row  zero.*/\$\$= 0                                            /*initialize with the zeroth entry (=0)*/       do k=2  for #;       y= word(\$, k)        /*start processing with the 2nd number.*/       if y==1  then do;  row= row + 1           /*Is it unity?    Then bump row number.*/                          say 'row('row")="  \$\$  /*display the row that was just created*/                          \$\$= 1                  /*initialize a new row with 1  (unity).*/                     end                else \$\$= \$\$  y                   /*Not unity?   Just append it to a row.*/       end   /*k*/ if \$\$\==''  then say "row("row+1')='  \$\$         /*display any residual data in the row.*/exit 0                                           /*stick a fork in it,  we're all done. *//*──────────────────────────────────────────────────────────────────────────────────────*/commas:  parse arg ?;  do _=length(?)-3  to 1  by -3; ?=insert(',', ?, _); end;   return ?`
output   when using the default inputs:

(Shown at  70%  size.)

```row(0)= 0
row(1)= 1
row(2)= 1 2
row(3)= 1 3 2 3
row(4)= 1 4 3 5 2 5 3 4
row(5)= 1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5
row(6)= 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 5 6
row(7)= 1 7 6 11 5 14 9 13 4 15 11 18 7 17 10 13 3 14 11 19 8 21 13 18 5 17 12 19 7 16 9 11 2 11 9 16 7 19 12 17 5 18 13 21 8 19 11 14 3 13 10 17 7 18 11 15 4 13 9 14 5 11 6 7
row(8)= 1 8 7 13 6 17 11 16 5 19 14 23 9 22 13 17 4 19 15 26 11 29 18 25 7 24 17 27 10 23 13 16 3 17 14 25 11 30 19 27 8 29 21 34 13 31 18 23 5 22 17 29 12 31 19 26 7 23 16 25 9 20 11 13 2 13 11 20 9 25 16 23 7 26 19 31 12 29 17 22 5 23 18 31 13 34 21 29 8 27 19 30 11 25 14 17 3 16 13 23 10 27 17 24 7 25 18 29 11 26 15 19 4 17 13 22 9 23 14 19 5 16 11 17 6 13 7 8
```
Output observation:   note that each (positive) row doubles in size (number of entries),   and starts with unity (1),   and
ends with the number of the row   (if the number of sequence elements is a power of two).

## Ring

` # Project: Fusc sequence max = 60fusc = list(36000)fusc = 1see "working..." + nlsee "wait for done..." + nlsee "The first 61 fusc numbers are:" + nlfuscseq(max)see "0"for m = 1 to max    see " " + fusc[m]next see nlsee "The fusc numbers whose length > any previous fusc number length are:" + nlsee "Index Value" + nlsee " 0     0" + nld = 10for i = 1 to 36000    if fusc[i] >= d         see " " + i + "   " + fusc[i] + nl        if d = 0            d = 1        ok        d = d*10    oknextsee "done..." + nl func fuscseq(max)      for n = 2 to 36000         if n%2 = 1             fusc[n] = fusc[(n-1)/2] + fusc[(n+1)/2]         but n%2 = 0              fusc[n] = fusc[n/2]         ok        next `
Output:
```working...
wait for done...
The first 61 fusc numbers are:
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
The fusc numbers whose length > any previous fusc number length are:
Index Value
0     0
37    11
1173  108
35499 1076
done...
```

## Ruby

Using two Enumerators; the second making use of the first:

`fusc = Enumerator.new do |y|  y << 0  y << 1  arr = [0,1]  2.step do |n|    res = n.even? ? arr[n/2] : arr[(n-1)/2] + arr[(n+1)/2]    y   << res    arr << res  endend fusc_max_digits = Enumerator.new do |y|   cur_max, cur_exp = 0, 0   0.step do |i|      f = fusc.next      if f >= cur_max        cur_exp += 1        cur_max = 10**cur_exp        y << [i, f]      end   endend puts fusc.take(61).join(" ")fusc_max_digits.take(6).each{|pair| puts "%15s : %s" % pair } `
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
0 : 0
11 : 37
108 : 1173
1076 : 35499
10946 : 699051
103682 : 19573419
```

## Rust

`fn fusc_sequence() -> impl std::iter::Iterator<Item = u32> {    let mut sequence = vec![0, 1];    let mut n = 0;    std::iter::from_fn(move || {        if n > 1 {            sequence.push(match n % 2 {                0 => sequence[n / 2],                _ => sequence[(n - 1) / 2] + sequence[(n + 1) / 2],            });        }        let result = sequence[n];        n += 1;        Some(result)    })} fn main() {    println!("First 61 fusc numbers:");    for n in fusc_sequence().take(61) {        print!("{} ", n)    }    println!();     let limit = 1000000000;    println!(        "Fusc numbers up to {} that are longer than any previous one:",        limit    );    let mut max = 0;    for (index, n) in fusc_sequence().take(limit).enumerate() {        if n >= max {            max = std::cmp::max(10, max * 10);            println!("index = {}, fusc number = {}", index, n);        }    }}`
Output:
```First 61 fusc numbers:
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
Fusc numbers up to 1000000000 that are longer than any previous one:
index = 0, fusc number = 0
index = 37, fusc number = 11
index = 1173, fusc number = 108
index = 35499, fusc number = 1076
index = 699051, fusc number = 10946
index = 19573419, fusc number = 103682
index = 615164587, fusc number = 1010747
```

## Sidef

`func fusc(n) is cached {     return 0 if n.is_zero    return 1 if n.is_one     n.is_even ? fusc(n/2) : (fusc((n-1)/2) + fusc(((n-1)/2)+1))} say ("First 61 terms of the Stern-Brocot sequence: ", 61.of(fusc).join(' ')) say "\nIndex and value for first term longer than any previous:"printf("%15s : %s\n", "Index", "Value"); var (index=0, len=0) 5.times {    index = (index..Inf -> first_by { fusc(_).len > len })    len = fusc(index).len    printf("%15s : %s\n", index.commify, fusc(index).commify)}`
Output:
```First 61 terms of the Stern-Brocot 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
```

## Swift

`struct FuscSeq: Sequence, IteratorProtocol {  private var arr = [0, 1]  private var i = 0   mutating func next() -> Int? {    defer {      i += 1    }     guard i > 1 else {      return arr[i]    }     switch i & 1 {    case 0:      arr.append(arr[i / 2])    case 1:      arr.append(arr[(i - 1) / 2] + arr[(i + 1) / 2])    case _:      fatalError()    }     return arr.last!  }} let first = FuscSeq().prefix(61) print("First 61: \(Array(first))") var max = -1 for (i, n) in FuscSeq().prefix(20_000_000).enumerated() {  let f = String(n).count   if f > max {    max = f     print("New max: \(i): \(n)")  }}`
Output:
```First 61: [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]
New max: 0: 0
New max: 37: 11
New max: 1173: 108
New max: 35499: 1076
New max: 699051: 10946
New max: 19573419: 103682```

## Tcl

`proc fusc n {    if {\$n < 2} {        return \$n    }     if {[info exists ::g_fusc(\$n)]} { return \$::g_fusc(\$n) }     if {\$n % 2} {               ;# n is odd        set r [expr {[fusc [expr {(\$n-1)/2}]] + [fusc [expr {(\$n+1)/2}]]}]    } else {                    ;# n is even        set r [fusc [expr {\$n/2}]]    }     if {\$n < 999999} { set ::g_fusc(\$n) \$r }     return \$r} proc ,,, {str {sep ,} {grouplen 3}} {    set strlen [string length \$str]    set padlen [expr {(\$grouplen - (\$strlen % \$grouplen)) % \$grouplen}]    set r [regsub -all ... [string repeat " " \$padlen]\$str &\$sep]    return [string range \$r \$padlen end-[string length \$sep]]} proc tabline {a b c} {    puts "[format %2s \$a] [format %10s \$b] [format %8s \$c]"} proc doit {{nmax 20000000}} {    for {set i 0} {\$i < 61} {incr i} {        puts -nonewline " [fusc \$i]"    }    puts ""    tabline L n fusc(n)    set maxL 0    for {set n 0} {\$n < \$nmax} {incr n} {        set f [fusc \$n]        set L [string length \$f]        if {\$L > \$maxL} {            set maxL \$L            tabline \$L [,,, \$n] [,,, \$f]        }    }}doit`
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
L          n  fusc(n)
1          0        0
2         37       11
3      1,173      108
4     35,499    1,076
5    699,051   10,946
6 19,573,419  103,682

real    2m5.559s
```

## Vala

Translation of: Nim
`int fusc(int n) {  if (n == 0 || n == 1)    return n;  else if (n % 2 == 0)    return fusc(n / 2);  else    return fusc((n - 1) / 2) + fusc((n + 1) / 2);} void main() {  print("The first 61 fusc numbers:\n");  for (int i = 0; i < 61; i++)    print(@"\$(fusc(i)) ");  print("\n\nThe fusc numbers whose lengths are greater than those of previous fusc numbers:\n");  print("        n   fusc(n)\n");  print("-------------------\n");  var max_length = 0;  for (int i = 0; i < 700000; i++) {    var f = fusc(i);    var length = f.to_string().length;    if (length > max_length) {      max_length = length;      print("%9d %9d\n", i, f);    }   }}`
Output:
```The first 61 fusc numbers:
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

The fusc numbers whose lengths are greater than those of previous fusc numbers:
n   fusc(n)
-------------------
0         0
37        11
1173       108
35499      1076
699051     10946
```

## Visual Basic .NET

Translation of: C#
`Module Module1     Dim n As Integer = 61, l As List(Of Integer) = {0, 1}.ToList     Function fusc(n As Integer) As Integer        If n < l.Count Then Return l(n)        fusc = If((n And 1) = 0, l(n >> 1), l((n - 1) >> 1) + l((n + 1) >> 1))        l.Add(fusc)    End Function     Sub Main(args As String())        Dim lst As Boolean = True, w As Integer = -1, c As Integer = 0,            fs As String = "{0,11:n0}  {1,-9:n0}", res As String = ""        Console.WriteLine("First {0} numbers in the fusc sequence:", n)        For i As Integer = 0 To Integer.MaxValue            Dim f As Integer = fusc(i)            If lst Then                If i < 61 Then                    Console.Write("{0} ", f)                Else                    lst = False                    Console.WriteLine()                    Console.WriteLine("Points in the sequence where an item has more digits than any previous items:")                    Console.WriteLine(fs, "Index\", "/Value") : Console.WriteLine(res) : res = ""                End If            End If            Dim t As Integer = f.ToString.Length            If t > w Then                w = t                res &= If(res = "", "", vbLf) & String.Format(fs, i, f)                If Not lst Then Console.WriteLine(res) : res = ""                c += 1 : If c > 5 Then Exit For            End If        Next : l.Clear()    End SubEnd Module `
Output:
```First 61 numbers in 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
Points in the sequence where an item has more digits than any previous items:
Index\  /Value
0  0
37  11
1,173  108
35,499  1,076
699,051  10,946
19,573,419  103,682
```

## Wren

Library: Wren-fmt
`import "/fmt" for Fmt System.print("The first 61 numbers in the fusc sequence are:")var fusc = [0, 1]var fusc2 = [[0, 0]]var maxLen = 1var n = 2while (n < 20e6) { // limit to indices under 20 million say    var f  = (n % 2  == 0) ? fusc[n/2] : fusc[(n-1)/2] + fusc[(n+1)/2]    fusc.add(f)    var len = "%(f)".count    if (len > maxLen) {        maxLen = len        if (n <= 60) {            fusc2.add([n, f])        } else {            System.print("%(Fmt.dc(10, n))  %(Fmt.dc(0, f))")        }    }    if (n == 60 ) {        for (f in fusc) System.write("%(f) ")        System.print("\n\nFirst terms longer than any previous ones for indices < 20,000,000:")        System.print("     Index  Value")        for (iv in fusc2) System.print("%(Fmt.d(10, iv))  %(iv)")    }    n = n + 1}`
Output:
```The first 61 numbers in the fusc sequence are:
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

First terms longer than any previous ones for indices < 20,000,000:
Index  Value
0  0
37  11
1,173  108
35,499  1,076
699,051  10,946
19,573,419  103,682
```

## zkl

`fuscs:=List.createLong(1_000_000, 0); fuscs=1; // we'll just use a big countforeach n in ([2..fuscs.len()-1]){		 // and generate   fuscs[n]=( if(n.isEven()) fuscs[n/2] else fuscs[(n-1)/2] + fuscs[(n+1)/2] )} println("First 61 terms of the Stern-Brocot sequence:");fuscs[0,61].concat(" ").println(); println("\nIndex and value for first term longer than any previous:");println("          Index : Value");prevMax:=-1;foreach n in (fuscs.len()){   f,fd := fuscs[n], f.numDigits;   if(fd>prevMax){ println("%15,d : %,d".fmt(n,f)); prevMax=fd }}`
Output:
```First 61 terms of the Stern-Brocot 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
```