Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 Fusc

Source Notebook

Evaluate the fusc function

Contributed by: Christopher Stover

ResourceFunction["Fusc"][n]

gives the fusc function fusc(n).

Details

Integer mathematical function, suitable for both symbolic and numerical manipulation.
ResourceFunction["Fusc"] is defined by the recurrence relation fusc(0)=0, fusc(1)=1, fusc(2m)=fusc(m) and fusc(2m+1)=fusc(m)+fusc(m+1).
According to author Edsger W. Dijkstra (EWD 570), the fusc function is named for the obfuscated appearance of its output.
ResourceFunction["Fusc"] automatically threads over lists.

Examples

Basic Examples (3) 

Evaluate numerically for positive even integer input:

In[1]:=
ResourceFunction["Fusc"][12]
Out[1]=

Evaluate numerically for positive odd integer input:

In[2]:=
ResourceFunction["Fusc"][31]
Out[2]=

Plot Fusc over a subset of the non-negative integers:

In[3]:=
ListPlot[Table[ResourceFunction["Fusc"][n], {n, 0, 2048}]]
Out[3]=

Scope (1) 

Fusc threads elementwise over lists:

In[4]:=
ResourceFunction["Fusc"][{3, 5, 11, 21, 162, 247000000}]
Out[4]=

Applications (4) 

The value fusc(n+1) is the number of odd binomial coefficients of the form Binomial[n-r,r], 0≤2r≤n:

In[5]:=
fuscs = Table[ResourceFunction["Fusc"][n + 1], {n, 0, 100}]
Out[6]=
In[7]:=
bins = Table[ Length@Select[Table[Binomial[n - r, r], {r, 0, n, 2}], OddQ[#] &], {n, 0, 200, 2}]
Out[7]=

Confirm the two lists are equal:

In[8]:=
fuscs == bins
Out[8]=

An alternative way to compute the same quantity:

In[9]:=
bins2 = Count[#, _?(OddQ[#] &)] & /@ Table[Binomial[n - r, r], {n, 0, 200, 2}, {r, 0, n, 2}]
Out[9]=

Confirm all three are equal:

In[10]:=
fuscs == bins == bins2
Out[10]=

Possible Issues (1) 

Fusc returns unevaluated if its input is anything other than a non-negative integer:

In[11]:=
(* Evaluate this cell to get the example input *) CloudGet["https://www.wolframcloud.com/obj/b55a9f4f-d97d-49df-ab3f-862b4578984c"]
Out[11]=

Neat Examples (3) 

Generate the first 100 terms of Stern's diatomic series, also known as the Stern–Brocot sequence (OEIS A002487):

In[12]:=
ResourceFunction["Fusc"] /@ Range[0, 99]
Out[12]=

When used in conjunction with Prime, you can generate OEIS sequences A261179 and A261273:

In[13]:=
ResourceFunction["Fusc"][#] & /@ (Prime[#] & /@ Range[1, 100])
Out[13]=
In[14]:=
ResourceFunction["Fusc"][# + 1] & /@ (Prime[#] & /@ Range[1, 100])
Out[14]=

These two sequences combine to form the prime numbered elements in the Calkin–Wilf sequence, one popular enumeration of the rational numbers. More precisely, the terms of the Calkin–Wilf enumeration of the rationals are given by fusc(n)/fusc(n+1):

In[15]:=
Table[ResourceFunction["Fusc"][n]/ResourceFunction["Fusc"][n + 1], {n, 0, 50}]
Out[15]=

Publisher

therealcstover

Version History

  • 1.0.0 – 09 September 2022

Source Metadata

  • Citation:
    • Dijkstra, E. W., Selected Writings on Computing: A Personal Perspective, EWD570 and EWD578. New York: Springer-Verlag, 1982.

Related Resources

License Information