Fusc sequence: Difference between revisions
Added Easylang
(Frugal version) |
(Added Easylang) |
||
| (16 intermediate revisions by 8 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 688 ⟶ 689:
</pre>
=={{header|
==={{header|BASIC256}}===
<syntaxhighlight lang="basic256">global f, max
max = 36000
Line 721 ⟶ 723:
next n
end subroutine</syntaxhighlight>
=={{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 1,199 ⟶ 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#}}==
Line 1,408 ⟶ 1,492:
=={{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}}==
Line 2,113 ⟶ 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}}==
Line 3,282 ⟶ 3,487:
===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
{| class="wikitable"
! RPL code
Line 3,755 ⟶ 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}}
<syntaxhighlight lang="
System.print("The first 61 numbers in the fusc sequence are:")
| |||