Values
The Wythoff array has the values
- (sequence A035513 in the OEIS ).
In mathematics, the Wythoff array is an infinite matrix of positive integers derived from the Fibonacci sequence and named after Dutch mathematician Willem Abraham Wythoff. Every positive integer occurs exactly once in the array, and every integer sequence defined by the Fibonacci recurrence can be derived by shifting a row of the array.
The Wythoff array was first defined by Morrison (1980) using Wythoff pairs, the coordinates of winning positions in Wythoff's game. It can also be defined using Fibonacci numbers and Zeckendorf's theorem, or directly from the golden ratio and the recurrence relation defining the Fibonacci numbers.
The Wythoff array has the values
Inspired by a similar Stolarsky array previously defined by Stolarsky (1977), Morrison (1980) defined the Wythoff array as follows. Let denote the golden ratio; then the th winning position in Wythoff's game is given by the pair of positive integers , where the numbers on the left and right sides of the pair define two complementary Beatty sequences that together include each positive integer exactly once. Morrison defines the first two numbers in row of the array to be the Wythoff pair given by the equation , and where the remaining numbers in each row are determined by the Fibonacci recurrence relation. That is, if denotes the entry in row and column of the array, then
The Zeckendorf representation of any positive integer is a representation as a sum of distinct Fibonacci numbers, no two of which are consecutive in the Fibonacci sequence. As Kimberling (1995) describes, the numbers within each row of the array have Zeckendorf representation that differ by a shift operation from each other, and the numbers within each column have Zeckendorf representations that all use the same smallest Fibonacci number. In particular the entry of the array is the th smallest number whose Zeckendorf representation begins with the th Fibonacci number.
Each Wythoff pair occurs exactly once in the Wythoff array, as a consecutive pair of numbers in the same row, with an odd index for the first number and an even index for the second. Because each positive integer occurs in exactly one Wythoff pair, each positive integer occurs exactly once in the array ( Morrison 1980 ).
Every sequence of positive integers satisfying the Fibonacci recurrence occurs, shifted by at most finitely many positions, in the Wythoff array. In particular, the Fibonacci sequence itself is the first row, and the sequence of Lucas numbers appears in shifted form in the second row ( Morrison 1980 ).
In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive. All primitive recursive functions are total and computable, but the Ackermann function illustrates that not all total computable functions are primitive recursive.
In mathematics, the Fibonacci sequence is a sequence in which each element is the sum of the two elements that precede it. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted Fn . Many writers begin the sequence with 0 and 1, although some authors start it from 1 and 1 and some from 1 and 2. Starting from 0 and 1, the sequence begins
In mathematics, two quantities are in the golden ratio if their ratio is the same as the ratio of their sum to the larger of the two quantities. Expressed algebraically, for quantities and with , is in a golden ratio to if
In number theory, Euler's totient function counts the positive integers up to a given integer n that are relatively prime to n. It is written using the Greek letter phi as or , and may also be called Euler's phi function. In other words, it is the number of integers k in the range 1 ≤ k ≤ n for which the greatest common divisor gcd(n, k) is equal to 1. The integers k of this form are sometimes referred to as totatives of n.
In mathematics, the floor function is the function that takes as input a real number x, and gives as output the greatest integer less than or equal to x, denoted ⌊x⌋ or floor(x). Similarly, the ceiling function maps x to the least integer greater than or equal to x, denoted ⌈x⌉ or ceil(x).
In mathematics, the discriminant of a polynomial is a quantity that depends on the coefficients and allows deducing some properties of the roots without computing them. More precisely, it is a polynomial function of the coefficients of the original polynomial. The discriminant is widely used in polynomial factoring, number theory, and algebraic geometry.
In mathematics, a recurrence relation is an equation according to which the th term of a sequence of numbers is equal to some combination of the previous terms. Often, only previous terms of the sequence appear in the equation, for a parameter that is independent of ; this number is called the order of the relation. If the values of the first numbers in the sequence have been given, the rest of the sequence can be calculated by repeatedly applying the equation.
The Lucas sequence is an integer sequence named after the mathematician François Édouard Anatole Lucas (1842–1891), who studied both that sequence and the closely related Fibonacci sequence. Individual numbers in the Lucas sequence are known as Lucas numbers. Lucas numbers and Fibonacci numbers form complementary instances of Lucas sequences.
In number theory, a formula for primes is a formula generating the prime numbers, exactly and without exception. Formulas for calculating primes do exist; however, they are computationally very slow. A number of constraints are known, showing what such a "formula" can and cannot be.
In number theory, the nth Pisano period, written as π(n), is the period with which the sequence of Fibonacci numbers taken modulo n repeats. Pisano periods are named after Leonardo Pisano, better known as Fibonacci. The existence of periodic functions in Fibonacci numbers was noted by Joseph Louis Lagrange in 1774.
In mathematics, Zeckendorf's theorem, named after Belgian amateur mathematician Edouard Zeckendorf, is a theorem about the representation of integers as sums of Fibonacci numbers.
A Fibonacci word is a specific sequence of binary digits. The Fibonacci word is formed by repeated concatenation in the same way that the Fibonacci numbers are formed by repeated addition.
In mathematics, the Fibonacci numbers form a sequence defined recursively by:
In mathematics, a Beatty sequence is the sequence of integers found by taking the floor of the positive multiples of a positive irrational number. Beatty sequences are named after Samuel Beatty, who wrote about them in 1926.
In algebra, the greatest common divisor of two polynomials is a polynomial, of the highest possible degree, that is a factor of both the two original polynomials. This concept is analogous to the greatest common divisor of two integers.
Wythoff's game is a two-player mathematical subtraction game, played with two piles of counters. Players take turns removing counters from one or both piles; when removing counters from both piles, the numbers of counters removed from each pile must be equal. The game ends when one player removes the last counter or counters, thus winning.
The Lambek–Moser theorem is a mathematical description of partitions of the natural numbers into two complementary sets. For instance, it applies to the partition of numbers into even and odd, or into prime and non-prime. There are two parts to the Lambek–Moser theorem. One part states that any two non-decreasing integer functions that are inverse, in a certain sense, can be used to split the natural numbers into two complementary subsets, and the other part states that every complementary partition can be constructed in this way. When a formula is known for the th natural number in a set, the Lambek–Moser theorem can be used to obtain a formula for the th number not in the set.
In mathematics and statistics, sums of powers occur in a number of contexts:
In mathematics, the Fibonomial coefficients or Fibonacci-binomial coefficients are defined as
The Meissel–Lehmer algorithm is an algorithm that computes exact values of the prime-counting function.
