Fusc sequence

From Fōrmulæ wiki
Jump to: navigation, search

This page is the answer to the task Fusc sequence in the Rosetta Code.

Description (from Rosetta Code)

Definitions

The fusc integer sequence is defined as:

  • fusc(0) = 0
  • fusc(1) = 1
  • for n>1, the nth term is defined as:
    • if n is even; fusc(n) = fusc(n/2)
    • if n is odd; fusc(n) = fusc((n-1)/2) + fusc((n+1)/2)

Note that MathWorld's definition starts with unity, not zero. This task will be using the OEIS' version (above).

An observation

  • fusc(A) = fusc(B)

where A is some non-negative integer expressed in binary, and where B is the binary value of   A reversed.

Fusc numbers are also known as:

  • fusc function   (by Dijkstra, 1982)
  • Stern's Diatomic series (although it starts with unity, not zero)
  • Stern-Brocot sequence (although it starts with unity, not zero)

Task

  • Show the first   61   fusc numbers (starting at zero) in a horizontal format.
  • Show the fusc number (and its index) whose length is greater than any previous fusc number length.
    • (the length is the number of digits when the fusc number is expressed in decimal.)
  • Show all numbers with commas   (if appropriate).
  • Show all output here.

Related task

Also see

Answers

Task 1. Showing the first 61 fusc numbers (starting at zero) in a horizontal format.

First, let us define the Fusc function:

FuscSequenceCode1.png

FuscSequenceOutput1.png

Task 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 n parameter is the maximum Fusc number to be calculated.

FuscSequenceCode2.png

The first column is the index, and the second one is the Fusc number.

FuscSequenceOutput2.png

Notes:

  • It is faster but requires much more memory. The last call involved the creation of a list of 20'000,000 numbers.
  • The first number (and index) is 1 and not 0, because the call of Digits(0) produces an empty list instead of a list with the digit 0.

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, see Visualization of numbers

The following is an example of the output if you are in France.

FuscSequenceOutput2FR.png

The following is an example of the output if you are in Italy.

FuscSequenceOutput2IT.png