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)
- Task
-
- show the first 61 fusc numbers (starting at zero) in a horizontal format.
- show the fusc number (and its index) whose length is greater than any previous fusc number length.
- (the length is the number of decimal digits when the fusc number is expressed in base ten.)
- show all numbers with commas (if appropriate).
- show all output here.
- Related task
- Also see
-
- the MathWorld entry: Stern's Diatomic Series.
- the OEIS entry: A2487.
11l
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
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
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
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)
Arturo
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
AutoHotkey
fusc:=[], fusc[0]:=0, fusc[1]:=1, n:=1, l:=0, result:=""
while (StrLen(fusc[n]) < 5)
fusc[++n] := Mod(n, 2) ? fusc[floor((n-1)/2)] + fusc[Floor((n+1)/2)] : fusc[floor(n/2)]
while (A_Index <= 61)
result .= (result = "" ? "" : ",") fusc[A_Index-1]
result .= "`n`nfusc number whose length is greater than any previous fusc number length:`nindex`tnumber`n"
for i, v in fusc
if (l < StrLen(v))
l := StrLen(v), result .= i "`t" v "`n"
MsgBox % 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 fusc number whose length is greater than any previous fusc number length: index number 0 0 37 11 1173 108 35499 1076 699051 10946
AWK
# 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
BASIC
BASIC256
global f, max
max = 36000
dim f(max)
call fusc()
for i = 0 to 60
print f[i]; " ";
next i
print : print
print " Index Value"
d = 0
for i = 0 to max-1
if f[i] >= d then
print rjust(string(i),10," "), rjust(string(f[i]),10," ")
if d = 0 then d = 1
d *= 10
end if
next i
end
subroutine fusc()
f[0] = 0 : f[1] = 1
for n = 2 to max-1
if (n mod 2) then
f[n] = f[(n-1)/2] + f[(n+1)/2]
else
f[n] = f[n/2]
end if
next n
end subroutineBBC BASIC
DIM Idx%(4)
L%=1
F%=FNfusc(I%)
PRINT "First 61 numbers:"
WHILE L% < 5
IF I% < 61 PRINT;F% ",";
I%+=1
F%=FNfusc(I%)
IF LOGF% > L% Idx%(L%)=I% : L%+=1
ENDIF
ENDWHILE
PRINT CHR$127 ''"Number of digits in sequence increase at:"
FOR I%=0 TO L%-1
PRINT ;Idx%(I%) ",";FNfusc(Idx%(I%))
NEXT
END
DEF FNfusc(n%)
IF n% < 2 THEN =n%
IF n% AND 1 THEN =FNfusc((n%-1)/2) + FNfusc((n%+1)/2)
=FNfusc(n%/2)
- Output:
First 61 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 Number of digits in sequence increase at: 0,0 37,11 1173,108 35499,1076 699051,10946
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++
#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
CLU
fusc = iter () yields (int)
q: array[int] := array[int]$[1]
yield(0)
yield(1)
while true do
x: int := array[int]$reml(q)
array[int]$addh(q,x)
yield(x)
x := x + array[int]$bottom(q)
array[int]$addh(q,x)
yield(x)
end
end fusc
longest_fusc = iter () yields (int,int)
sofar: int := 0
count: int := 0
for f: int in fusc() do
if f >= sofar then
yield (count,f)
sofar := 10*sofar
if sofar=0 then sofar:=10 end
end
count := count + 1
end
end longest_fusc
start_up = proc ()
po: stream := stream$primary_output()
stream$putl(po, "First 61:")
n: int := 0
for f: int in fusc() do
stream$puts(po, int$unparse(f) || " ")
n := n + 1
if n = 61 then break end
end
stream$putl(po, "\nLength records:")
n := 0
for i, f: int in longest_fusc() do
stream$putl(po, "fusc(" || int$unparse(i) || ") = " || int$unparse(f))
n := n + 1
if n = 5 then break end
end
end start_up- 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
D
Built-in memoization
import std.functional, std.stdio, std.format, std.conv;
ulong fusc(ulong n) =>
memoize!fuscImp(n);
ulong fuscImp(ulong n) =>
( n < 2 ) ? n :
( n % 2 == 0 ) ? memoize!fuscImp( n/2 ) :
memoize!fuscImp( (n-1)/2 ) + memoize!fuscImp( (n+1)/2 );
void main() {
const N_FIRST=61;
const MAX_N_DIGITS=5;
format!"First %d fusc numbers: "(N_FIRST).write;
foreach( n; 0..N_FIRST ) n.fusc.format!"%d ".write;
writeln;
format!"\nFusc numbers with more digits than any previous (1 to %d digits):"(MAX_N_DIGITS).writeln;
for(auto n=0, ndigits=0; ndigits<MAX_N_DIGITS; n++)
if( n.fusc.to!string.length > ndigits ){
format!"fusc(%d)=%d"( n, n.fusc ).writeln;
ndigits = n.fusc.to!string.length.to!int;
}
}
- 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 any previous (1 to 5 digits): fusc(0)=0 fusc(37)=11 fusc(1173)=108 fusc(35499)=1076 fusc(699051)=10946
Manual memoization
import std.stdio, std.format, std.conv;
int[] fusc_cache = [0, 1];
int fusc(int n) {
// Ensure cache contains all missing numbers until n
for(auto i=fusc_cache.length;i<=n;i++)
fusc_cache ~= i%2 == 0
? fusc_cache[i/2]
: fusc_cache[(i-1)/2] + fusc_cache[(i + 1)/2];
// Solve using cache
return fusc_cache[n];
}
void main() {
const N_FIRST=61;
const MAX_N_DIGITS=6;
format!"First %d fusc numbers: "(N_FIRST).write;
foreach( n; 0..N_FIRST ) n.fusc.format!"%d ".write;
writeln;
format!"\nFusc numbers with more digits than any previous (1 to %d digits):"(MAX_N_DIGITS).writeln;
for(auto n=0, ndigits=0; ndigits<MAX_N_DIGITS; n++)
if( n.fusc.to!string.length > ndigits ){
format!"fusc(%d)=%d"( n, n.fusc ).writeln;
ndigits = n.fusc.to!string.length.to!int;
}
}
- 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 any previous (1 to 6 digits): fusc(0)=0 fusc(37)=11 fusc(1173)=108 fusc(35499)=1076 fusc(699051)=10946 fusc(19573419)=103682
Delphi
See Pascal.
Dyalect
let n = 61
let l = [0, 1]
func fusc(n) {
return l[n] when n < l.Length()
let f = (n &&& 1) == 0 ? l[n >>> 1] : l[(n - 1) >>> 1] + l[(n + 1) >>> 1]
l.Add(f)
return f
}
var lst = true
var w = -1
var c = 0
var t = nil
var res = ""
print("First \(n) numbers in the fusc sequence:")
for i in 0..Integer.Max {
let f = fusc(i)
if lst {
if i < 61 {
print("\(f) ", terminator: "")
} else {
lst = false
print("")
print("Points in the sequence where an item has more digits than any previous items:")
print("Index/Value:")
print(res)
res = ""
}
}
t = f.ToString().Length()
if t > w {
w = t
res += (res == "" ? "" : "\n") + "\(i)/\(f)"
if !lst {
print(res)
res = ""
}
c += 1
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 1173/108 35499/1076 699051/10946 19573419/103682
EasyLang
FUSCMAX = 20000000
len fusc[] FUSCMAX + 1
arrbase fusc[] 0
#
fusc[0] = 0
fusc[1] = 1
for n = 2 to FUSCMAX
if n mod 2 = 0
fusc[n] = fusc[n / 2]
else
fusc[n] = fusc[(n - 1) / 2] + fusc[(n + 1) / 2]
.
.
for n = 0 to 60
write fusc[n] & " "
.
print ""
print ""
for i = 0 to 5
val = -1
if i <> 0
val = floor pow 10 i
.
for j = start to FUSCMAX
if fusc[j] > val
print "fusc[" & j & "] = " & fusc[j]
start = j
break 1
.
.
.
- 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[0] = 0 fusc[37] = 11 fusc[1173] = 108 fusc[35499] = 1076 fusc[699051] = 10946 fusc[19573419] = 103682
F#
The Function
// 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
- 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.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 ] 2bi@ + ]
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 ] bi@ "%-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
Forth
\ Gforth 0.7.9_20211014
: fusc ( n -- n) \ input n -- output fusc(n)
dup dup 0= swap 1 = or \ n = 0 or 1
if exit \ return n
else dup 2 mod 0= \ test even
if 2/ recurse \ even fusc(n)= fusc(n/2)
else dup 1- 2/ recurse \ odd fusc(n) = fusc((n-1)/2) +
swap 1+ 2/ recurse + \ fusc((n+1)/2)
then
then
;
: cntDigits ( n -- n ) \ returns the numbers of digits
0 begin 1+ swap
10 /
swap over
0= until
swap drop
;
: fuscLen ( n -- ) \ count until end index
cr 1 swap 0
do
i fusc cntDigits
over > if 1+
." fusc( " i . ." ) : "
i fusc . cr
then
loop
;
: firstFusc ( n -- ) \ show fusc(i) until limit
dup ." First " . ." fusc(n) : " cr
0 do I fusc . loop cr
;
61 firstFusc
20 1000 1000 * * fuscLen
bye
- Output:
First 61 fusc(n) : 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( 37 ) : 11 fusc( 1173 ) : 108 fusc( 35499 ) : 1076 fusc( 699051 ) : 10946 fusc( 19573419 ) : 103682
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, 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
FutureBasic
_max = 20000000
begin globals
NSUInteger f(_max)
end globals
void local fn Fusc
f(0) = 0 : f(1) = 1
for NSUInteger n = 2 to _max
if ( n & 1 )
f(n) = f((n - 1) / 2) + f((n + 1) / 2)
else
f(n) = f(n / 2)
end if
next
end fn
void local fn DoIt
NSUInteger i, d = 0
fn Fusc
for i = 0 to 60
print f(i);" ";
if ( i == 32 ) then print
next
print : print : print @" index\t\t value"
for i = 0 to _max
if ( f(i) >= d )
printf @"%11lu\t\t%6lu",i,f(i)
if ( d == 0 ) then d = 1
d *= 10
end if
next
end fn
fn DoIt
HandleEvents- 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
1173 108
35499 1076
699051 10946
19573419 103682
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.
In this page you can see and run the program(s) related to this task and their results. You can also change either the programs or the parameters they are called with, for experimentation, but remember that these programs were created with the main purpose of showing a clear solution of the task, and they generally lack any kind of validation.
Solution
The following function retrieves the n-th fusc number (0-based):
1. Showing the first 61 fusc numbers (starting at zero) in a horizontal format
A chart of Fusc sequence, from 0 to 256:
2. Showing the Fusc number (and its index) whose length is greater than any previous Fusc number length
The Fusc function previously defined is slow. In the next program results are stored in a list for future retrieving.
The argument n is the maximum Fusc number to be calculated.
Testing with 100,000 numbers
Testing with 20,000,000 numbers
It is faster but requires much more memory. The next call involves the creation of a list of 20'000,000 numbers.
3. Showing all numbers with commas (if appropriate)
In Fōrmulæ, all numbers are shown with group separator when necessary. In fact, the group separator is not always the comma, it depends of the locale.
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] = 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)
Groovy
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] = 0
fusc[1] = 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] = 0 fusc[37] = 11 fusc[1,173] = 108 fusc[35,499] = 1,076 fusc[699,051] = 10,946 fusc[19,573,419] = 103,682
Haskell
---------------------- FUSC SEQUENCE ---------------------
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)
--------------------------- TEST -------------------------
main :: IO ()
main = do
putStrLn "First 61 terms:"
print $ fusc <$> [0 .. 60]
putStrLn "\n(Index, Value):"
mapM_ print $ take 5 widths
widths :: [(Int, Int)]
widths =
fmap
(\(_, i, x) -> (i, x))
(iterate nxtWidth (2, 0, 0))
nxtWidth :: (Int, Int, Int) -> (Int, Int, Int)
nxtWidth (w, i, v) = (succ w, j, x)
where
fi = (,) <*> fusc
(j, x) =
until
((w <=) . length . show . snd)
(fi . succ . fst)
(fi 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] (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 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│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] = 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
Functional
A composition of pure generic functions:
(() => {
"use strict";
// ---------------------- FUSC -----------------------
// fusc :: Int -> Int
const fusc = i => {
const go = n =>
0 === n ? [
1, 0
] : (() => {
const [x, y] = go(Math.floor(n / 2));
return 0 === n % 2 ? (
[x + y, y]
) : [x, x + y];
})();
return 1 > i ? (
0
) : go(i - 1)[0];
};
// ---------------------- TEST -----------------------
const main = () => {
const terms = enumFromTo(0)(60).map(fusc);
return [
"First 61 terms:",
`[${terms.join(",")}]`,
"",
"(Index, Value):",
firstWidths(5).reduce(
(a, x) => [x.slice(1), ...a],
[]
)
.map(([i, x]) => `(${i}, ${x})`)
.join("\n")
]
.join("\n");
};
// firstWidths :: Int -> [(Int, Int)]
const firstWidths = n => {
const nxtWidth = xs => {
const
fi = fanArrow(fusc)(x => x),
[w, i] = xs[0],
[x, j] = Array.from(
until(
v => w <= `${v[0]}`.length
)(
v => fi(1 + v[1])
)(fi(i))
);
return [
[1 + w, j, x],
...xs
];
};
return until(x => n < x[0][0])(
nxtWidth
)([
[2, 0, 0]
]);
};
// ---------------- GENERIC FUNCTIONS ----------------
// enumFromTo :: Int -> Int -> [Int]
const enumFromTo = m =>
n => Array.from({
length: 1 + n - m
}, (_, i) => m + i);
// fanArrow (&&&) ::
// (a -> b) -> (a -> c) -> (a -> (b, c))
const fanArrow = f =>
// A combined function, given f and g,
// from x to a tuple of (f(x), g(x))
// ((,) . f <*> g)
g => x => [f(x), g(x)];
// until :: (a -> Bool) -> (a -> a) -> a -> a
const until = p =>
// The value resulting from successive applications
// of f to f(x), starting with a seed value x,
// and terminating when the result returns true
// for the predicate p.
f => {
const go = x =>
p(x) ? x : go(f(x));
return go;
};
// 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)
jq
Adapted from Wren
Works with gojq, the Go implementation of jq
Preliminaries
# input should be a non-negative integer
def commatize:
# "," is 44
def digits: tostring | explode | reverse;
[foreach digits[] as $d (-1; .+1;
(select(. > 0 and . % 3 == 0)|44), $d)]
| reverse | implode ;
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;Fusc Sequence
# Save space by truncating the beginning of the array
def fusc:
0, 1,
foreach range(2; infinite) as $n ([0, 1];
($n % 2 == 0) as $even
| if $even then . + [.[1]] else.[1:] + [.[1] + .[2]] end;
.[-1] );
# Report first longest
def fusc( $mx ):
def l: commatize|lpad(10);
foreach limit( $mx; fusc ) as $f ({ maxLen: 0, n: 0 };
.emit = false
| ("\($f)"|length) as $len
| if $len > .maxLen
then .maxLen = $len
| .emit = "\(.n|l) \($f|commatize)"
else .
end
| .n += 1
;
select(.emit).emit
);
# First $first numbers in the fusc sequence
61 as $first
| 2e6 as $mx
| "The first \($first) numbers in the fusc sequence are:",
([limit($first; fusc)]| map(tostring) | join(" ")) ,
"\nFirst terms longer than any previous ones for indices < \($mx + 0 |commatize):",
" Index Value",
fusc($mx)- 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
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)
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
// 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
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
M2000 Interpreter
Using Array
module Fusc_sequence (max as long) {
long n, max_len=-1, m
string fmt="#,##0", fs="{0:-10} : {1}"
dim f(0 to max) as long
f(0)=0, 1
for n=2 To max{If binary.and(n,1) Then f(n)=f((n-1)/2)+f((n+1)/2) else f(n)=f(n/2)}
print "First 61 terms:"
print "["+f()#slice(0,60)#str$(", ")+"]"
print "Points in the sequence where an item has more digits than any previous items:"
print format$(fs, "index", "value")
for n=0 to max{if f(n)>=max_len then m++:max_len=10&**m:print format$(fs,str$(n,fmt),str$(f(n),fmt)):refresh}
}
Fusc_sequence 700000Using Generator
M2000 has no Yield statement, but has Events for call back, or the use of call back functions. The Lazy(&f1()) pass the reference of f1 plus the same scope as the current scope (where we apply the lazy() function). The lazy function used also to pass expressions for lazy evaluation, using the scope from where we pass the expression.
Number pop a number from stack of values. StackItem() return the value (pick value from top of stack). Data append value to stack of values (normally we use Push to add items at the top of stack - like LIFO - but here we use FIFO).
We use an object to send feedback (to end the generation of the series) through noStop member. The call k(x) is the call back function.
module Fusc_sequence (level) {
class z {
boolean noStop=true
module generate(&k()) {
object q=stack:=1
call k(0)
call k(1)
stack q {
x=number:data x:call k(x)
x+=stackitem():data x:call k(x)
if .noStop then loop
}
q=stack
.noStop<=true
}
}
z=z()
long max=61, n, k=-1, m
string fmt="#,##0", fs="{0:-10} : {1}", prev
function f1(new x) {
n++
if n=1 then print "First 61 terms:":print "[";
if n<max then
print x+", ";
else.if n=max then
print x+"]"
z.noStop=false
end if
}
profiler
z.generate lazy$(&f1())
print "Points in the sequence where an item has more digits than any previous items:"
print format$(fs, "index", "value")
n=0: max=level
function f2(new x) {if x>=k then m++:k=10&**m:print format$(fs,str$(n,fmt),str$(x,fmt)):if m=max then z.noStop=false
n++}
z.generate lazy$(&f2())
print timecount
}
Fusc_sequence 5- 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:
index : value
0 : 0
37 : 11
1,173 : 108
35,499 : 1,076
699,051 : 10,946
Mathematica / Wolfram Language
ClearAll[Fusc]
Fusc[0] := 0
Fusc[1] := 1
Fusc[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 = 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
Using iterators and double queues (deques)
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 = [1].toDeque()
yield 0
yield 1
while true:
var val = q.popFirst()
q.addLast(val)
yield val
val += q[0]
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 = -1
for f in fusc():
inc i
stdout.write f
if i == MaxFusc:
echo ""
break
stdout.write ' '
echo "\nLength records:"
var count = 0
for (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
OCaml
let seq_fusc =
let rec next x xs () =
match xs () with
| Seq.Nil -> assert false
| Cons (x', xs') -> Seq.Cons (x' + x, Seq.cons x' (next x' xs'))
in
let rec tail () = Seq.Cons (1, next 1 tail) in
Seq.cons 0 (Seq.cons 1 tail)
let seq_first_of_lengths =
let rec next i l sq () =
match sq () with
| Seq.Nil -> Seq.Nil
| Cons (x, xs) when x >= l -> Cons ((i, x), next (succ i) (10 * l) xs)
| Cons (_, xs) -> next (succ i) l xs ()
in next 0 10
let () =
seq_fusc |> Seq.take 61 |> Seq.iter (Printf.printf " %u") |> print_newline
and () =
seq_fusc |> seq_first_of_lengths |> Seq.take 7
|> Seq.iter (fun (i, x) -> Printf.printf "%9u @ %u%!\n" x i)
Compiled by ocamlopt the program finishes in about 8 minutes.
- 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
11 @ 37
108 @ 1173
1076 @ 35499
10946 @ 699051
103682 @ 19573419
1010747 @ 615164587
10059505 @ 18611524949
With take 8, a further line would be output after almost 3 hours:
102334155 @ 366503875925
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]:= 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
PascalABC.NET
const maxcalc = 100000000;
var cache := new integer[maxcalc];
function Fusc(n: integer): integer;
begin
if (n = 0) or (n = 1) then
begin
Result := n;
exit
end;
if (n < maxcalc) and (cache[n] > 0) then
begin
Result := cache[n];
exit;
end;
if n.IsEven then
Result := Fusc(n div 2)
else Result := Fusc((n-1) div 2) + Fusc((n+1) div 2);
if n < maxcalc then
cache[n] := Result
end;
function Digits(n: integer): integer;
begin
Result := 0;
while n > 0 do
begin
Result += 1;
n := n div 10;
end;
end;
begin
(0..60).Select(Fusc).Println;
var maxdigits := 1;
var num := 0;
var prevfun := 0;
for var i:=1 to integer.MaxValue - 1 do
begin
var fun := Fusc(i);
if fun > prevfun then
begin
var dig := Digits(fun);
if dig > maxdigits then
begin
maxdigits := dig;
Println(fun,i);
num +=1;
if num = 6 then exit;
end;
end;
prevfun := fun;
end;
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 11 37 108 1173 1076 35499 10946 699051 103682 19573419 1010747 615164587
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[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
Picat
main =>
println("First 61 fusc numbers:"),
println([fusc(I) : I in 0..60]),
nl,
println("Points in the sequence whose length is greater than any previous fusc number length:\n"),
println(" Index fusc Len"),
largest_fusc_string(20_000_000).
table
fusc(0) = 0.
fusc(1) = 1.
fusc(N) = fusc(N//2), even(N) => true.
fusc(N) = fusc((N-1)//2) + fusc((N+1)//2) => true.
largest_fusc_string(Limit) =>
largest_fusc_string(0,Limit,0).
largest_fusc_string(Limit,Limit,_).
largest_fusc_string(N,Limit,LargestLen) :-
N <= Limit,
F = fusc(N),
Len = F.to_string.len,
(Len > LargestLen ->
printf("%8d %8d %4d\n",N,F,Len),
LargestLen1 = Len
;
LargestLen1 = LargestLen
),
largest_fusc_string(N+1,Limit,LargestLen1).- 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]
Points in the sequence whose length is greater than any previous fusc number length:
Index fusc Len
0 0 1
37 11 2
1173 108 3
35499 1076 4
699051 10946 5
19573419 103682 6
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
:- 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 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
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)
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.
firstNFuscNumbers <- function(n)
{
stopifnot(n > 0)
if(n == 1) return(0) else fusc <- c(0, 1)
if(n > 2)
{
for(i in seq(from = 3, to = n, by = 1))
{
fusc[i] <- if(i %% 2) fusc[(i + 1) / 2] else fusc[i / 2] + fusc[(i + 2) / 2]
}
}
fusc
}
first61 <- firstNFuscNumbers(61)
cat("The first 61 Fusc numbers are:", "\n", first61, "\n")
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=61 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, "\n")
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 <- firstNFuscNumbers(2 * 10^7)
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:
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 first fusc number that is longer than all previous fusc numbers is 11 and it occurs at index 38 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 = 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...
RPL
| RPL code | Comment |
|---|---|
≪
IF DUP #1 > THEN
IF DUP #1 AND B→R
THEN SR DUP FUSC SWAP 1 + FUSC +
ELSE SR FUSC
END END
≫ ‘FUSC’ STO
≪ { 0 1 }
WHILE DUP2 SIZE > REPEAT
DUP DUP SIZE 2 / 1 + GET LAST
SWAP
IF DUP FP THEN IP GET + ELSE DROP2 END
+
END SWAP DROP
≫ 'TASK1' STO
≪ { (0,0) } 1
1 4 ROLL FOR j
j R→B FUSC B→R
SWAP OVER →STR SIZE
IF DUP2 <
THEN SWAP DROP SWAP ROT SWAP j R→C + SWAP
ELSE ROT DROP2 END
2 STEP DROP
≫ 'TASK2' STO
|
FUSC ( #n -- #fusc(#n) )
if #n is odd
fusc(#n) = fusc(#n//2) + fusc(#n//2+1)
else fusc(#n) = fusc(#n//2)
TASK1 ( n -- { fusc(1)..fusc(n) } )
loop n-2 times
get fusc(ceiling(n/2))
correct the 'LAST after GET' emulator bug
if n odd, add fusc(floor(n/2))
add to list
clean stack
TASK2 ( n -- { (fusc(a),a) .. )
loop n-2 times
get fusc(j)
get length(fusc(j))
if greater then previous ones
update list
else clean stack
consider odd j only
|
- Input:
61 TASK1 2000 TASK2
- Output:
2: { 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 }
1: { (0,0) (11,37) (108,1173) }
Frugal version
Based on Mike Stay's formula, this program does not need recursion or storage of n/2 previous terms, and is faster.
Since fusc(2^n)=1 and fusc(2^n+1)=n+1, this formula can seriously improve speed for big values of n, as the iteration could start at 2^floor(log2(n)) instead of 2.
| RPL code | Comment |
|---|---|
≪
{ (0,0) } 0 0 1
2 6 ROLL FOR j
DUP2 + LAST MOD 2 * - ROT DROP
IF DUP XPON 4 PICK >
THEN ROT DROP DUP XPON ROT ROT
4 ROLL OVER j SWAP R→C + 4 ROLLD END
NEXT 3 DROPN
≫ 'TASK2' STO
|
TASK2 ( n -- { (a,fusc(a)).. )
initialize stack: result list, length, fusc(0) and fusc(1)
loop n-2 times
fusc(j) = jusc(j-2) + fusc(j-1) - 2*(fusc(j-2) mod fusc(j-1))
if new length record
update record in stack
add (j,fusc(j)) to list
clean stack
|
- Input:
36000 TASK2
- Output:
1: { (0,0) (11,37) (1173,108) (35499,1076) }
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
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
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
uBasic/4tH
Only numbers up to 35500 are listed, otherwise it would take an unreasonable amount of time to run this program.
Print "Index-------Value"
For i = 0 To 60
Print Using "____#"; i; Using "___________#"; FUNC(_fusc(i))
Next
Proc _printLargeFuscs (35500)
End
_fusc
Param (1)
If (a@ = 0) + (a@ = 1) Then Return (a@)
If (a@ % 2) = 0 Then Return (FUNC(_fusc(a@/2)))
Return (FUNC(_fusc((a@ - 1)/2)) + FUNC(_fusc((a@ + 1)/2)))
_printLargeFuscs
Param (1)
Local (4) ' (int) i, f, len, maxLen = 1
e@ = 1
Print "\n\nPrinting all largest Fusc numbers upto "; a@; "\nIndex-------Value"
For b@ = 0 To a@
c@ = FUNC(_fusc(b@))
d@ = Len(Str(c@))
If d@ > e@ Then
e@ = d@
Print Using "____#"; b@; Using "___________#"; c@
EndIf
Next
Return
- 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 upto 35500
Index-------Value
37 11
1173 108
35499 1076
0 OK, 0:145
Vala
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
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
V (Vlang)
fn main() {
mut max_len, mut temp := 0, 0
println("First 61 terms:")
for i := 0; i < 60; i++ {
print("${fusc(i)} ")
}
println(fusc(60))
println("\nNumbers whose length is greater than any previous fusc number length:")
println("Index:\tValue:")
// less than 700,000 used
for i := 0; i < 700000; i++ {
temp = fusc(i)
if temp.str().len > max_len {
max_len = temp.str().len
println("${i}\t${temp}")
}
}
}
fn fusc(n int) int {
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 Numbers whose length is greater than any previous fusc number length: Index: Value: 0 0 37 11 1173 108 35499 1076 699051 10946
Wren
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
XPL0
func IntLen(N); \Return number of digits in N
int N, L;
[L:= 0;
repeat N:= N/10;
L:= L+1;
until N = 0;
return L;
];
def Size = 1000000;
int Fusc(Size), N, Len, Max;
[Fusc(0):= 0; Fusc(1):= 1;
for N:= 2 to Size-1 do
Fusc(N):= if N&1 then Fusc((N-1)/2) + Fusc((N+1)/2) else Fusc(N/2);
for N:= 0 to 60 do
[IntOut(0, Fusc(N)); ChOut(0, ^ )];
Text(0, "
n fusc(n)
");
Max:= 0;
for N:= 0 to Size-1 do
[Len:= IntLen(Fusc(N));
if Len > Max then
[Max:= Len;
IntOut(0, N); ChOut(0, 9\tab\);
IntOut(0, Fusc(N)); CrLf(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 n fusc(n) 0 0 37 11 1173 108 35499 1076 699051 10946
Yabasic
maximo = 20000000
dim f(maximo)
fusc()
for i = 0 to 60
print f(i), " ";
next i
print "\n\n Index Value"
d = 0
for i = 0 to maximo-1
if f(i) >= d then
print i using "###,###,###", f(i) using "###,###,###"
if d = 0 d = 1
d = d * 10
end if
next i
end
sub fusc()
f(0) = 0 : f(1) = 1
for n = 2 to maximo-1
if mod(n, 2) then
f(n) = f((n-1) / 2) + f((n+1) / 2)
else
f(n) = f(n / 2)
end if
next n
end sub
- Output:
Igual que la entrada de FreeBASIC.
zkl
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
Categories:
- Programming Tasks
- Solutions by Programming Task
- 11l
- Ada
- ALGOL 68
- AppleScript
- Arturo
- AutoHotkey
- AWK
- BASIC
- BASIC256
- BBC BASIC
- BQN
- C
- C sharp
- C++
- CLU
- D
- Delphi
- Dyalect
- EasyLang
- F Sharp
- Factor
- Forth
- FreeBASIC
- FutureBasic
- Fōrmulæ
- Go
- Groovy
- Haskell
- J
- Java
- JavaScript
- Jq
- Julia
- Kotlin
- Lua
- M2000 Interpreter
- Mathematica
- Wolfram Language
- Nim
- OCaml
- Pascal
- PascalABC.NET
- Perl
- Phix
- Picat
- Processing
- Prolog
- Python
- Quackery
- R
- Racket
- Raku
- REXX
- Ring
- RPL
- Ruby
- Rust
- Sidef
- Swift
- Tcl
- UBasic/4tH
- Vala
- Visual Basic .NET
- V (Vlang)
- Wren
- Wren-fmt
- XPL0
- Yabasic
- Zkl