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

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


Related task


Also see



11l[edit]

Translation of: Kotlin
F fusc(n)
V res = [0] * n
res[1] = 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 = 0
L(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)

Ada[edit]

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[edit]

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
OD
END
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[edit]

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 if
end fusc
 
set sequence to {}
set longestSoFar to 0
repeat 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 if
end 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 script
end firstFuscOfEachMagnitude
 
 
-- fuscTerm :: Int -> Int
on 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 tell
end 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 script
end 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 script
end fmapGen
 
 
-- intercalate :: String -> [String] -> String
on 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
s
end 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 script
end 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 tell
end 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 if
end mReturn
 
 
-- gen :: [a] -> Gen a
on 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 script
end gen
 
 
-- showList :: [a] -> String
on showList(xs)
"[" & intercalate(", ", my map(my str, xs)) & "]"
end showList
 
 
-- showTuple :: (,) -> String
on showTuple(xs)
"(" & intercalate(", ", my map(my str, xs)) & ")"
end showTuple
 
 
-- snd :: (a, b) -> b
on snd(tpl)
if class of tpl is record then
|2| of tpl
else
item 2 of tpl
end if
end snd
 
 
-- str :: a -> String
on str(x)
x as string
end str
 
 
-- take :: Int -> [a] -> [a]
-- take :: Int -> String -> String
on 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 if
end take
 
 
-- unlines :: [String] -> String
on 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
s
end 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)

AWK[edit]

 
# syntax: GAWK -f FUSC_SEQUENCE.AWK
# converted from C
BEGIN {
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

C[edit]

 
#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#[edit]

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++[edit]

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[edit]

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

F#[edit]

The Function[edit]

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

The Tasks[edit]

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[edit]

USING: arrays assocs formatting io kernel make math math.parser
math.ranges namespaces prettyprint sequences
tools.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[edit]

' 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, d
Dim As String fs
 
fusc
 
For i = 0 To 60
Print f(i); " ";
Next
 
Print : Print
Print " 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 If
Next
 
' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End
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æ[edit]

In this page you can see the solution of this task.

Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text (more info). 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 transportation effects more than visualization and edition.

The option to show Fōrmulæ programs and their results is showing images. Unfortunately images cannot be uploaded in Rosetta Code.

Go[edit]

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] = 0
res[1] = 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) [][2]int {
maxLen := -1
maxFusc := -1
f := fusc(n)
var res [][2]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, [2]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][1]), commatize(res[i][0]))
}
}
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)

Haskell[edit]

fusc :: Int -> Int
fusc 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)

J[edit]

 
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 70
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!: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│037117335499
├─────┼─┼──┼────┼─────┤
│value│0111081076
└─────┴─┴──┴────┴─────┘
 
 

Java[edit]

 
 
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] = 0;
fusc[1] = 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] = 0
fusc[37] = 11
fusc[1,173] = 108
fusc[35,499] = 1,076
fusc[699,051] = 10,946
fusc[19,573,419] = 103,682

JavaScript[edit]

Functional[edit]

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[0];
 
// head :: [a] -> a
const head = xs => xs.length ? xs[0] : 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[1];
 
// 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[edit]

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)
end
end
 
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
end
end
 
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[edit]

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] = 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[edit]

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)
end
end
 
function numLen(n)
local sum = 1
while n > 9 do
n = math.floor(n / 10)
sum = sum + 1
end
return sum
end
 
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
end
end
 
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

Nim[edit]

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 = 0
for 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

Pascal[edit]

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
MaxIdx =1253*1000*1000;//19573420; // must be even
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]:= 0;
FF[1]:= 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[0];// 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[edit]

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 Stern-Brocot 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 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:
              0 : 0
             37 : 11
          1,173 : 108
         35,499 : 1,076
        699,051 : 10,946

Phix[edit]

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[1]
fuscs[2] = 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

Prolog[edit]

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).
 
number_length(N, L):-
number_string(N, S),
string_length(S, L).
 
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),
number_length(F, L),
(L > Max ->
writef('n = %w, fusc(n) = %w\n', [M, F]), Max1 = L
;
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[edit]

Procedural[edit]

from collections import deque
from itertools import islice, count
 
 
def fusc():
q = deque([1])
yield 0
yield 1
 
while True:
x = q.popleft()
q.append(x)
yield x
 
x += q[0]
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[edit]

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, islice
from 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[0], 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, [1])
)
)
)
 
 
# Or as a function over an integer:
 
# fusc :: Int -> Int
def 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)[0]
)
 
 
# 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] -> String
def showList(xs):
'''Compact stringification of a list.'''
return '[' + ','.join(repr(x) for x in xs) + ']'
 
 
# take :: Int -> [a] -> [a]
# take :: Int -> String -> String
def 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)

Racket[edit]

#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[edit]

(formerly Perl 6)

Works with: Rakudo version 2018.12
my @Stern-Brocot;
@Stern-Brocot = 0, 1, 1, { |(@Stern-Brocot[$_ - 1] + @Stern-Brocot[$_], @Stern-Brocot[$_]) given ++$+1 } ... *;
 
sub comma { $^i.flip.comb(3).join(',').flip }
 
put "First 61 terms of the Stern-Brocot sequence:\n{@Stern-Brocot[^61].gist}" ~
"\n\nIndex and value for first term longer than any previous:";
 
for flat 'Index', 'Value', 0, 0, (1..4).map({
my $l = 10**$_;
@Stern-Brocot.first(* > $l, :kv).map: *.&comma
}) -> $i, $v {
printf "%15s : %s\n", $i, $v
}
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

REXX[edit]

/*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
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 _
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 inputs of:     0   999999999   5
═══index═══   ═══fusc number═══
        0              0
       37             11
    1,173            108
   35,499          1,076
  699,051         10,946

Ring[edit]

 
# Project: Fusc sequence
 
max = 60
fusc = list(36000)
fusc[1] = 1
see "working..." + nl
see "wait for done..." + nl
see "The first 61 fusc numbers are:" + nl
fuscseq(max)
see "0"
for m = 1 to max
see " " + fusc[m]
next
 
see nl
see "The fusc numbers whose length > any previous fusc number length are:" + nl
see "Index Value" + nl
see " 0 0" + nl
d = 10
for i = 1 to 36000
if fusc[i] >= d
see " " + i + " " + fusc[i] + nl
if d = 0
d = 1
ok
d = d*10
ok
next
see "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[edit]

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

Sidef[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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 Sub
End 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[edit]

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 = 1
var n = 2
while (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[0]))  %(iv[1])")
}
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[edit]

fuscs:=List.createLong(1_000_000, 0); fuscs[1]=1; // we'll just use a big count
foreach 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