Fusc sequence: Difference between revisions
Added Easylang
(Added Easylang) |
|||
| (24 intermediate revisions by 12 users not shown) | |||
Line 39:
;Related task:
:* [[Calkin-Wilf sequence]].
<!-- This is similar as "generate primes by trial division", and "generate primes via a sieve". Both Rosetta Code tasks have their uses and methods of generation. !~-->
Line 51 ⟶ 52:
{{trans|Kotlin}}
<
V res = [0] * n
res[1] = 1
Line 68 ⟶ 69:
I String(f[i]).len > max_len
max_len = String(f[i]).len
print((i, f[i]))</
{{out}}
Line 85 ⟶ 86:
=={{header|Ada}}==
<
with Ada.Integer_Text_IO;
Line 180 ⟶ 181:
Print_Small_Fuscs;
Print_Large_Fuscs (High => 20_000_000);
end Show_Fusc;</
{{out}}
Line 196 ⟶ 197:
=={{header|ALGOL 68}}==
<
# calculate some members of the fusc sequence #
# f0 = 0, f1 = 1, fn = f(n/2) if n even #
Line 235 ⟶ 236:
FI
OD
END</
{{out}}
<pre>
Line 249 ⟶ 250:
=={{header|AppleScript}}==
<
if (n < 2) then
return n
Line 272 ⟶ 273:
end repeat
return {sequence:sequence, firstLongest:firstLongest, indexThereof:indexThereof}</
{{output}}
<pre>{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}</pre>
Line 279 ⟶ 280:
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:
<
on fusc()
-- Terms of the Fusc sequence
Line 543 ⟶ 544:
set my text item delimiters to dlm
s
end unlines</
{{Out}}
<pre>First 61 terms:
Line 556 ⟶ 557:
=={{header|Arturo}}==
{{trans|Nim}}
<syntaxhighlight lang="rebol">fusc: function [n][
if? or? n=0 n=1 -> n
else [
Line 585 ⟶ 584:
]
]
]</
{{out}}
Line 601 ⟶ 600:
=={{header|AutoHotkey}}==
<
while (StrLen(fusc[n]) < 5)
Line 614 ⟶ 613:
l := StrLen(v), result .= i "`t" v "`n"
MsgBox % result</
{{out}}
<pre>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
Line 626 ⟶ 625:
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f FUSC_SEQUENCE.AWK
# converted from C
Line 677 ⟶ 676:
return(sum)
}
</syntaxhighlight>
{{out}}
<pre>
Line 690 ⟶ 689:
</pre>
=={{header|
==={{header|BASIC256}}===
<syntaxhighlight lang="basic256">global f, max
max = 36000
dim f(max)
Line 722:
end if
next n
end subroutine</
=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
<syntaxhighlight lang="bbcbasic"> 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)</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|BQN}}==
Line 728 ⟶ 763:
<code>Fusc</code> computes fusc numbers iteratively.
<
{
𝕩∾+´(⍷(⌈∾⌊)2÷˜≠𝕩)⊑¨<𝕩
Line 736 ⟶ 771:
•Show Fusc 61
•Show >⟨"Index"‿"Number"⟩∾{((1+↕4)⊐˜(⌊1+10⋆⁼1⌈|)¨𝕩){𝕨∾𝕨⊑𝕩}¨<𝕩} Fusc 99999</
<
┌─
╵ "Index" "Number"
Line 744 ⟶ 779:
1173 108
35499 1076
┘</
=={{header|C}}==
<syntaxhighlight lang="c">
#include<limits.h>
#include<stdio.h>
Line 797 ⟶ 832:
return 0;
}
</syntaxhighlight>
Prints first 61 Fusc numbers followed by the largest numbers :
<pre>
Line 874 ⟶ 909:
=={{header|C sharp|C#}}==
<
using System.Collections.Generic;
Line 915 ⟶ 950:
l.Clear();
}
}</
{{out}}
<pre>First 61 numbers in the fusc sequence:
Line 930 ⟶ 965:
=={{header|C++}}==
{{trans|C#}}
<
#include <iostream>
#include <limits>
Line 986 ⟶ 1,021:
}
return 0;
}</
{{out}}
<pre>First 61 numbers in the fusc sequence:
Line 1,001 ⟶ 1,036:
=={{header|CLU}}==
{{trans|Python}}
<
q: array[int] := array[int]$[1]
yield(0)
Line 1,049 ⟶ 1,084:
if n = 5 then break end
end
end start_up</
{{out}}
<pre>First 61:
Line 1,062 ⟶ 1,097:
=={{header|D}}==
===Built-in memoization===
<
ulong fusc(ulong n) =>
Line 1,086 ⟶ 1,121:
ndigits = n.fusc.to!string.length.to!int;
}
}</
{{Out}}
<pre>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
Line 1,098 ⟶ 1,133:
=== Manual memoization ===
<
int[] fusc_cache = [0, 1];
Line 1,125 ⟶ 1,160:
ndigits = n.fusc.to!string.length.to!int;
}
}</
{{out}}
<pre>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
Line 1,141 ⟶ 1,176:
=={{header|Dyalect}}==
{{trans|C#}}
<syntaxhighlight lang="dyalect">let n = 61
let l = [0, 1]
Line 1,189 ⟶ 1,222:
}
}
l.Clear()</
{{out}}
Line 1,203 ⟶ 1,236:
699051/10946
19573419/103682</pre>
=={{header|EasyLang}}==
{{trans|Java}}
<syntaxhighlight>
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
.
.
.
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|F_Sharp|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))
</syntaxhighlight>
===The Tasks===
;Print first 62 elements
<
fusc |> Seq.take 61 |> Seq.iter(fun(_,g)->printf "%d " g); printfn ""
</syntaxhighlight>
{{out}}
<pre>
Line 1,222 ⟶ 1,302:
;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)
</syntaxhighlight>
{{out}}
<pre>
Line 1,239 ⟶ 1,319:
=={{header|Factor}}==
<
math.ranges namespaces prettyprint sequences
tools.memory.private ;
Line 1,277 ⟶ 1,357:
[ [ commas ] bi@ "%-6s %-7s\n" printf ] assoc-each ;
MAIN: fusc-demo</
{{out}}
<pre>
Line 1,296 ⟶ 1,376:
=={{header|Forth}}==
<
: fusc ( n -- n) \ input n -- output fusc(n)
Line 1,338 ⟶ 1,418:
bye
</syntaxhighlight>
{{out}}
<pre>
Line 1,352 ⟶ 1,432:
=={{header|FreeBASIC}}==
<
' compile with: fbc -s console
Line 1,399 ⟶ 1,479:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>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
Line 1,413 ⟶ 1,493:
=={{header|Fōrmulæ}}==
{{FormulaeEntry|page=https://formulae.org/?script=examples/Fusc_sequence}}
'''Solution'''
The following function retrieves the n-th fusc number (0-based):
[[File:Fōrmulæ - Fusc sequence 01.png]]
'''1. Showing the first 61 fusc numbers (starting at zero) in a horizontal format'''
[[File:Fōrmulæ - Fusc sequence 02.png]]
[[File:Fōrmulæ - Fusc sequence 03.png]]
A chart of Fusc sequence, from 0 to 256:
[[File:Fōrmulæ - Fusc sequence 04.png]]
[[File:Fōrmulæ - Fusc sequence 05.png]]
'''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.
[[File:Fōrmulæ - Fusc sequence 06.png]]
Testing with 100,000 numbers
[[File:Fōrmulæ - Fusc sequence 07.png]]
[[File:Fōrmulæ - Fusc sequence 08.png]]
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.
[[File:Fōrmulæ - Fusc sequence 09.png]]
[[File:Fōrmulæ - Fusc sequence 10.png]]
'''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.
=={{header|Go}}==
<
import (
Line 1,489 ⟶ 1,609:
fmt.Printf("%7s (index %10s)\n", commatize(res[i][1]), commatize(res[i][0]))
}
}</
{{out}}
Line 1,507 ⟶ 1,627:
=={{header|Groovy}}==
{{trans|Java}}
<
static void main(String[] args) {
println("Show the first 61 fusc numbers (starting at zero) in a horizontal format")
Line 1,545 ⟶ 1,665:
}
}
}</
{{out}}
<pre>Show the first 61 fusc numbers (starting at zero) in a horizontal format
Line 1,559 ⟶ 1,679:
=={{header|Haskell}}==
<
fusc :: Int -> Int
Line 1,595 ⟶ 1,715:
((w <=) . length . show . snd)
(fi . succ . fst)
(fi i)</
{{Out}}
<pre>First 61 terms:
Line 1,608 ⟶ 1,728:
Another version using infinite list:
<
zipWithLazy f ~(x : xs) ~(y : ys) =
f x y : zipWithLazy f xs ys
Line 1,628 ⟶ 1,748:
print $ take 61 fuscs
putStrLn "\n(Index, Value):"
mapM_ print $ take 5 widths</
{{out}}
<pre>
Line 1,643 ⟶ 1,763:
=={{header|J}}==
<syntaxhighlight lang="j">
fusc_term =: ({~ -:@#)`([: +/ ({~ ([: -: _1 1 + #)))@.(2 | #)
fusc =: (, fusc_term)@:]^:[ 0 1"_
Line 1,663 ⟶ 1,783:
└─────┴─┴──┴────┴─────┘
</syntaxhighlight>
=={{header|Java}}==
<syntaxhighlight lang="java">
public class FuscSequence {
Line 1,701 ⟶ 1,821:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,719 ⟶ 1,839:
===Functional===
{{Trans|Python}}
A composition of pure generic functions:
<syntaxhighlight lang="javascript">(() => {
"use strict";
// ---------------------- FUSC -----------------------
// fusc :: Int -> Int
const go = n =>
0 === n ? [
1, 0
] : (() => {
const [x, y] = go(Math.floor(n / 2));
[x + y, y]
) : [x, x + y];
})();
)
};
// ---------------------- TEST -----------------------
return
(
)
.map(([i, x]) => `(${i}, ${x})`)
]
.join("\n");
};
//
const
[x, j] = Array.from(
until(
v => w <= `${v[0]}`.length
)(
v => fi(1 + v[1])
)(fi(i))
);
};
};
// ---------------- GENERIC FUNCTIONS ----------------
//
const
n => Array.from({
length: 1 + n - m
}, (_, i) => m + i);
//
// (a -> b) -> (a -> c) -> (a -> (b, c))
const fanArrow = f =>
// A combined function,
// from x to a tuple of (f(x), g(x
// ((,) . f
//
const
// 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));
// MAIN ---
return main();
})();</
{{Out}}
<pre>First 61 terms:
Line 1,923 ⟶ 1,963:
'''Preliminaries'''
<
def commatize:
# "," is 44
Line 1,931 ⟶ 1,971:
| reverse | implode ;
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;</
'''Fusc Sequence'''
<
def fusc:
0, 1,
Line 1,966 ⟶ 2,006:
"\nFirst terms longer than any previous ones for indices < \($mx + 0 |commatize):",
" Index Value",
fusc($mx)</
{{out}}
<pre>
Line 1,984 ⟶ 2,024:
=={{header|Julia}}==
<
@memoize function sternbrocot(n)
Line 2,011 ⟶ 2,051:
println("The first 61 fusc numbers are: ", [sternbrocot(x) for x in 0:60])
fusclengths()
</
<pre>
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,
Line 2,026 ⟶ 2,066:
=={{header|Kotlin}}==
{{trans|Go}}
<
fun fusc(n: Int): IntArray {
Line 2,068 ⟶ 2,108:
System.out.printf("%,7d (index %,10d)\n", r.second, r.first)
}
}</
{{output}}
Line 2,086 ⟶ 2,126:
=={{header|Lua}}==
{{trans|C}}
<
n = math.floor(n)
if n == 0 or n == 1 then
Line 2,128 ⟶ 2,168:
end
main()</
{{out}}
<pre>Index-------Value
Line 2,198 ⟶ 2,238:
35499 1076
699051 10946</pre>
=={{header|M2000 Interpreter}}==
=====Using Array=====
<syntaxhighlight lang="m2000 interpreter">
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 700000
</syntaxhighlight>
=====Using 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.
<syntaxhighlight lang="m2000 interpreter">
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
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
Fusc[0] := 0
Fusc[1] := 1
Line 2,215 ⟶ 2,335:
i++;
];
res</
{{out}}
<pre>{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}
Line 2,223 ⟶ 2,343:
===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.
<
func fusc(n: int): int =
Line 2,245 ⟶ 2,365:
if length > maxLength:
maxLength = length
echo fmt"{i:9} {f:9}"</
{{out}}
<pre>
Line 2,264 ⟶ 2,384:
{{trans|Python}}
This is a translation of the Python procedural algorithm, using iterators instead of generators. It allows to compute the seven first Fusc numbers whose lengths are greater than those of previous Fusc numbers.
<
Line 2,314 ⟶ 2,434:
echo &"fusc({i}) = {f}"
if count == LongestCount:
break</
{{out}}
Line 2,328 ⟶ 2,448:
fusc(19573419) = 103682
fusc(615164587) = 1010747</pre>
=={{header|OCaml}}==
<syntaxhighlight lang="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)</syntaxhighlight>
Compiled by ''ocamlopt'' the program finishes in about 8 minutes.
{{out}}
<pre>
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
</pre>
With <code>take 8</code>, a further line would be output after almost 3 hours:
<pre>102334155 @ 366503875925</pre>
=={{header|Pascal}}==
Line 2,333 ⟶ 2,491:
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
<
uses
sysutils;
Line 2,459 ⟶ 2,617:
setlength(FuscField,0);
{$IFDEF WIN}readln;{$ENDIF}
END.</
{{Out}}
<pre>First 61 fusc numbers:
Line 2,489 ⟶ 2,647:
=={{header|Perl}}==
Borrowing from the [http://rosettacode.org/wiki/Stern-Brocot_sequence Stern-Brocot sequence] task.
<
use warnings;
use feature 'say';
Line 2,513 ⟶ 2,671:
printf("%15s : %s\n", comma($i), comma($v)) and $l = length $v if length $v > $l;
$i++;
}</
{{out}}
<pre>First 61 terms of the Fusc sequence:
Line 2,528 ⟶ 2,686:
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.
<!--<
<span style="color: #008080;">constant</span> <span style="color: #000000;">limit</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">20_000_000</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">fuscs</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">);</span> <span style="color: #000080;font-style:italic;">-- NB 1-based indexing; fusc(0)===fuscs[1]</span>
Line 2,548 ⟶ 2,706:
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</
{{out}}
<pre>
Line 2,565 ⟶ 2,723:
=={{header|Picat}}==
<
println("First 61 fusc numbers:"),
println([fusc(I) : I in 0..60]),
Line 2,593 ⟶ 2,751:
LargestLen1 = LargestLen
),
largest_fusc_string(N+1,Limit,LargestLen1).</
{{out}}
Line 2,610 ⟶ 2,768:
=={{header|Processing}}==
<
println("First 61 terms:");
for (int i = 0; i < 60; i++) {
Line 2,636 ⟶ 2,794:
return fusc((n - 1) / 2) + fusc((n + 1) / 2);
}
}</
{{out}}
<pre>First 61 terms:
Line 2,650 ⟶ 2,808:
=={{header|Prolog}}==
{{works with|SWI Prolog}}
<
fusc(0, 0):-!.
Line 2,704 ⟶ 2,862:
main:-
print_fusc_sequence(61),
print_max_fusc(1000000).</
{{out}}
Line 2,720 ⟶ 2,878:
=={{header|Python}}==
===Procedural===
<
from itertools import islice, count
Line 2,753 ⟶ 2,911:
for i, f in islice(longest_fusc(), 6):
print(f'fusc({i}) = {f}')
</syntaxhighlight>
{{out}}
<pre>First 61:
Line 2,768 ⟶ 2,926:
===Functional===
By composition of pure functions, avoiding mutable variables, and confining any unavoidables to the internals of well-tested primitives:
<
from itertools import chain, count, islice
Line 2,893 ⟶ 3,051:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>First 61 terms:
Line 2,907 ⟶ 3,065:
=={{header|Quackery}}==
<syntaxhighlight lang="quackery">
[ 1 & ] is odd ( n --> b )
Line 2,946 ⟶ 3,103:
else [ nip swap ]
dup size 1000000 = until ]
2drop</
{{out}}
Line 2,964 ⟶ 3,121:
Our first step is to adapt the 0-indexed definition to our 1-indexed language, letting us complete the first task.
<
{
stopifnot(n > 0)
Line 2,978 ⟶ 3,135:
}
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:
<
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:
<
twentyMillionCountable <- format(twentyMillion, scientific = FALSE, trim = TRUE)
indices <- sapply(2:6, function(x) which.max(nchar(twentyMillionCountable) == x))
Line 2,993 ⟶ 3,150:
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"))</
{{Out}}
<pre>The first 61 Fusc numbers are:
Line 3,006 ⟶ 3,163:
=={{header|Racket}}==
<syntaxhighlight lang="racket">#lang racket
(require racket/generator)
Line 3,050 ⟶ 3,206:
(for ([i (in-range 5)] [x gen])
(match-define (list index result) x)
(printf "~a: ~a\n" (comma index) (comma result)))</
{{out}}
Line 3,066 ⟶ 3,222:
(formerly Perl 6)
=== Recurrence ===
<syntaxhighlight lang="raku"
sub comma { $^i.flip.comb(3).join(',').flip }
Line 3,078 ⟶ 3,234:
}) -> $i, $v {
printf "%15s : %s\n", $i, $v
}</
{{out}}
<pre>First 61 terms of the Fusc sequence:
Line 3,093 ⟶ 3,249:
=== Recursive ===
Alternative version using Raku's multiple-dispatch feature. This version is significantly slower than the one above, but it's definitely prettier.
<syntaxhighlight lang="raku" line>
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;</
{{out}}
<pre>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</pre>
Line 3,104 ⟶ 3,260:
=={{header|REXX}}==
=== version 1, standard formatting ===
<
parse arg st # xw . /*obtain optional arguments from the CL*/
if st=='' | st=="," then st= 0 /*Not specified? Then use the default.*/
Line 3,129 ⟶ 3,285:
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg ?; do _=length(?)-3 to 1 by -3; ?=insert(',', ?, _); end; return ?</
{{out|output|text= when using the default inputs:}}
Line 3,147 ⟶ 3,303:
=== version 2, formatted with rows re─starting whenever a '''1''' (unity) appears ===
<
parse arg st # xw . /*obtain optional arguments from the CL*/
if st=='' | st=="," then st= 0 /*Not specified? Then use the default.*/
Line 3,183 ⟶ 3,339:
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg ?; do _=length(?)-3 to 1 by -3; ?=insert(',', ?, _); end; return ?</
{{out|output|text= when using the default inputs:}}
(Shown at '''70%''' size.)
Line 3,203 ⟶ 3,359:
=={{header|Ring}}==
<
# Project: Fusc sequence
Line 3,242 ⟶ 3,398:
ok
next
</syntaxhighlight>
{{out}}
<pre>
Line 3,256 ⟶ 3,412:
35499 1076
done...
</pre>
=={{header|RPL}}==
{{works with|Halcyon Calc|4.2.7}}
{| class="wikitable"
! 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
|}
{{in}}
<pre>
61 TASK1
2000 TASK2
</pre>
{{out}}
<pre>
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) }
</pre>
===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 <code>fusc(2^n)=1</code> and <code>fusc(2^n+1)=n+1</code>, this formula can seriously improve speed for big values of n, as the iteration could start at <code>2^floor(log2(n))</code> instead of 2.
{| class="wikitable"
! 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
|}
{{in}}
<pre>
36000 TASK2
</pre>
{{out}}
<pre>
1: { (0,0) (11,37) (1173,108) (35499,1076) }
</pre>
=={{header|Ruby}}==
Using two Enumerators; the second making use of the first:
<
y << 0
y << 1
Line 3,285 ⟶ 3,549:
puts fusc.take(61).join(" ")
fusc_max_digits.take(6).each{|pair| puts "%15s : %s" % pair }
</syntaxhighlight>
{{out}}
<pre>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
Line 3,297 ⟶ 3,561:
=={{header|Rust}}==
<
let mut sequence = vec![0, 1];
let mut n = 0;
Line 3,332 ⟶ 3,596:
}
}
}</
{{out}}
Line 3,349 ⟶ 3,613:
=={{header|Sidef}}==
<
return 0 if n.is_zero
Line 3,368 ⟶ 3,632:
len = fusc(index).len
printf("%15s : %s\n", index.commify, fusc(index).commify)
}</
{{out}}
<pre>
Line 3,383 ⟶ 3,647:
=={{header|Swift}}==
<syntaxhighlight lang="swift">struct FuscSeq: Sequence, IteratorProtocol {
private var arr = [0, 1]
private var i = 0
Line 3,424 ⟶ 3,687:
print("New max: \(i): \(n)")
}
}</
{{out}}
Line 3,437 ⟶ 3,700:
=={{header|Tcl}}==
<
if {$n < 2} {
return $n
Line 3,482 ⟶ 3,745:
}
}
doit</
{{out}}
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
Line 3,494 ⟶ 3,757:
real 2m5.559s
=={{header|uBasic/4tH}}==
{{trans|C}}
Only numbers up to 35500 are listed, otherwise it would take an unreasonable amount of time to run this program.
<syntaxhighlight lang="text">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</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|Vala}}==
{{trans|Nim}}
<
if (n == 0 || n == 1)
return n;
Line 3,522 ⟶ 3,894:
}
}
}</
{{out}}
<pre>
Line 3,540 ⟶ 3,912:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Dim n As Integer = 61, l As List(Of Integer) = {0, 1}.ToList
Line 3,576 ⟶ 3,948:
End Sub
End Module
</syntaxhighlight>
{{out}}
<pre>First 61 numbers in the fusc sequence:
Line 3,588 ⟶ 3,960:
699,051 10,946
19,573,419 103,682
</pre>
=={{header|V (Vlang)}}==
<syntaxhighlight lang="Zig">
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)}
}
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Wren}}==
{{libheader|Wren-fmt}}
<
System.print("The first 61 numbers in the fusc sequence are:")
Line 3,618 ⟶ 4,032:
}
n = n + 1
}</
{{out}}
Line 3,636 ⟶ 4,050:
=={{header|XPL0}}==
<
int N, L;
[L:= 0;
Line 3,664 ⟶ 4,078:
];
];
]</
{{out}}
Line 3,678 ⟶ 4,092:
=={{header|Yabasic}}==
<
dim f(maximo)
Line 3,707 ⟶ 4,121:
end if
next n
end sub</
{{out}}
<pre>Igual que la entrada de FreeBASIC.</pre>
=={{header|zkl}}==
<
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] )
Line 3,726 ⟶ 4,140:
f,fd := fuscs[n], f.numDigits;
if(fd>prevMax){ println("%15,d : %,d".fmt(n,f)); prevMax=fd }
}</
{{out}}
<pre>
| |||