1.
On-Line Encyclopedia of Integer Sequences
–
The On-Line Encyclopedia of Integer Sequences, also cited simply as Sloanes, is an online database of integer sequences. It was created and maintained by Neil Sloane while a researcher at AT&T Labs, Sloane continues to be involved in the OEIS in his role as President of the OEIS Foundation. OEIS records information on integer sequences of interest to professional mathematicians and amateurs, and is widely cited. As of 30 December 2016 it contains nearly 280,000 sequences, the database is searchable by keyword and by subsequence. Neil Sloane started collecting integer sequences as a student in 1965 to support his work in combinatorics. The database was at first stored on punched cards and he published selections from the database in book form twice, A Handbook of Integer Sequences, containing 2,372 sequences in lexicographic order and assigned numbers from 1 to 2372. The Encyclopedia of Integer Sequences with Simon Plouffe, containing 5,488 sequences and these books were well received and, especially after the second publication, mathematicians supplied Sloane with a steady flow of new sequences. The collection became unmanageable in book form, and when the database had reached 16,000 entries Sloane decided to go online—first as an e-mail service, as a spin-off from the database work, Sloane founded the Journal of Integer Sequences in 1998. The database continues to grow at a rate of some 10,000 entries a year, Sloane has personally managed his sequences for almost 40 years, but starting in 2002, a board of associate editors and volunteers has helped maintain the database. In 2004, Sloane celebrated the addition of the 100, 000th sequence to the database, A100000, in 2006, the user interface was overhauled and more advanced search capabilities were added. In 2010 an OEIS wiki at OEIS. org was created to simplify the collaboration of the OEIS editors and contributors, besides integer sequences, the OEIS also catalogs sequences of fractions, the digits of transcendental numbers, complex numbers and so on by transforming them into integer sequences. Sequences of rationals are represented by two sequences, the sequence of numerators and the sequence of denominators, important irrational numbers such as π =3.1415926535897. are catalogued under representative integer sequences such as decimal expansions, binary expansions, or continued fraction expansions. The OEIS was limited to plain ASCII text until 2011, yet it still uses a form of conventional mathematical notation. Greek letters are represented by their full names, e. g. mu for μ. Every sequence is identified by the letter A followed by six digits, sometimes referred to without the leading zeros, individual terms of sequences are separated by commas. Digit groups are not separated by commas, periods, or spaces, a represents the nth term of the sequence. Zero is often used to represent non-existent sequence elements, for example, A104157 enumerates the smallest prime of n² consecutive primes to form an n×n magic square of least magic constant, or 0 if no such magic square exists. The value of a is 2, a is 1480028129, but there is no such 2×2 magic square, so a is 0
On-Line Encyclopedia of Integer Sequences
–
On-Line Encyclopedia of Integer Sequences
2.
Number
–
A number is a mathematical object used to count, measure, and label. The original examples are the natural numbers 1,2,3, a notational symbol that represents a number is called a numeral. In addition to their use in counting and measuring, numerals are used for labels, for ordering. In common usage, number may refer to a symbol, a word, calculations with numbers are done with arithmetical operations, the most familiar being addition, subtraction, multiplication, division, and exponentiation. Their study or usage is called arithmetic, the same term may also refer to number theory, the study of the properties of numbers. Besides their practical uses, numbers have cultural significance throughout the world, for example, in Western society the number 13 is regarded as unlucky, and a million may signify a lot. Though it is now regarded as pseudoscience, numerology, the belief in a significance of numbers, permeated ancient. Numerology heavily influenced the development of Greek mathematics, stimulating the investigation of problems in number theory which are still of interest today. During the 19th century, mathematicians began to develop many different abstractions which share certain properties of numbers, among the first were the hypercomplex numbers, which consist of various extensions or modifications of the complex number system. Numbers should be distinguished from numerals, the used to represent numbers. Boyer showed that Egyptians created the first ciphered numeral system, Greeks followed by mapping their counting numbers onto Ionian and Doric alphabets. The number five can be represented by digit 5 or by the Roman numeral Ⅴ, notations used to represent numbers are discussed in the article numeral systems. The Roman numerals require extra symbols for larger numbers, different types of numbers have many different uses. Numbers can be classified into sets, called number systems, such as the natural numbers, the same number can be written in many different ways. For different methods of expressing numbers with symbols, such as the Roman numerals, each of these number systems may be considered as a proper subset of the next one. This is expressed, symbolically, by writing N ⊂ Z ⊂ Q ⊂ R ⊂ C, the most familiar numbers are the natural numbers,1,2,3, and so on. Traditionally, the sequence of numbers started with 1 However, in the 19th century, set theorists. Today, different mathematicians use the term to both sets, including 0 or not
Number
–
The number 605 in
Khmer numerals, from an inscription from 683 AD. An early use of zero as a decimal figure.
Number
–
Subsets of the
complex numbers.
3.
Prime number
–
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a number is called a composite number. For example,5 is prime because 1 and 5 are its only positive integer factors, the property of being prime is called primality. A simple but slow method of verifying the primality of a number n is known as trial division. It consists of testing whether n is a multiple of any integer between 2 and n, algorithms much more efficient than trial division have been devised to test the primality of large numbers. Particularly fast methods are available for numbers of forms, such as Mersenne numbers. As of January 2016, the largest known prime number has 22,338,618 decimal digits, there are infinitely many primes, as demonstrated by Euclid around 300 BC. There is no simple formula that separates prime numbers from composite numbers. However, the distribution of primes, that is to say, many questions regarding prime numbers remain open, such as Goldbachs conjecture, and the twin prime conjecture. Such questions spurred the development of branches of number theory. Prime numbers give rise to various generalizations in other domains, mainly algebra, such as prime elements. A natural number is called a number if it has exactly two positive divisors,1 and the number itself. Natural numbers greater than 1 that are not prime are called composite, among the numbers 1 to 6, the numbers 2,3, and 5 are the prime numbers, while 1,4, and 6 are not prime. 1 is excluded as a number, for reasons explained below. 2 is a number, since the only natural numbers dividing it are 1 and 2. Next,3 is prime, too,1 and 3 do divide 3 without remainder, however,4 is composite, since 2 is another number dividing 4 without remainder,4 =2 ·2. 5 is again prime, none of the numbers 2,3, next,6 is divisible by 2 or 3, since 6 =2 ·3. The image at the right illustrates that 12 is not prime,12 =3 ·4, no even number greater than 2 is prime because by definition, any such number n has at least three distinct divisors, namely 1,2, and n
Prime number
–
The number 12 is not a prime, as 12 items can be placed into 3 equal-size columns of 4 each (among other ways). 11 items cannot be all placed into several equal-size columns of more than 1 item each without some extra items leftover (a remainder). Therefore, the number 11 is a prime.
4.
Binary number
–
The base-2 system is a positional notation with a radix of 2. Because of its implementation in digital electronic circuitry using logic gates. Each digit is referred to as a bit, the modern binary number system was devised by Gottfried Leibniz in 1679 and appears in his article Explication de lArithmétique Binaire. Systems related to binary numbers have appeared earlier in multiple cultures including ancient Egypt, China, Leibniz was specifically inspired by the Chinese I Ching. The scribes of ancient Egypt used two different systems for their fractions, Egyptian fractions and Horus-Eye fractions, the method used for ancient Egyptian multiplication is also closely related to binary numbers. This method can be seen in use, for instance, in the Rhind Mathematical Papyrus, the I Ching dates from the 9th century BC in China. The binary notation in the I Ching is used to interpret its quaternary divination technique and it is based on taoistic duality of yin and yang. Eight trigrams and a set of 64 hexagrams, analogous to the three-bit and six-bit binary numerals, were in use at least as early as the Zhou Dynasty of ancient China. The Song Dynasty scholar Shao Yong rearranged the hexagrams in a format that resembles modern binary numbers, the Indian scholar Pingala developed a binary system for describing prosody. He used binary numbers in the form of short and long syllables, Pingalas Hindu classic titled Chandaḥśāstra describes the formation of a matrix in order to give a unique value to each meter. The binary representations in Pingalas system increases towards the right, the residents of the island of Mangareva in French Polynesia were using a hybrid binary-decimal system before 1450. Slit drums with binary tones are used to encode messages across Africa, sets of binary combinations similar to the I Ching have also been used in traditional African divination systems such as Ifá as well as in medieval Western geomancy. The base-2 system utilized in geomancy had long been applied in sub-Saharan Africa. Leibnizs system uses 0 and 1, like the modern binary numeral system, Leibniz was first introduced to the I Ching through his contact with the French Jesuit Joachim Bouvet, who visited China in 1685 as a missionary. Leibniz saw the I Ching hexagrams as an affirmation of the universality of his own beliefs as a Christian. Binary numerals were central to Leibnizs theology and he believed that binary numbers were symbolic of the Christian idea of creatio ex nihilo or creation out of nothing. Is not easy to impart to the pagans, is the ex nihilo through Gods almighty power. In 1854, British mathematician George Boole published a paper detailing an algebraic system of logic that would become known as Boolean algebra
Binary number
–
Numeral systems
Binary number
–
Arithmetic values represented by parts of the Eye of Horus
Binary number
–
Gottfried Leibniz
Binary number
–
George Boole
5.
Mersenne prime
–
In mathematics, a Mersenne prime is a prime number that is one less than a power of two. That is, it is a number that can be written in the form Mn = 2n −1 for some integer n. They are named after Marin Mersenne, a French Minim friar, the first four Mersenne primes are 3,7,31, and 127. If n is a number then so is 2n −1. The definition is therefore unchanged when written Mp = 2p −1 where p is assumed prime, more generally, numbers of the form Mn = 2n −1 without the primality requirement are called Mersenne numbers. The smallest composite pernicious Mersenne number is 211 −1 =2047 =23 ×89, Mersenne primes Mp are also noteworthy due to their connection to perfect numbers. As of January 2016,49 Mersenne primes are known, the largest known prime number 274,207,281 −1 is a Mersenne prime. Since 1997, all newly found Mersenne primes have been discovered by the “Great Internet Mersenne Prime Search”, many fundamental questions about Mersenne primes remain unresolved. It is not even whether the set of Mersenne primes is finite or infinite. The Lenstra–Pomerance–Wagstaff conjecture asserts that there are infinitely many Mersenne primes,23 | M11,47 | M23,167 | M83,263 | M131,359 | M179,383 | M191,479 | M239, and 503 | M251. Since for these primes p, 2p +1 is congruent to 7 mod 8, so 2 is a quadratic residue mod 2p +1, since p is a prime, it must be p or 1. The first four Mersenne primes are M2 =3, M3 =7, M5 =31, a basic theorem about Mersenne numbers states that if Mp is prime, then the exponent p must also be prime. This follows from the identity 2 a b −1 = ⋅ = ⋅ and this rules out primality for Mersenne numbers with composite exponent, such as M4 =24 −1 =15 =3 ×5 = ×. Though the above examples might suggest that Mp is prime for all p, this is not the case. The evidence at hand does suggest that a randomly selected Mersenne number is more likely to be prime than an arbitrary randomly selected odd integer of similar size. Nonetheless, prime Mp appear to grow increasingly sparse as p increases, in fact, of the 2,270,720 prime numbers p up to 37,156,667, Mp is prime for only 45 of them. The lack of any simple test to determine whether a given Mersenne number is prime makes the search for Mersenne primes a difficult task, the Lucas–Lehmer primality test is an efficient primality test that greatly aids this task. The search for the largest known prime has somewhat of a cult following, consequently, a lot of computer power has been expended searching for new Mersenne primes, much of which is now done using distributed computing
Mersenne prime
–
Graph of number of digits in largest known Mersenne prime by year – electronic era. Note that the vertical scale, the number of digits, is a double logarithmic scale of the value of the prime.
6.
Decimal
–
This article aims to be an accessible introduction. For the mathematical definition, see Decimal representation, the decimal numeral system has ten as its base, which, in decimal, is written 10, as is the base in every positional numeral system. It is the base most widely used by modern civilizations. Decimal fractions have terminating decimal representations and other fractions have repeating decimal representations, Decimal notation is the writing of numbers in a base-ten numeral system. Examples are Brahmi numerals, Greek numerals, Hebrew numerals, Roman numerals, Roman numerals have symbols for the decimal powers and secondary symbols for half these values. Brahmi numerals have symbols for the nine numbers 1–9, the nine decades 10–90, plus a symbol for 100, Chinese numerals have symbols for 1–9, and additional symbols for powers of ten, which in modern usage reach 1072. Positional decimal systems include a zero and use symbols for the ten values to represent any number, positional notation uses positions for each power of ten, units, tens, hundreds, thousands, etc. The position of each digit within a number denotes the multiplier multiplied with that position has a value ten times that of the position to its right. There were at least two independent sources of positional decimal systems in ancient civilization, the Chinese counting rod system. Ten is the number which is the count of fingers and thumbs on both hands, the English word digit as well as its translation in many languages is also the anatomical term for fingers and toes. In English, decimal means tenth, decimate means reduce by a tenth, however, the symbols used in different areas are not identical, for instance, Western Arabic numerals differ from the forms used by other Arab cultures. A decimal fraction is a fraction the denominator of which is a power of ten. g, Decimal fractions 8/10, 1489/100, 24/100000, and 58900/10000 are expressed in decimal notation as 0.8,14.89,0.00024,5.8900 respectively. In English-speaking, some Latin American and many Asian countries, a period or raised period is used as the separator, in many other countries, particularly in Europe. The integer part, or integral part of a number is the part to the left of the decimal separator. The part from the separator to the right is the fractional part. It is usual for a number that consists only of a fractional part to have a leading zero in its notation. Any rational number with a denominator whose only prime factors are 2 and/or 5 may be expressed as a decimal fraction and has a finite decimal expansion. 1/2 =0.5 1/20 =0.05 1/5 =0.2 1/50 =0.02 1/4 =0.25 1/40 =0.025 1/25 =0.04 1/8 =0.125 1/125 =0.008 1/10 =0
Decimal
–
The world's earliest decimal multiplication table was made from bamboo slips, dating from 305 BC, during the
Warring States period in China.
Decimal
–
Numeral systems
Decimal
–
Ten fingers on two hands, the possible starting point of the decimal counting.
Decimal
–
Diagram of the world's earliest decimal multiplication table (c. 305 BC) from the Warring States period
7.
1 (number)
–
1, is a number, a numeral, and the name of the glyph representing that number. It represents a single entity, the unit of counting or measurement, for example, a line segment of unit length is a line segment of length 1. It is also the first of the series of natural numbers. The word one can be used as a noun, an adjective and it comes from the English word an, which comes from the Proto-Germanic root *ainaz. The Proto-Germanic root *ainaz comes from the Proto-Indo-European root *oi-no-, compare the Proto-Germanic root *ainaz to Old Frisian an, Gothic ains, Danish een, Dutch een, German eins and Old Norse einn. Compare the Proto-Indo-European root *oi-no- to Greek oinos, Latin unus, Old Persian aivam, Old Church Slavonic -inu and ino-, Lithuanian vienas, Old Irish oin, One, sometimes referred to as unity, is the first non-zero natural number. It is thus the integer before two and after zero, and the first positive odd number, any number multiplied by one is that number, as one is the identity for multiplication. As a result,1 is its own factorial, its own square, its own cube, One is also the result of the empty product, as any number multiplied by one is itself. It is also the natural number that is neither composite nor prime with respect to division. The Gupta wrote it as a line, and the Nagari sometimes added a small circle on the left. The Nepali also rotated it to the right but kept the circle small and this eventually became the top serif in the modern numeral, but the occasional short horizontal line at the bottom probably originates from similarity with the Roman numeral I. Where the 1 is written with an upstroke, the number 7 has a horizontal stroke through the vertical line. While the shape of the 1 character has an ascender in most modern typefaces, in typefaces with text figures, many older typewriters do not have a separate symbol for 1 and use the lowercase letter l instead. It is possible to find cases when the uppercase J is used,1 cannot be used as the base of a positional numeral system, as the only digit that would be permitted in such a system would be 0. Since the base 1 exponential function always equals 1, its inverse does not exist, there are two ways to write the real number 1 as a recurring decimal, as 1.000. and as 0.999. There is only one way to represent the real number 1 as a Dedekind cut, in a multiplicative group or monoid, the identity element is sometimes denoted 1, but e is also traditional. However,1 is especially common for the identity of a ring. When such a ring has characteristic n not equal to 0,1 is the first figurate number of every kind, such as triangular number, pentagonal number and centered hexagonal number, to name just a few
1 (number)
–
The 24-hour tower clock in
Venice, using J as a symbol for 1.
8.
Base 2
–
The base-2 system is a positional notation with a radix of 2. Because of its implementation in digital electronic circuitry using logic gates. Each digit is referred to as a bit, the modern binary number system was devised by Gottfried Leibniz in 1679 and appears in his article Explication de lArithmétique Binaire. Systems related to binary numbers have appeared earlier in multiple cultures including ancient Egypt, China, Leibniz was specifically inspired by the Chinese I Ching. The scribes of ancient Egypt used two different systems for their fractions, Egyptian fractions and Horus-Eye fractions, the method used for ancient Egyptian multiplication is also closely related to binary numbers. This method can be seen in use, for instance, in the Rhind Mathematical Papyrus, the I Ching dates from the 9th century BC in China. The binary notation in the I Ching is used to interpret its quaternary divination technique and it is based on taoistic duality of yin and yang. Eight trigrams and a set of 64 hexagrams, analogous to the three-bit and six-bit binary numerals, were in use at least as early as the Zhou Dynasty of ancient China. The Song Dynasty scholar Shao Yong rearranged the hexagrams in a format that resembles modern binary numbers, the Indian scholar Pingala developed a binary system for describing prosody. He used binary numbers in the form of short and long syllables, Pingalas Hindu classic titled Chandaḥśāstra describes the formation of a matrix in order to give a unique value to each meter. The binary representations in Pingalas system increases towards the right, the residents of the island of Mangareva in French Polynesia were using a hybrid binary-decimal system before 1450. Slit drums with binary tones are used to encode messages across Africa, sets of binary combinations similar to the I Ching have also been used in traditional African divination systems such as Ifá as well as in medieval Western geomancy. The base-2 system utilized in geomancy had long been applied in sub-Saharan Africa. Leibnizs system uses 0 and 1, like the modern binary numeral system, Leibniz was first introduced to the I Ching through his contact with the French Jesuit Joachim Bouvet, who visited China in 1685 as a missionary. Leibniz saw the I Ching hexagrams as an affirmation of the universality of his own beliefs as a Christian. Binary numerals were central to Leibnizs theology and he believed that binary numbers were symbolic of the Christian idea of creatio ex nihilo or creation out of nothing. Is not easy to impart to the pagans, is the ex nihilo through Gods almighty power. In 1854, British mathematician George Boole published a paper detailing an algebraic system of logic that would become known as Boolean algebra
Base 2
–
Numeral systems
Base 2
–
Gottfried Leibniz
Base 2
–
George Boole
9.
Pigeon-hole principle
–
In mathematics, the pigeonhole principle states that if n items are put into m containers, with n > m, then at least one container must contain more than one item. This theorem is exemplified in real life by truisms like there must be at least two left gloves or two right gloves in a group of three gloves. The first formalization of the idea is believed to have made by Peter Gustav Lejeune Dirichlet in 1834 under the name Schubfachprinzip. For this reason it is commonly called Dirichlets box principle or Dirichlets drawer principle. This should not be confused with Dirichlets principle, an introduced by Riemann that refers to the minimum principle for harmonic functions. The principle has several generalizations and can be stated in various ways, for arbitrary n and m this generalizes to k +1 = ⌊/m⌋ +1, where ⌊. ⌋ is the floor function. Though the most straightforward application is to finite sets, it is used with infinite sets that cannot be put into one-to-one correspondence. To do so requires the formal statement of the pigeonhole principle, advanced mathematical proofs like Siegels lemma build upon this more general concept. Dirichlet published his works in both French and German, the strict original meaning of either the German Schubfach, or the French tiroir, corresponds to the English drawer, an open-topped box that can be slid in and out of the cabinet that contains it. These terms were morphed to the word pigeonhole, standing for an open space in a desk, cabinet, or wall for keeping letters or papers. Assume a drawer contains a mixture of black socks and blue socks, each of which can be worn on either foot, what is the minimum number of pulled socks required to guarantee a pair of the same color. Using the pigeonhole principle, to have at least one pair of the color using one pigeonhole per color. Either you have three of one color, or, exclusively, two of one color and one of the other. If there are n people who can shake hands with one another, as the holes, or m, correspond to number of hands shaken, and each person can shake hands with anybody from 0 to n −1 other people, this creates n −1 possible holes. This is because either the 0 or the n −1 hole must be empty and this leaves n people to be placed in at most n −1 non-empty holes, guaranteeing duplication. We can demonstrate there must be at least two people in London with the number of hairs on their heads as follows. Since a typical human head has an average of around 150,000 hairs, there are more than 1,000,000 people in London. For the average case with the constraint, fewest overlaps, there will be at most one person assigned to every pigeonhole, in the absence of this constraint, there may be empty pigeonholes because the collision happens before we get to the 150, 001st person
Pigeon-hole principle
–
An image of pigeons in holes. Here there are n = 10 pigeons in m = 9 holes. Since 10 is greater than 9, the pigeonhole principle says that at least one hole has more than one pigeon.
10.
Coprime integers
–
In number theory, two integers a and b are said to be relatively prime, mutually prime, or coprime if the only positive integer that divides both of them is 1. That is, the common positive factor of the two numbers is 1. This is equivalent to their greatest common divisor being 1, the numerator and denominator of a reduced fraction are coprime. In addition to gcd =1 and =1, the notation a ⊥ b is used to indicate that a and b are relatively prime. For example,14 and 15 are coprime, being divisible by only 1. The numbers 1 and −1 are the only integers coprime to every integer, a fast way to determine whether two numbers are coprime is given by the Euclidean algorithm. The number of integers coprime to an integer n, between 1 and n, is given by Eulers totient function φ. A set of integers can also be called if its elements share no common positive factor except 1. A set of integers is said to be pairwise coprime if a and b are coprime for every pair of different integers in it, a number of conditions are individually equivalent to a and b being coprime, No prime number divides both a and b. There exist integers x and y such that ax + by =1, the integer b has a multiplicative inverse modulo a, there exists an integer y such that by ≡1. In other words, b is a unit in the ring Z/aZ of integers modulo a, the least common multiple of a and b is equal to their product ab, i. e. LCM = ab. As a consequence of the point, if a and b are coprime and br ≡ bs. That is, we may divide by b when working modulo a, as a consequence of the first point, if a and b are coprime, then so are any powers ak and bl. If a and b are coprime and a divides the product bc and this can be viewed as a generalization of Euclids lemma. In a sense that can be made precise, the probability that two randomly chosen integers are coprime is 6/π2, which is about 61%, two natural numbers a and b are coprime if and only if the numbers 2a −1 and 2b −1 are coprime. As a generalization of this, following easily from the Euclidean algorithm in base n >1, a set of integers S = can also be called coprime or setwise coprime if the greatest common divisor of all the elements of the set is 1. For example, the integers 6,10,15 are coprime because 1 is the positive integer that divides all of them. If every pair in a set of integers is coprime, then the set is said to be pairwise coprime, pairwise coprimality is a stronger condition than setwise coprimality, every pairwise coprime finite set is also setwise coprime, but the reverse is not true
Coprime integers
–
Figure 1. The numbers 4 and 9 are coprime. Therefore, the diagonal of a 4 x 9 lattice does not intersect any other
lattice points
11.
Euclidean Algorithm
–
It is named after the ancient Greek mathematician Euclid, who first described it in Euclids Elements. It is an example of an algorithm, a procedure for performing a calculation according to well-defined rules. It can be used to reduce fractions to their simplest form, the Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example,21 is the GCD of 252 and 105, since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, they are the GCD of the two numbers. By reversing the steps, the GCD can be expressed as a sum of the two numbers each multiplied by a positive or negative integer, e. g.21 =5 ×105 + ×252. The fact that the GCD can always be expressed in this way is known as Bézouts identity, the version of the Euclidean algorithm described above can take many subtraction steps to find the GCD when one of the given numbers is much bigger than the other. A more efficient version of the algorithm shortcuts these steps, instead replacing the larger of the two numbers by its remainder when divided by the smaller of the two. With this improvement, the algorithm never requires more steps than five times the number of digits of the smaller integer and this was proven by Gabriel Lamé in 1844, and marks the beginning of computational complexity theory. Additional methods for improving the algorithms efficiency were developed in the 20th century, the Euclidean algorithm has many theoretical and practical applications. It is used for reducing fractions to their simplest form and for performing division in modular arithmetic, finally, it can be used as a basic tool for proving theorems in number theory such as Lagranges four-square theorem and the uniqueness of prime factorizations. This led to abstract algebraic notions such as Euclidean domains. The Euclidean algorithm calculates the greatest common divisor of two numbers a and b. The greatest common divisor g is the largest natural number that divides both a and b without leaving a remainder, synonyms for the GCD include the greatest common factor, the highest common factor, the highest common divisor, and the greatest common measure. The greatest common divisor is often written as gcd or, more simply, as, although the notation is also used for other mathematical concepts. If gcd =1, then a and b are said to be coprime and this property does not imply that a or b are themselves prime numbers. For example, neither 6 nor 35 is a prime number, nevertheless,6 and 35 are coprime. No natural number other than 1 divides both 6 and 35, since they have no prime factors in common
Euclidean Algorithm
–
The Euclidean algorithm was probably invented centuries before
Euclid, shown here holding a
compass.
Euclidean Algorithm
12.
Integer factorization
–
In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these integers are further restricted to numbers, the process is called prime factorization. When the numbers are large, no efficient, non-quantum integer factorization algorithm is known. However, it has not been proven that no efficient algorithm exists, the presumed difficulty of this problem is at the heart of widely used algorithms in cryptography such as RSA. Many areas of mathematics and computer science have been brought to bear on the problem, including elliptic curves, algebraic number theory, not all numbers of a given length are equally hard to factor. The hardest instances of these problems are semiprimes, the product of two prime numbers, many cryptographic protocols are based on the difficulty of factoring large composite integers or a related problem—for example, the RSA problem. An algorithm that efficiently factors an arbitrary integer would render RSA-based public-key cryptography insecure, by the fundamental theorem of arithmetic, every positive integer has a unique prime factorization. If the integer is then it can be recognized as such in polynomial time. If composite however, the theorem gives no insight into how to obtain the factors, given a general algorithm for integer factorization, any integer can be factored down to its constituent prime factors simply by repeated application of this algorithm. The situation is complicated with special-purpose factorization algorithms, whose benefits may not be realized as well or even at all with the factors produced during decomposition. For example, if N =10 × p × q where p < q are very large primes, trial division will quickly produce the factors 2 and 5 but will take p divisions to find the next factor. Among the b-bit numbers, the most difficult to factor in practice using existing algorithms are those that are products of two primes of similar size, for this reason, these are the integers used in cryptographic applications. The largest such semiprime yet factored was RSA-768, a 768-bit number with 232 decimal digits and this factorization was a collaboration of several research institutions, spanning two years and taking the equivalent of almost 2000 years of computing on a single-core 2.2 GHz AMD Opteron. Like all recent factorization records, this factorization was completed with an optimized implementation of the general number field sieve run on hundreds of machines. No algorithm has been published that can factor all integers in polynomial time, neither the existence nor non-existence of such algorithms has been proved, but it is generally suspected that they do not exist and hence that the problem is not in class P. The problem is clearly in class NP but has not been proved to be in, or not in and it is generally suspected not to be in NP-complete. There are published algorithms that are faster than O for all positive ε, i. e. sub-exponential, the best published asymptotic running time is for the general number field sieve algorithm, which, for a b-bit number n, is, O. For current computers, GNFS is the best published algorithm for large n, for a quantum computer, however, Peter Shor discovered an algorithm in 1994 that solves it in polynomial time
Integer factorization
–
This image demonstrates the prime decomposition of 864. A shorthand way of writing the resulting prime factors is 2 5 × 3 3
13.
OEIS
–
The On-Line Encyclopedia of Integer Sequences, also cited simply as Sloanes, is an online database of integer sequences. It was created and maintained by Neil Sloane while a researcher at AT&T Labs, Sloane continues to be involved in the OEIS in his role as President of the OEIS Foundation. OEIS records information on integer sequences of interest to professional mathematicians and amateurs, and is widely cited. As of 30 December 2016 it contains nearly 280,000 sequences, the database is searchable by keyword and by subsequence. Neil Sloane started collecting integer sequences as a student in 1965 to support his work in combinatorics. The database was at first stored on punched cards and he published selections from the database in book form twice, A Handbook of Integer Sequences, containing 2,372 sequences in lexicographic order and assigned numbers from 1 to 2372. The Encyclopedia of Integer Sequences with Simon Plouffe, containing 5,488 sequences and these books were well received and, especially after the second publication, mathematicians supplied Sloane with a steady flow of new sequences. The collection became unmanageable in book form, and when the database had reached 16,000 entries Sloane decided to go online—first as an e-mail service, as a spin-off from the database work, Sloane founded the Journal of Integer Sequences in 1998. The database continues to grow at a rate of some 10,000 entries a year, Sloane has personally managed his sequences for almost 40 years, but starting in 2002, a board of associate editors and volunteers has helped maintain the database. In 2004, Sloane celebrated the addition of the 100, 000th sequence to the database, A100000, in 2006, the user interface was overhauled and more advanced search capabilities were added. In 2010 an OEIS wiki at OEIS. org was created to simplify the collaboration of the OEIS editors and contributors, besides integer sequences, the OEIS also catalogs sequences of fractions, the digits of transcendental numbers, complex numbers and so on by transforming them into integer sequences. Sequences of rationals are represented by two sequences, the sequence of numerators and the sequence of denominators, important irrational numbers such as π =3.1415926535897. are catalogued under representative integer sequences such as decimal expansions, binary expansions, or continued fraction expansions. The OEIS was limited to plain ASCII text until 2011, yet it still uses a form of conventional mathematical notation. Greek letters are represented by their full names, e. g. mu for μ. Every sequence is identified by the letter A followed by six digits, sometimes referred to without the leading zeros, individual terms of sequences are separated by commas. Digit groups are not separated by commas, periods, or spaces, a represents the nth term of the sequence. Zero is often used to represent non-existent sequence elements, for example, A104157 enumerates the smallest prime of n² consecutive primes to form an n×n magic square of least magic constant, or 0 if no such magic square exists. The value of a is 2, a is 1480028129, but there is no such 2×2 magic square, so a is 0
OEIS
–
On-Line Encyclopedia of Integer Sequences
14.
Prime number theorem
–
In number theory, the prime number theorem describes the asymptotic distribution of the prime numbers among the positive integers. It formalizes the idea that primes become less common as they become larger by precisely quantifying the rate at which this occurs. The theorem was proved independently by Jacques Hadamard and Charles Jean de la Vallée-Poussin in 1896 using ideas introduced by Bernhard Riemann, the first such distribution found is π ~ N/log, where π is the prime-counting function and log is the natural logarithm of N. This means that for large enough N, the probability that an integer not greater than N is prime is very close to 1 / log. Consequently, an integer with at most 2n digits is about half as likely to be prime as a random integer with at most n digits. For example, among the integers of at most 1000 digits, about one in 2300 is prime, whereas among positive integers of at most 2000 digits. In other words, the gap between consecutive prime numbers among the first N integers is roughly log. Let π be the function that gives the number of primes less than or equal to x. For example, π =4 because there are four prime numbers less than or equal to 10, using asymptotic notation this result can be restated as π ∼ x log x. This notation does not say anything about the limit of the difference of the two functions as x increases without bound, instead, the theorem states that x / log x approximates π in the sense that the relative error of this approximation approaches 0 as x increases without bound. For example, the 7017200000000000000♠2×1017th prime number is 7018851267738604819♠8512677386048191063, and log rounds to 7018796741875229174♠7967418752291744388, a relative error of about 6. 4%. The prime number theorem is equivalent to lim x → ∞ ϑ x = lim x → ∞ ψ x =1, where ϑ and ψ are the first. Based on the tables by Anton Felkel and Jurij Vega, Adrien-Marie Legendre conjectured in 1797 or 1798 that π is approximated by the function a /, where A and B are unspecified constants. In the second edition of his book on number theory he made a more precise conjecture. Carl Friedrich Gauss considered the question at age 15 or 16 in the year 1792 or 1793. In 1838 Peter Gustav Lejeune Dirichlet came up with his own approximating function, in two papers from 1848 and 1850, the Russian mathematician Pafnuty Chebyshev attempted to prove the asymptotic law of distribution of prime numbers. He was able to prove unconditionally that this ratio is bounded above, an important paper concerning the distribution of prime numbers was Riemanns 1859 memoir On the Number of Primes Less Than a Given Magnitude, the only paper he ever wrote on the subject. In particular, it is in paper of Riemann that the idea to apply methods of complex analysis to the study of the real function π originates
Prime number theorem
–
Graph showing ratio of the prime-counting function π(x) to two of its approximations, x /log x and Li(x). As x increases (note x axis is logarithmic), both ratios tend towards 1. The ratio for x /log x converges from above very slowly, while the ratio for Li(x) converges more quickly from below.
15.
Permutation
–
These differ from combinations, which are selections of some members of a set where order is disregarded. For example, written as tuples, there are six permutations of the set, namely and these are all the possible orderings of this three element set. As another example, an anagram of a word, all of whose letters are different, is a permutation of its letters, in this example, the letters are already ordered in the original word and the anagram is a reordering of the letters. The study of permutations of finite sets is a topic in the field of combinatorics, Permutations occur, in more or less prominent ways, in almost every area of mathematics. For similar reasons permutations arise in the study of sorting algorithms in computer science, the number of permutations of n distinct objects is n factorial, usually written as n. which means the product of all positive integers less than or equal to n. In algebra and particularly in group theory, a permutation of a set S is defined as a bijection from S to itself and that is, it is a function from S to S for which every element occurs exactly once as an image value. This is related to the rearrangement of the elements of S in which each element s is replaced by the corresponding f, the collection of such permutations form a group called the symmetric group of S. The key to this structure is the fact that the composition of two permutations results in another rearrangement. Permutations may act on structured objects by rearranging their components, or by certain replacements of symbols, in elementary combinatorics, the k-permutations, or partial permutations, are the ordered arrangements of k distinct elements selected from a set. When k is equal to the size of the set, these are the permutations of the set, fabian Stedman in 1677 described factorials when explaining the number of permutations of bells in change ringing. Starting from two bells, first, two must be admitted to be varied in two ways which he illustrates by showing 12 and 21 and he then explains that with three bells there are three times two figures to be produced out of three which again is illustrated. His explanation involves cast away 3, and 1.2 will remain, cast away 2, and 1.3 will remain, cast away 1, and 2.3 will remain. He then moves on to four bells and repeats the casting away argument showing that there will be four different sets of three, effectively this is an recursive process. He continues with five bells using the casting method and tabulates the resulting 120 combinations. At this point he gives up and remarks, Now the nature of these methods is such, in modern mathematics there are many similar situations in which understanding a problem requires studying certain permutations related to it. There are two equivalent common ways of regarding permutations, sometimes called the active and passive forms, or in older terminology substitutions and permutations, which form is preferable depends on the type of questions being asked in a given discipline. The active way to regard permutations of a set S is to them as the bijections from S to itself. Thus, the permutations are thought of as functions which can be composed with each other, forming groups of permutations
Permutation
–
In the
15 puzzle the goal is to get the squares in ascending order. Initial positions which have an odd number of inversions are impossible to solve.
Permutation
–
In the popular puzzle
Rubik's cube invented in 1974 by
Ernő Rubik, each turn of the puzzle faces creates a permutation of the surface colors.
Permutation
–
Biologist and statistician Ronald Fisher
16.
Perfect power
–
In mathematics, a perfect power is a positive integer that can be expressed as an integer power of another positive integer. More formally, n is a perfect power if there exist natural numbers m >1, in this case, n may be called a perfect kth power. If k =2 or k =3, then n is called a square or perfect cube. Sometimes 1 is also considered a perfect power. The sum of the reciprocals of the perfect powers p without duplicates is, ∑ p 1 p = ∑ k =2 ∞ μ ≈0.874464368 … where μ is the Möbius function and this is sometimes known as the Goldbach-Euler theorem. Detecting whether or not a natural number n is a perfect power may be accomplished in many different ways. One of the simplest such methods is to all possible values for k across each of the divisors of n. This method can immediately be simplified by considering only prime values of k. This is because if n = m k for a composite k = a p p is prime. Because of this result, the value of k must necessarily be prime. As an example, consider n = 296·360·724, since gcd =12, n is a perfect 12th power. In 2002 Romanian mathematician Preda Mihăilescu proved that the pair of consecutive perfect powers is 23 =8 and 32 =9. Pillais conjecture states that for any positive integer k there are only a finite number of pairs of perfect powers whose difference is k. As an alternate way to perfect powers, the recursive approach has yet to be found useful. It is based on the observation that the difference between ab and b where a > b may not be constant, but if you take the difference of differences, b times. For example,94 =6561, and 104 is 10000, the difference between 84 and 94 is 2465, meaning the difference of differences is 974. A step further and you have 204, one step further, and you have 24, which is equal to 4. One step further and collating this key row from progressively larger exponents yields a similar to Pascals
Perfect power
–
Overview
17.
Nth root
–
A root of degree 2 is called a square root and a root of degree 3, a cube root. Roots of higher degree are referred by using numbers, as in fourth root, twentieth root. For example,2 is a root of 4, since 22 =4. −2 is also a root of 4, since 2 =4. A real number or complex number has n roots of degree n. While the roots of 0 are not distinct, the n nth roots of any real or complex number are all distinct. If n is odd and x is real, one nth root is real and has the sign as x. Finally, if x is not real, then none of its nth roots is real. Roots are usually using the radical symbol or radix or √, with x or √ x denoting the square root, x 3 denoting the cube root, x 4 denoting the fourth root. In the expression x n, n is called the index, is the sign or radix. For example, −8 has three roots, −2,1 + i √3 and 1 − i √3. Out of these,1 + i √3 has the least argument,4 has two square roots,2 and −2, having arguments 0 and π respectively. So 2 is considered the root on account of having the lesser argument. An unresolved root, especially one using the symbol, is often referred to as a surd or a radical. Nth roots can also be defined for complex numbers, and the roots of 1 play an important role in higher mathematics. The origin of the root symbol √ is largely speculative, some sources imply that the symbol was first used by Arab mathematicians. One of those mathematicians was Abū al-Hasan ibn Alī al-Qalasādī, legend has it that it was taken from the Arabic letter ج, which is the first letter in the Arabic word جذر. However, many scholars, including Leonhard Euler, believe it originates from the letter r, the symbol was first seen in print without the vinculum in the year 1525 in Die Coss by Christoff Rudolff, a German mathematician
Nth root
–
Roots of integer numbers from 0 to 10. Line labels = x. x -axis = n. y -axis = n th root of x.
18.
Logarithm
–
In mathematics, the logarithm is the inverse operation to exponentiation. That means the logarithm of a number is the exponent to which another fixed number, in simple cases the logarithm counts factors in multiplication. For example, the base 10 logarithm of 1000 is 3, the logarithm of x to base b, denoted logb, is the unique real number y such that by = x. For example, log2 =6, as 64 =26, the logarithm to base 10 is called the common logarithm and has many applications in science and engineering. The natural logarithm has the e as its base, its use is widespread in mathematics and physics. The binary logarithm uses base 2 and is used in computer science. Logarithms were introduced by John Napier in the early 17th century as a means to simplify calculations and they were rapidly adopted by navigators, scientists, engineers, and others to perform computations more easily, using slide rules and logarithm tables. The present-day notion of logarithms comes from Leonhard Euler, who connected them to the function in the 18th century. Logarithmic scales reduce wide-ranging quantities to tiny scopes, for example, the decibel is a unit quantifying signal power log-ratios and amplitude log-ratios. In chemistry, pH is a measure for the acidity of an aqueous solution. Logarithms are commonplace in scientific formulae, and in measurements of the complexity of algorithms and they describe musical intervals, appear in formulas counting prime numbers, inform some models in psychophysics, and can aid in forensic accounting. In the same way as the logarithm reverses exponentiation, the logarithm is the inverse function of the exponential function applied to complex numbers. The discrete logarithm is another variant, it has uses in public-key cryptography, the idea of logarithms is to reverse the operation of exponentiation, that is, raising a number to a power. For example, the power of 2 is 8, because 8 is the product of three factors of 2,23 =2 ×2 ×2 =8. It follows that the logarithm of 8 with respect to base 2 is 3, the third power of some number b is the product of three factors equal to b. More generally, raising b to the power, where n is a natural number, is done by multiplying n factors equal to b. The n-th power of b is written bn, so that b n = b × b × ⋯ × b ⏟ n factors, exponentiation may be extended to by, where b is a positive number and the exponent y is any real number. For example, b−1 is the reciprocal of b, that is, the logarithm of a positive real number x with respect to base b, a positive real number not equal to 1, is the exponent by which b must be raised to yield x
Logarithm
–
John Napier (1550–1617), the inventor of logarithms
Logarithm
–
The
graph of the logarithm to base 2 crosses the
x axis (horizontal axis) at 1 and passes through the points with
coordinates (2, 1), (4, 2), and (8, 3). For example, log 2 (8) = 3, because 2 3 = 8. The graph gets arbitrarily close to the y axis, but
does not meet or intersect it.
Logarithm
–
The logarithm keys (lo g for base-10 and ln for base- e) on a typical scientific calculator
Logarithm
–
A
nautilus displaying a logarithmic spiral
19.
Base (exponentiation)
–
In exponentiation, the base is the number b in an expression of the form bn. The number n is called the exponent and the expression is known formally as exponentiation of b by n or the exponential of n with base b and it is more commonly expressed as the nth power of b, b to the nth power or b to the power n. For example, the power of 10 is 10,000 because 104 =10 ×10 ×10 ×10 =10,000. The term power strictly refers to the expression, but is sometimes used to refer to the exponent. When the nth power of b equals a number a, or a = bn, for example,10 is a fourth root of 10,000. The inverse function to exponentiation with base b is called the logarithm to base b, for example, log1010,000 =4
Base (exponentiation)
–
Exponentiation of numbers 0-10. Line labels = base. X axis = power. Y axis = result.
20.
19 (number)
–
19 is the natural number following 18 and preceding 20. In a 24-hour clock, the hour is in conventional language called seven or seven oclock. 19 is the 8th prime number, the sequence continues 23,29,31,37. 19 is the seventh Mersenne prime exponent,19 is the fifth happy number and the third happy prime. 19 is the sum of two odd discrete semiprimes,65 and 77 and is the base of the 19-aliquot tree. 19 is the number of fourth powers needed to sum up to any natural number. It is the value of g.19 is the lowest prime centered triangular number, a centered hexagonal number. The only non-trivial normal magic hexagon contains 19 hexagons,19 is the first number with more than one digit that can be written from base 2 to base 19 using only the digits 0 to 9, the other number is 20. 19 is The TCP/IP port used for chargen, astronomy, Every 19 years, the solar year and the lunar year align in whats known as the metonic cycle. Quran code, There have been claims that patterns of the number 19 are present a number of times in the Quran. The Number of Verse and Sura together in the Quran which announces Jesus son of Maryams birth, in the Bábí and Baháí faiths, a group of 19 is called a Váhid, a Unity. The numerical value of this word in the Abjad numeral system is 19, the Baháí calendar is structured such that a year contains 19 months of 19 days each, as well as a 19-year cycle and a 361-year supercycle. The Báb and his disciples formed a group of 19, There were 19 Apostles of Baháulláh. With a similar name and anti-Vietnam War theme, I Was Only Nineteen by the Australian group Redgum reached number one on the Australian charts in 1983, in 2005 a hip hop version of the song was produced by The Herd. 19 is the name of Adeles 2008 debut album, so named since she was 19 years old at the time, hey Nineteen is a song by American jazz rock band Steely Dan, written by members Walter Becker and Donald Fagen, and released on their 1980 album Gaucho. Nineteen has been used as an alternative to twelve for a division of the octave into equal parts and this idea goes back to Salinas in the sixteenth century, and is interesting in part because it gives a system of meantone tuning, being close to 1/3 comma meantone. Some organs use the 19th harmonic to approximate a minor third and they refer to the ka-tet of 19, Directive Nineteen, many names add up to 19,19 seems to permeate every aspect of Roland and his travelers lives. In addition, the ends up being a powerful key
19 (number)
–
A 19x19
Go board
19 (number)
–
19 is a
centered triangular number
21.
G.I.P. Railway
–
The Great Indian Peninsula Railway was a predecessor of the Central Railway, whose headquarters was at the Boree Bunder in Mumbai. The Great Indian Peninsula Railway was incorporated on August 1,1849 by an act of the British Parliament and it had a share capital of 50,000 pounds. The Court of Directors of the East India Company appointed James John Berkeley as Chief Resident Engineer, kar and R. W. Graham as his assistants. It was Indias ever first railway, the original 21 mile section opening in 1853, on July 1,1925 its management was taken over by the Government. On November 5,1951 it was incorporated into the Central Railway and it was meant for the purpose of increasing the export of cotton, silk, opium, sugar and spices. The management committee consisted of 25 British men, including officials of the East India company and banks in London, most of whom resided in Britain and some who had resided in India. It was originally meant to connect the towns of Poonah, Nassuek, Aurungabad, Ahmednuggur, Sholapoor, Nagpur, Oomrawutty, and Hyderabad. On April 16,1853 at 3,35 pm, the first passenger train of the Great Indian Peninsula Railway left Boree Bunder station in Bombay for Tannah The train took fifty-seven minutes to reach Tannah and it covered a distance of 21 miles. Three locomotives named Sultan, Sindh and Sahib pulled the 14 carriages carrying 400 passengers on board, the railway bridge over Thane creek, first in India, was completed in 1854. The portion of the line from Tannah to Callian was opened on May 1,1854, the construction of this portion was difficult as it involved a two-line viaduct over the estuary and two tunnels. On May 12,1856 the line was extended to Campoolie via Padusdhurree, the Padusdhurree-Khandala section involved the difficult crossing of the Bhore Ghat and it took another five years for completion. During this period, the 21 km gap was covered by palanquin, the Kassarah line was opened on January 1,1861 and the steep Thull ghat section up to Egutpoora was opened on January 1,1865 and thus completed the crossing of the Sahyadri. The south-east main line proceeded over Bhor Ghat to Poonah, Sholapore and Raichore, by 1868, route kilometerage was 888 km and by 1870, route kilometerage was 2,388. Beyond Callian, the north-east main line proceeded over the Thull ghat to Bhosawal near Nusseerabad, from Bhosawal, there was a bifurcation. One passed through great cotton district of Oomravuttee and was extended up to Nagpore, the other was extended up to Jubbulpore to connect with the Allahabad-Jubbulpore branch line of the East Indian Railway which had been opened in June 1867. Hence it became possible to directly from Bombay to Calcutta. The Howrah-Allahabad-Mumbai line was opened on 7 March 1870 and it was part of the inspiration for French writer Jules Vernes book Around the World in Eighty Days
G.I.P. Railway
G.I.P. Railway
–
A passenger train travelling from
Bombay to
Tannah, 1855
22.
Negative base
–
A negative base may be used to construct a non-standard positional numeral system. The need to store the information normally contained by a sign often results in a negative-base number being one digit longer than its positive-base equivalent. Negative numerical bases were first considered by Vittorio Grünwald in his work Giornale di Matematiche di Battaglini, Grünwald gave algorithms for performing addition, subtraction, multiplication, division, root extraction, divisibility tests, and radix conversion. Negative bases were later rediscovered by A. J. Kempner in 1936 and Zdzisław Pawlak. Negabinary was implemented in the early Polish computer BINEG, built 1957–59, based on ideas by Z. Pawlak, implementations since then have been rare. The base −r expansion of a is given by the string dndn-1…d1d0. Negative-base systems may thus be compared to signed-digit representations, such as balanced ternary, some numbers have the same representation in base −r as in base r. For example, the numbers from 100 to 109 have the same representations in decimal and negadecimal, similarly,17 =24 +20 =4 +0 and is represented by 10001 in binary and 10001 in negabinary. The base −r expansion of a number can be found by repeated division by −r, recording the non-negative remainders of 0,1, …, r −1, and concatenating those remainders, starting with the last. Note that if a / b = c, remainder d, then bc + d = a, to arrive at the correct conversion, the value for c must be chosen such that d is non-negative and minimal. This is exemplified in the line of the following example wherein –5 ÷ –3 must be chosen to equal 2 remainder 1 instead of 1 remainder –2. Note that in most programming languages, the result of dividing a number by a negative number is rounded towards 0. In such a case we have a = c + d = c + d − r + r = +, because |d| < r, is the positive remainder. The conversion from integer to some negative base, Visual Basic implementation, The conversion to negabinary allows a remarkable shortcut, the bitwise XOR portion is originally due to Schroeppel. Adding negabinary numbers proceeds bitwise, starting from the least significant bits, while adding two negabinary numbers, every time a carry is generated an extra carry should be propagated to next bit. Unary negation, −x, can be computed as binary subtraction from zero,0 − x, shifting to the left multiplies by −2, shifting to the right divides by −2. To multiply, multiply like normal decimal or binary numbers, but using the rules for adding the carry. It is possible to compare negabinary numbers by slightly adjusting a normal unsigned binary comparator, when comparing the numbers A and B, invert each odd positioned bit of both numbers
Negative base
–
Numeral systems
23.
International Standard Book Number
–
The International Standard Book Number is a unique numeric commercial book identifier. An ISBN is assigned to each edition and variation of a book, for example, an e-book, a paperback and a hardcover edition of the same book would each have a different ISBN. The ISBN is 13 digits long if assigned on or after 1 January 2007, the method of assigning an ISBN is nation-based and varies from country to country, often depending on how large the publishing industry is within a country. The initial ISBN configuration of recognition was generated in 1967 based upon the 9-digit Standard Book Numbering created in 1966, the 10-digit ISBN format was developed by the International Organization for Standardization and was published in 1970 as international standard ISO2108. Occasionally, a book may appear without a printed ISBN if it is printed privately or the author does not follow the usual ISBN procedure, however, this can be rectified later. Another identifier, the International Standard Serial Number, identifies periodical publications such as magazines, the ISBN configuration of recognition was generated in 1967 in the United Kingdom by David Whitaker and in 1968 in the US by Emery Koltay. The 10-digit ISBN format was developed by the International Organization for Standardization and was published in 1970 as international standard ISO2108, the United Kingdom continued to use the 9-digit SBN code until 1974. The ISO on-line facility only refers back to 1978, an SBN may be converted to an ISBN by prefixing the digit 0. For example, the edition of Mr. J. G. Reeder Returns, published by Hodder in 1965, has SBN340013818 -340 indicating the publisher,01381 their serial number. This can be converted to ISBN 0-340-01381-8, the check digit does not need to be re-calculated, since 1 January 2007, ISBNs have contained 13 digits, a format that is compatible with Bookland European Article Number EAN-13s. An ISBN is assigned to each edition and variation of a book, for example, an ebook, a paperback, and a hardcover edition of the same book would each have a different ISBN. The ISBN is 13 digits long if assigned on or after 1 January 2007, a 13-digit ISBN can be separated into its parts, and when this is done it is customary to separate the parts with hyphens or spaces. Separating the parts of a 10-digit ISBN is also done with either hyphens or spaces, figuring out how to correctly separate a given ISBN number is complicated, because most of the parts do not use a fixed number of digits. ISBN issuance is country-specific, in that ISBNs are issued by the ISBN registration agency that is responsible for country or territory regardless of the publication language. Some ISBN registration agencies are based in national libraries or within ministries of culture, in other cases, the ISBN registration service is provided by organisations such as bibliographic data providers that are not government funded. In Canada, ISBNs are issued at no cost with the purpose of encouraging Canadian culture. In the United Kingdom, United States, and some countries, where the service is provided by non-government-funded organisations. Australia, ISBNs are issued by the library services agency Thorpe-Bowker
International Standard Book Number
–
A 13-digit ISBN, 978-3-16-148410-0, as represented by an
EAN-13 bar code
24.
Natural number
–
In mathematics, the natural numbers are those used for counting and ordering. In common language, words used for counting are cardinal numbers, texts that exclude zero from the natural numbers sometimes refer to the natural numbers together with zero as the whole numbers, but in other writings, that term is used instead for the integers. These chains of extensions make the natural numbers canonically embedded in the number systems. Properties of the numbers, such as divisibility and the distribution of prime numbers, are studied in number theory. Problems concerning counting and ordering, such as partitioning and enumerations, are studied in combinatorics, the most primitive method of representing a natural number is to put down a mark for each object. Later, a set of objects could be tested for equality, excess or shortage, by striking out a mark, the first major advance in abstraction was the use of numerals to represent numbers. This allowed systems to be developed for recording large numbers, the ancient Egyptians developed a powerful system of numerals with distinct hieroglyphs for 1,10, and all the powers of 10 up to over 1 million. A stone carving from Karnak, dating from around 1500 BC and now at the Louvre in Paris, depicts 276 as 2 hundreds,7 tens, and 6 ones, and similarly for the number 4,622. A much later advance was the development of the idea that 0 can be considered as a number, with its own numeral. The use of a 0 digit in place-value notation dates back as early as 700 BC by the Babylonians, the Olmec and Maya civilizations used 0 as a separate number as early as the 1st century BC, but this usage did not spread beyond Mesoamerica. The use of a numeral 0 in modern times originated with the Indian mathematician Brahmagupta in 628, the first systematic study of numbers as abstractions is usually credited to the Greek philosophers Pythagoras and Archimedes. Some Greek mathematicians treated the number 1 differently than larger numbers, independent studies also occurred at around the same time in India, China, and Mesoamerica. In 19th century Europe, there was mathematical and philosophical discussion about the nature of the natural numbers. A school of Naturalism stated that the numbers were a direct consequence of the human psyche. Henri Poincaré was one of its advocates, as was Leopold Kronecker who summarized God made the integers, in opposition to the Naturalists, the constructivists saw a need to improve the logical rigor in the foundations of mathematics. In the 1860s, Hermann Grassmann suggested a recursive definition for natural numbers thus stating they were not really natural, later, two classes of such formal definitions were constructed, later, they were shown to be equivalent in most practical applications. The second class of definitions was introduced by Giuseppe Peano and is now called Peano arithmetic and it is based on an axiomatization of the properties of ordinal numbers, each natural number has a successor and every non-zero natural number has a unique predecessor. Peano arithmetic is equiconsistent with several systems of set theory
Natural number
–
The
Ishango bone (on exhibition at the
Royal Belgian Institute of Natural Sciences) is believed to have been used 20,000 years ago for natural number arithmetic.
Natural number
–
Natural numbers can be used for counting (one
apple, two apples, three apples, …)
25.
Exponentiation
–
Exponentiation is a mathematical operation, written as bn, involving two numbers, the base b and the exponent n. The exponent is usually shown as a superscript to the right of the base, Some common exponents have their own names, the exponent 2 is called the square of b or b squared, the exponent 3 is called the cube of b or b cubed. The exponent −1 of b, or 1 / b, is called the reciprocal of b, when n is a positive integer and b is not zero, b−n is naturally defined as 1/bn, preserving the property bn × bm = bn + m. The definition of exponentiation can be extended to any real or complex exponent. Exponentiation by integer exponents can also be defined for a variety of algebraic structures. The term power was used by the Greek mathematician Euclid for the square of a line, archimedes discovered and proved the law of exponents, 10a 10b = 10a+b, necessary to manipulate powers of 10. In the late 16th century, Jost Bürgi used Roman numerals for exponents, early in the 17th century, the first form of our modern exponential notation was introduced by Rene Descartes in his text titled La Géométrie, there, the notation is introduced in Book I. Nicolas Chuquet used a form of notation in the 15th century. The word exponent was coined in 1544 by Michael Stifel, samuel Jeake introduced the term indices in 1696. In the 16th century Robert Recorde used the square, cube, zenzizenzic, sursolid, zenzicube, second sursolid. Biquadrate has been used to refer to the power as well. Some mathematicians used exponents only for greater than two, preferring to represent squares as repeated multiplication. Thus they would write polynomials, for example, as ax + bxx + cx3 + d, another historical synonym, involution, is now rare and should not be confused with its more common meaning. In 1748 Leonhard Euler wrote consider exponentials or powers in which the exponent itself is a variable and it is clear that quantities of this kind are not algebraic functions, since in those the exponents must be constant. With this introduction of transcendental functions, Euler laid the foundation for the introduction of natural logarithm as the inverse function for y = ex. The expression b2 = b ⋅ b is called the square of b because the area of a square with side-length b is b2, the expression b3 = b ⋅ b ⋅ b is called the cube of b because the volume of a cube with side-length b is b3. The exponent indicates how many copies of the base are multiplied together, for example,35 =3 ⋅3 ⋅3 ⋅3 ⋅3 =243. The base 3 appears 5 times in the multiplication, because the exponent is 5
Exponentiation
–
Graphs of y = b x for various bases b: base 10 (green), base e (red), base 2 (blue), and base 1 / 2 (cyan). Each curve passes through the point (0, 1) because any nonzero number raised to the power of 0 is 1. At x = 1, the value of y equals the base because any number raised to the power of 1 is the number itself.
26.
Achilles number
–
An Achilles number is a number that is powerful but not a perfect power. A positive integer n is a number if, for every prime factor p of n. In other words, every prime factor appears at least squared in the factorization, however, not all powerful numbers are Achilles numbers, only those that cannot be represented as mk, where m and k are positive integers greater than 1. Achilles numbers were named by Henry Bottomley after Achilles, a hero of the Trojan war, strong Achilles numbers are Achilles numbers whose Euler totients are also Achilles numbers. A number n = p1a1 p2a2 … pkak is powerful if min ≥2, if in addition gcd =1 the number is an Achilles number. The smallest pair of consecutive Achilles numbers is,5425069447 =73 ×412 ×9725425069448 =23 ×260412108 is a powerful number and its prime factorization is 22 ·33, and thus its prime factors are 2 and 3. Both 22 =4 and 32 =9 are divisors of 108, however,108 cannot be represented as mk, where m and k are positive integers greater than 1, so 108 is an Achilles number. 360 is not an Achilles number because it is not powerful, one of its prime factors is 5 but 360 is not divisible by 52 =25. Finally,784 is not an Achilles number and it is a powerful number, because not only are 2 and 7 its only prime factors, but also 22 =4 and 72 =49 are divisors of it. Nonetheless, it is a power,784 =24 ⋅72 =2 ⋅72 =2 =282. So it is not an Achilles number
Achilles number
–
Overview
27.
Power of two
–
In mathematics, a power of two means a number of the form 2n where n is an integer, i. e. the result of exponentiation with number two as the base and integer n as the exponent. In a context where only integers are considered, n is restricted to values, so we have 1,2. Because two is the base of the numeral system, powers of two are common in computer science. Written in binary, a power of two always has the form 100…000 or 0. 00…001, just like a power of ten in the decimal system, a word, interpreted as an unsigned integer, can represent values from 0 to 2n −1 inclusively. Corresponding signed integer values can be positive, negative and zero, either way, one less than a power of two is often the upper bound of an integer in binary computers. As a consequence, numbers of this show up frequently in computer software. For example, in the original Legend of Zelda the main character was limited to carrying 255 rupees at any time. Powers of two are used to measure computer memory. A byte is now considered eight bits (an octet, resulting in the possibility of 256 values, the prefix kilo, in conjunction with byte, may be, and has traditionally been, used, to mean 1,024. However, in general, the term kilo has been used in the International System of Units to mean 1,000, binary prefixes have been standardized, such as kibi meaning 1,024. Nearly all processor registers have sizes that are powers of two,32 or 64 being most common, powers of two occur in a range of other places as well. For many disk drives, at least one of the size, number of sectors per track. The logical block size is almost always a power of two. Numbers that are not powers of two occur in a number of situations, such as video resolutions, but they are often the sum or product of two or three powers of two, or powers of two minus one. For example,640 =512 +128 =128 ×5, put another way, they have fairly regular bit patterns. A prime number that is one less than a power of two is called a Mersenne prime, for example, the prime number 31 is a Mersenne prime because it is 1 less than 32. Similarly, a number that is one more than a positive power of two is called a Fermat prime—the exponent itself is a power of two. A fraction that has a power of two as its denominator is called a dyadic rational, the numbers that can be represented as sums of consecutive positive integers are called polite numbers, they are exactly the numbers that are not powers of two
Power of two
–
Visualization of powers of two from 1 to 1024 (2 0 to 2 10).
28.
Power of 10
–
In mathematics, a power of 10 is any of the integer powers of the number ten, in other words, ten multiplied by itself a certain number of times. By definition, the one is a power of ten. The first few powers of ten are,1,10,100,1000,10000,100000,1000000,10000000. In decimal notation the nth power of ten is written as 1 followed by n zeroes and it can also be written as 10n or as 1En in E notation. See order of magnitude and orders of magnitude for named powers of ten, there are two conventions for naming positive powers of ten, called the long and short scales. Where a power of ten has different names in the two conventions, the long scale namme is shown in brackets, googolplex, a much larger power of ten, was also introduced in that book. Scientific notation is a way of writing numbers of very large, a number written in scientific notation has a significand multiplied by a power of ten. Sometimes written in the form, m × 10n Or more compactly as, where n is positive, this indicates the number zeros after the number, and where the n is negative, this indicates the number of decimal places before the number. As an example,105 =100,000 10−5 =0.00001 The notation of mEn, known as E notation, is used in programming, spreadsheets and databases. Power of two SI prefix Cosmic View, inspiration for the film Powers of Ten Video Powers of Ten, US Public Broadcasting Service, made by Charles and Ray Eames. Starting at a picnic by the lakeside in Chicago, this film transports the viewer to the edges of the universe. Every ten seconds we view the point from ten times farther out until our own galaxy is visible only as a speck of light among many others. Returning to Earth with breathtaking speed, we move inward - into the hand of the sleeping picnicker - with ten times more magnification every ten seconds and our journey ends inside a proton of a carbon atom within a DNA molecule in a white blood cell
Power of 10
–
Visualisation of powers of 10 from one to 1 trillion.
29.
Square number
–
In mathematics, a square number or perfect square is an integer that is the square of an integer, in other words, it is the product of some integer with itself. For example,9 is a number, since it can be written as 3 × 3. The usual notation for the square of a n is not the product n × n. The name square number comes from the name of the shape, another way of saying that a integer is a square number, is that its square root is again an integer. For example, √9 =3, so 9 is a square number, a positive integer that has no perfect square divisors except 1 is called square-free. For a non-negative integer n, the nth square number is n2, the concept of square can be extended to some other number systems. If rational numbers are included, then a square is the ratio of two integers, and, conversely, the ratio of two square integers is a square, e. g.49 =2. Starting with 1, there are ⌊√m⌋ square numbers up to and including m, the squares smaller than 602 =3600 are, The difference between any perfect square and its predecessor is given by the identity n2 −2 = 2n −1. Equivalently, it is possible to count up square numbers by adding together the last square, the last squares root, and the current root, that is, n2 =2 + + n. The number m is a number if and only if one can compose a square of m equal squares. Hence, a square with side length n has area n2, the expression for the nth square number is n2. This is also equal to the sum of the first n odd numbers as can be seen in the above pictures, the formula follows, n 2 = ∑ k =1 n. So for example,52 =25 =1 +3 +5 +7 +9, there are several recursive methods for computing square numbers. For example, the nth square number can be computed from the square by n2 =2 + + n =2 +. Alternatively, the nth square number can be calculated from the two by doubling the th square, subtracting the th square number, and adding 2. For example, 2 × 52 −42 +2 = 2 × 25 −16 +2 =50 −16 +2 =36 =62, a square number is also the sum of two consecutive triangular numbers. The sum of two square numbers is a centered square number. Every odd square is also an octagonal number
Square number
–
m = 1 2 = 1
30.
Cube (algebra)
–
In arithmetic and algebra, the cube of a number n is its third power, the result of the number multiplied by itself twice, n3 = n × n × n. It is also the number multiplied by its square, n3 = n × n2 and this is also the volume formula for a geometric cube with sides of length n, giving rise to the name. The inverse operation of finding a number whose cube is n is called extracting the cube root of n and it determines the side of the cube of a given volume. It is also n raised to the one-third power, both cube and cube root are odd functions,3 = −. The cube of a number or any other mathematical expression is denoted by a superscript 3, a cube number, or a perfect cube, or sometimes just a cube, is a number which is the cube of an integer. The perfect cubes up to 603 are, Geometrically speaking, an integer m is a perfect cube if and only if one can arrange m solid unit cubes into a larger. For example,27 small cubes can be arranged into one larger one with the appearance of a Rubiks Cube, the difference between the cubes of consecutive integers can be expressed as follows, n3 −3 = 3n +1. There is no minimum perfect cube, since the cube of an integer is negative. For example, −4 × −4 × −4 = −64, unlike perfect squares, perfect cubes do not have a small number of possibilities for the last two digits. Except for cubes divisible by 5, where only 25,75 and 00 can be the last two digits, any pair of digits with the last digit odd can be a perfect cube. With even cubes, there is considerable restriction, for only 00, o2, e4, o6, some cube numbers are also square numbers, for example,64 is a square number and a cube number. This happens if and only if the number is a perfect sixth power, the last digits of each 3rd power are, It is, however, easy to show that most numbers are not perfect cubes because all perfect cubes must have digital root 1,8 or 9. That is their values modulo 9 may be only −1,1 and 0, every positive integer can be written as the sum of nine positive cubes. The equation x3 + y3 = z3 has no solutions in integers. In fact, it has none in Eisenstein integers, both of these statements are also true for the equation x3 + y3 = 3z3. The sum of the first n cubes is the nth triangle number squared,13 +23 + ⋯ + n 3 =2 =2. Proofs Charles Wheatstone gives a simple derivation, by expanding each cube in the sum into a set of consecutive odd numbers. Indeed, he begins by giving the identity n 3 = + + + ⋯ + ⏟ n consecutive odd numbers, kanim provides a purely visual proof, Benjamin & Orrison provide two additional proofs, and Nelsen gives seven geometric proofs
Cube (algebra)
–
y = x 3 for values of 0 ≤ x ≤ 25.
31.
Powerful number
–
A powerful number is a positive integer m such that for every prime number p dividing m, p2 also divides m. Equivalently, a number is the product of a square and a cube, that is, a number m of the form m = a2b3. Powerful numbers are known as squareful, square-full, or 2-full. Paul Erdős and George Szekeres studied such numbers and Solomon W. Golomb named such numbers powerful, in the other direction, suppose that m is powerful, with prime factorization m = ∏ p i α i, where each αi ≥2. Define γi to be three if αi is odd, and zero otherwise, and define βi = αi - γi. Then, all values βi are nonnegative integers, and all values γi are either zero or three, so m = =23 supplies the desired representation of m as a product of a square. Informally, given the prime factorization of m, take b to be the product of the factors of m that have an odd exponent. Because m is powerful, each prime factor with an odd exponent has an exponent that is at least 3, in addition, each prime factor of m/b3 has an even exponent, so m/b3 is a perfect square, so call this a2, then m = a2b3. The representation m = a2b3 calculated in this way has the property that b is squarefree, the sum of the reciprocals of the powerful numbers converges. More generally, the sum of the reciprocals of the sth powers of the numbers is equal to ζ ζ ζ whenever it converges. Let k denote the number of numbers in the interval. Then k is proportional to the root of x. More precisely, c x 1 /2 −3 x 1 /3 ≤ k ≤ c x 1 /2, c = ζ / ζ =2.173 …, the two smallest consecutive powerful numbers are 8 and 9. However, one of the two numbers in a pair formed in this way must be a square. According to Guy, Erdős has asked whether there are many pairs of consecutive powerful numbers such as in which neither number in the pair is a square. Jaroslaw Wroblewski showed that there are indeed infinitely many such pairs by showing that 33c2 +1 = 73d2 has infinitely many solutions and it is a conjecture of Erdős, Mollin, and Walsh that there are no three consecutive powerful numbers. Any odd number is a difference of two squares,2 = k2 + 2k +1, so 2 − k2 = 2k +1. Similarly, any multiple of four is a difference of the squares of two numbers that differ by two,2 − k2 = 4k +4
Powerful number
–
Overview
32.
Recursion
–
Recursion occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic, the most common application of recursion is in mathematics and computer science, where a function being defined is applied within its own definition. While this apparently defines a number of instances, it is often done in such a way that no loop or infinite chain of references can occur. The ancestors of ones ancestors are also ones ancestors, the Fibonacci sequence is a classic example of recursion, Fib =0 as base case 1, Fib =1 as base case 2, For all integers n >1, Fib, = Fib + Fib. Many mathematical axioms are based upon recursive rules, for example, the formal definition of the natural numbers by the Peano axioms can be described as,0 is a natural number, and each natural number has a successor, which is also a natural number. By this base case and recursive rule, one can generate the set of all natural numbers, recursively defined mathematical objects include functions, sets, and especially fractals. There are various more tongue-in-cheek definitions of recursion, see recursive humor, Recursion is the process a procedure goes through when one of the steps of the procedure involves invoking the procedure itself. A procedure that goes through recursion is said to be recursive, to understand recursion, one must recognize the distinction between a procedure and the running of a procedure. A procedure is a set of steps based on a set of rules, the running of a procedure involves actually following the rules and performing the steps. An analogy, a procedure is like a recipe, running a procedure is like actually preparing the meal. Recursion is related to, but not the same as, a reference within the specification of a procedure to the execution of some other procedure. For instance, a recipe might refer to cooking vegetables, which is another procedure that in turn requires heating water, for this reason recursive definitions are very rare in everyday situations. An example could be the procedure to find a way through a maze. Proceed forward until reaching either an exit or a branching point, If the point reached is an exit, terminate. Otherwise try each branch in turn, using the procedure recursively, if every trial fails by reaching only dead ends, return on the path led to this branching point. Whether this actually defines a terminating procedure depends on the nature of the maze, in any case, executing the procedure requires carefully recording all currently explored branching points, and which of their branches have already been exhaustively tried. This can be understood in terms of a definition of a syntactic category. A sentence can have a structure in which what follows the verb is another sentence, Dorothy thinks witches are dangerous, so a sentence can be defined recursively as something with a structure that includes a noun phrase, a verb, and optionally another sentence
Recursion
–
A visual form of recursion known as the
Droste effect. The woman in this image holds an object that contains a smaller image of her holding an identical object, which in turn contains a smaller image of herself holding an identical object, and so forth. Advertisement for Droste
cocoa, c. 1900
Recursion
–
Ouroboros, an ancient symbol depicting a serpent or dragon eating its own tail.
Recursion
–
Recently refreshed
sourdough, bubbling through
fermentation: the
recipe calls for some sourdough left over from the last time the same recipe was made.
Recursion
–
Recursive dolls: the original set of
Matryoshka dolls by
Zvyozdochkin and
Malyutin, 1892
33.
Fibonacci number
–
The Fibonacci sequence is named after Italian mathematician Leonardo of Pisa, known as Fibonacci. His 1202 book Liber Abaci introduced the sequence to Western European mathematics, the sequence described in Liber Abaci began with F1 =1. Fibonacci numbers are related to Lucas numbers L n in that they form a complementary pair of Lucas sequences U n = F n and V n = L n. They are intimately connected with the ratio, for example. Fibonacci numbers appear unexpectedly often in mathematics, so much so that there is a journal dedicated to their study. The Fibonacci sequence appears in Indian mathematics, in connection with Sanskrit prosody, in the Sanskrit tradition of prosody, there was interest in enumerating all patterns of long syllables that are 2 units of duration, and short syllables that are 1 unit of duration. Counting the different patterns of L and S of a given duration results in the Fibonacci numbers, susantha Goonatilake writes that the development of the Fibonacci sequence is attributed in part to Pingala, later being associated with Virahanka, Gopāla, and Hemachandra. He dates Pingala before 450 BC, however, the clearest exposition of the sequence arises in the work of Virahanka, whose own work is lost, but is available in a quotation by Gopala, Variations of two earlier meters. For example, for four, variations of meters of two three being mixed, five happens, in this way, the process should be followed in all mātrā-vṛttas. The sequence is also discussed by Gopala and by the Jain scholar Hemachandra, outside India, the Fibonacci sequence first appears in the book Liber Abaci by Fibonacci. The puzzle that Fibonacci posed was, how many pairs will there be in one year, at the end of the first month, they mate, but there is still only 1 pair. At the end of the month the female produces a new pair. At the end of the month, the original female produces a second pair. At the end of the month, the original female has produced yet another new pair. At the end of the nth month, the number of pairs of rabbits is equal to the number of new pairs plus the number of pairs alive last month and this is the nth Fibonacci number. The name Fibonacci sequence was first used by the 19th-century number theorist Édouard Lucas, the most common such problem is that of counting the number of compositions of 1s and 2s that sum to a given total n, there are Fn+1 ways to do this. For example, if n =5, then Fn+1 = F6 =8 counts the eight compositions, 1+1+1+1+1 = 1+1+1+2 = 1+1+2+1 = 1+2+1+1 = 2+1+1+1 = 2+2+1 = 2+1+2 = 1+2+2, all of which sum to 5. The Fibonacci numbers can be found in different ways among the set of strings, or equivalently
Fibonacci number
–
A page of
Fibonacci 's
Liber Abaci from the
Biblioteca Nazionale di Firenze showing (in box on right) the Fibonacci sequence with the position in the sequence labeled in Latin and Roman numerals and the value in Hindu-Arabic numerals.
Fibonacci number
–
A tiling with squares whose side lengths are successive Fibonacci numbers
34.
Padovan sequence
–
The Padovan sequence is the sequence of integers P defined by the initial values P = P = P =1, and the recurrence relation P = P + P. The first few values of P are 1,1,1,2,2,3,4,5,7,9,12,16,21,28,37,49,65,86,114,151,200,265. The Padovan sequence is named after Richard Padovan who attributed its discovery to Dutch architect Hans van der Laan in his 1994 essay Dom, Hans van der Laan, Modern Primitive. The sequence was described by Ian Stewart in his Scientific American column Mathematical Recreations in June 1996 and he also writes about it in one of his books, Math Hysteria, Fun Games With Mathematics. The above definition is the one given by Ian Stewart and by MathWorld, other sources may start the sequence at a different place, in which case some of the identities in this article must be adjusted with appropriate offsets. This is a property of recurrence relations, the Perrin sequence can be obtained from the Padovan sequence by the following formula, P e r r i n = P + P. e. The Padovan sequence also satisfies the identity P2 − P P = P. The Padovan sequence is related to sums of binomial coefficients by the following identity, P = ∑2 m + n = k = ∑ m = ⌈ k /3 ⌉ ⌊ k /2 ⌋. For example, for k =12, the values for the pair with 2m + n =12 which give non-zero binomial coefficients are, and, and, + + =1 +10 +1 =12 = P. The Padovan sequence numbers can be written in terms of powers of the roots of the equation x 3 − x −1 =0 and this equation has 3 roots, one real root p and two complex conjugate roots q and r. Given these three roots, the Padovan sequence can be expressed by a formula involving p, q and r, P = a p n + b q n + c r n where a, b and c are constants. Since the magnitudes of the complex roots q and r are both less than 1, the powers of these roots approach 0 for large n, and P − a p n tends to zero. For all n ≥0, P is the integer closest to p n −1 s, the ratio of successive terms in the Padovan sequence approaches p, which has a value of approximately 1.324718. This constant bears the same relationship to the Padovan sequence and the Perrin sequence as the ratio does to the Fibonacci sequence. P is the number of ways of writing n +2 as a sum in which each term is either 2 or 3. This can be used to prove identities involving products of the Padovan sequence with geometric terms, such as, ∑ n =0 ∞ P α n = α2 α3 − α −1. A Padovan prime is P that is prime, the first few Padovan primes are 2,3,5,7,37,151,3329,23833. Also, if you count the number of As, Bs and Cs in each string, then for the nth string, you have P As, P Bs, the count of BB pairs, AA pairs and CC pairs are also Padovan numbers
Padovan sequence
–
Spiral of equilateral triangles with side lengths which follow the Padovan sequence.
35.
Pell number
–
In mathematics, the Pell numbers are an infinite sequence of integers, known since ancient times, that comprise the denominators of the closest rational approximations to the square root of 2. This sequence of approximations begins 1/1, 3/2, 7/5, 17/12, and 41/29, so the sequence of Pell numbers begins with 1,2,5,12, and 29. The numerators of the sequence of approximations are half the companion Pell numbers or Pell–Lucas numbers, these numbers form a second infinite sequence that begins with 2,6,14,34. As with Pells equation, the name of the Pell numbers stems from Leonhard Eulers mistaken attribution of the equation, the Pell–Lucas numbers are also named after Édouard Lucas, who studied sequences defined by recurrences of this type, the Pell and companion Pell numbers are Lucas sequences. The Pell numbers are defined by the recurrence relation P n = {0 if n =0,1 if n =1,2 P n −1 + P n −2 otherwise. In words, the sequence of Pell numbers starts with 0 and 1, and then each Pell number is the sum of twice the previous Pell number and the Pell number before that. The first few terms of the sequence are 0,1,2,5,12,29,70,169,408,985,2378,5741,13860, …. The Pell numbers can also be expressed by the closed form formula P n = n − n 22, a third definition is possible, from the matrix formula = n. Pell numbers arise historically and most notably in the rational approximation to √2. If two large integers x and y form a solution to the Pell equation x 2 −2 y 2 = ±1 and that is, the solutions have the form P n −1 + P n P n. The approximation 2 ≈577408 of this type was known to Indian mathematicians in the third or fourth century B. C, the Greek mathematicians of the fifth century B. C. also knew of this sequence of approximations, Plato refers to the numerators as rational diameters. In the 2nd century CE Theon of Smyrna used the term the side and these approximations can be derived from the continued fraction expansion of 2,2 =1 +12 +12 +12 +12 +12 + ⋱. As Knuth describes, the fact that Pell numbers approximate √2 allows them to be used for accurate rational approximations to an octagon with vertex coordinates. All vertices are equally distant from the origin, and form uniform angles around the origin. Alternatively, the points, and form approximate octagons in which the vertices are equally distant from the origin. A Pell prime is a Pell number that is prime, the first few Pell primes are 2,5,29,5741, …. The indices of these primes within the sequence of all Pell numbers are 2,3,5,11,13,29,41,53,59,89,97,101,167,181,191, … These indices are all themselves prime. As with the Fibonacci numbers, a Pell number Pn can only be prime if n itself is prime, the only Pell numbers that are squares, cubes, or any higher power of an integer are 0,1, and 169 =132. However, despite having so few squares or other powers, Pell numbers have a connection to square triangular numbers
Pell number
–
Rational approximations to regular
octagons, with coordinates derived from the Pell numbers.
36.
Polite number
–
In number theory, a polite number is a positive integer that can be written as the sum of two or more consecutive positive integers. Polite numbers have also called staircase numbers because the Young diagrams representing graphically the partitions of a polite number into consecutive integers resemble staircases. If all numbers in the sum are strictly greater than one, the impolite numbers are exactly the powers of two. It follows from the Lambek–Moser theorem that the nth polite number is ƒ, the politeness of a positive number is defined as the number of ways it can be expressed as the sum of consecutive integers. For every x, the politeness of x equals the number of odd divisors of x that are greater than one. The politeness of the numbers 1,2,3. is 0,0,1,0,1,1,1,0,2,1,1,1,1,1,3,0,1,2,1,1,3. For instance 90 has politeness 5 because 90 =2 ×32 ×51, the powers of 3 and 5 are respectively 2 and 1, to see the connection between odd divisors and polite representations, suppose a number x has the odd divisor y >1. Then y consecutive integers centered on x/y have x as their sum, some of the terms in this sum may be zero or negative. However, if a term is zero it can be omitted and any negative terms may be used to cancel positive ones, for instance, the polite number x =14 has a single nontrivial odd divisor,7. It is therefore the sum of 7 consecutive numbers centered at 14/7 =2,14 = + + +2 + + +. The first term, −1, cancels a later +1, conversely, every polite representation of x can be formed from this construction. After this extension, again, x/y is the middle term, more generally, the same idea gives a two-to-one correspondence between, on the one hand, representations as a sum of consecutive integers and on the other hand odd divisors. If a polite representation starts with 1, the number so represented is a triangular number T n = n 2 =1 +2 + ⋯ + n. Otherwise, it is the difference of two numbers, i + + + ⋯ + j = T j − T i −1. In the latter case, it is called a trapezoidal number and that is, a trapezoidal number is a polite number that has a polite representation in which all terms are strictly greater than one. Thus, polite non-trapezoidal numbers must have the form of a power of two multiplied by a prime number, for instance, the perfect number 28 =23 −1 and the number 136 =24 −1 are both polite triangular numbers that are not trapezoidal. It is believed there are finitely many Fermat primes, but infinitely many Mersenne primes. Polite Numbers, NRICH, University of Cambridge, December 2002 An Introduction to Runsums, is there any pattern to the set of trapezoidal numbers
Polite number
–
A
Young diagram representing visually the polite expansion 15 = 4 + 5 + 6
37.
Practical number
–
In number theory, a practical number or panarithmic number is a positive integer n such that all smaller positive integers can be represented as sums of distinct divisors of n. Practical numbers were used by Fibonacci in his Liber Abaci in connection with the problem of representing rational numbers as Egyptian fractions, Fibonacci does not formally define practical numbers, but he gives a table of Egyptian fraction expansions for fractions with practical denominators. The name practical number is due to Srinivasan and he noted that the subdivision of money, weights and measures involved numbers like 4,12,16,20 and 28 which are usually supposed to be so inconvenient as to deserve replacement by powers of 10. He rediscovered the number theoretical property of such numbers and was the first to attempt a classification of numbers that was completed by Stewart. This characterization makes it possible to determine whether a number is practical by examining its prime factorization, every even perfect number and every power of two is also a practical number. Practical numbers have also shown to be analogous with prime numbers in many of their properties. If the ordered set of all divisors of the number n is d 1, d 2. D j with d 1 =1 and d j = n, in other words the ordered sequence of all divisors d 1 < d 2 <. < d j of a number has to be a complete sub-sequence. This partial characterization was extended and completed by Stewart and Sierpiński who showed that it is straightforward to determine whether a number is practical from its prime factorization, a positive integer greater than one with prime factorization n = p 1 α1. P k α k is if and only if each of its prime factors p i is small enough for p i −1 to have a representation as a sum of smaller divisors. The condition stated above is necessary and sufficient for a number to be practical, in the other direction, the condition is sufficient, as can be shown by induction. Since q ≤ σ and n / p k α k can be shown by induction to be practical, we can find a representation of q as a sum of divisors of n / p k α k. The divisors representing r, together with p k α k times each of the divisors representing q, the only odd practical number is 1, because if n >2 is an odd number, then 2 cannot be expressed as the sum of distinct divisors of n. More strongly, Srinivasan observes that other than 1 and 2, the product of two practical numbers is also a practical number. More strongly the least common multiple of any two numbers is also a practical number. Equivalently, the set of all numbers is closed under multiplication. From the above characterization by Stewart and Sierpiński it can be seen that if n is a practical number, in the set of all practical numbers there is a primitive set of practical numbers
Practical number
–
Overview
38.
Primary pseudoperfect number
–
The eight known primary pseudoperfect numbers are 2,6,42,1806,47058,2214502422,52495396602,8490421583559688410706771261086. The first four of these numbers are one less than the numbers in Sylvesters sequence. It is unknown whether there are many primary pseudoperfect numbers. The prime factors of primary pseudoperfect numbers sometimes may provide solutions to Známs problem, for instance, the prime factors of the primary pseudoperfect number 47058 form the solution set to Známs problem. Anne observes that there is one solution set of this type that has k primes in it, for each k ≤8. If a primary pseudoperfect number N is one less than a prime number, for instance,47058 is primary pseudoperfect, and 47059 is prime, so 47058 ×47059 =2214502422 is also primary pseudoperfect. Primary pseudoperfect numbers were first investigated and named by Butske, Jaje and those with 2 ≤ r ≤8, when reduced modulo 288, form the arithmetic progression 6,42,78,114,150,186,222, as was observed by Sondow and MacMillan. Giuga number Anne, Premchand, Egyptian fractions and the problem, The College Mathematics Journal, Mathematical Association of America,29, 296–300, doi,10. 2307/2687685. Butske, William, Jaje, Lynda M. Mayernik, Daniel R, on the equation ∑ p | N1 p +1 N =1, pseudoperfect numbers, and perfectly weighted graphs, Mathematics of Computation,69, 407–420, doi,10. 1090/S0025-5718-99-01088-1. Weisstein, Eric W. Primary Pseudoperfect Number
Primary pseudoperfect number
–
Graphical demonstration that 1 = 1/2 + 1/3 + 1/11 + 1/23 + 1/31 + 1/(2×3×11×23×31). Therefore the product, 47058, is primary pseudoperfect.
39.
Code
–
An early example is the invention of language which enabled a person, through speech, to communicate what he or she saw, heard, felt, or thought to others. But speech limits the range of communication to the distance a voice can carry, decoding is the reverse process, converting code symbols back into a form that the recipient of that understands time. One reason for coding is to communication in places where ordinary plain language. For example, semaphore, where the configuration of flags held by a signaller or the arms of a semaphore tower encodes parts of the message, another person standing a great distance away can interpret the flags and reproduce the words sent. An extension of the code for representing sequences of symbols over the alphabet is obtained by concatenating the encoded strings. Before giving a precise definition, this is a brief example. The mapping C = is a code, whose alphabet is the set. Using the extension of the code, the encoded string 0011001011 can be grouped into codewords as 0 011 0 01 011, and these in turn can be decoded to the sequence of source symbols acabc. Using terms from formal language theory, the mathematical definition of this concept is as follows. In this section, we consider codes which encode each character by a code word from some dictionary. Variable-length codes are useful when clear text characters have different probabilities. A prefix code is a code with the property, there is no valid code word in the system that is a prefix of any other valid code word in the set. Huffman coding is the most known algorithm for deriving prefix codes, prefix codes are widely referred to as Huffman codes even when the code was not produced by a Huffman algorithm. Other examples of prefix codes are country calling codes, the country and publisher parts of ISBNs, Krafts inequality characterizes the sets of codeword lengths that are possible in a prefix code. Virtually any uniquely decodable code, not necessary a prefix one. Codes may also be used to represent data in a way more resistant to errors in transmission or storage, such a code is called an error-correcting code, and works by including carefully crafted redundancy with the stored data. Examples include Hamming codes, Reed–Solomon, Reed–Muller, Walsh–Hadamard, Bose–Chaudhuri–Hochquenghem, Turbo, Golay, Goppa, low-density parity-check codes, error detecting codes can be optimised to detect burst errors, or random errors. A cable code replaces words with words, allowing the same information to be sent with fewer characters, more quickly
Code
–
Morse code, a famous type of code
40.
Two-dimensional space
–
In physics and mathematics, two-dimensional space is a geometric model of the planar projection of the physical universe. The two dimensions are commonly called length and width, both directions lie in the same plane. A sequence of n numbers can be understood as a location in n-dimensional space. When n =2, the set of all locations is called two-dimensional space or bi-dimensional space. Each reference line is called an axis or just axis of the system. The coordinates can also be defined as the positions of the projections of the point onto the two axes, expressed as signed distances from the origin. The idea of system was developed in 1637 in writings by Descartes and independently by Pierre de Fermat. Both authors used a single axis in their treatments and have a length measured in reference to this axis. The concept of using a pair of axes was introduced later, after Descartes La Géométrie was translated into Latin in 1649 by Frans van Schooten and these commentators introduced several concepts while trying to clarify the ideas contained in Descartes work. Later, the plane was thought of as a field, where any two points could be multiplied and, except for 0, divided and this was known as the complex plane. The complex plane is called the Argand plane because it is used in Argand diagrams. These are named after Jean-Robert Argand, although they were first described by Norwegian-Danish land surveyor, Argand diagrams are frequently used to plot the positions of the poles and zeroes of a function in the complex plane. In mathematics, analytic geometry describes every point in space by means of two coordinates. Two perpendicular coordinate axes are given which cross each other at the origin and they are usually labeled x and y. Another widely used system is the polar coordinate system, which specifies a point in terms of its distance from the origin. In two dimensions, there are infinitely many polytopes, the polygons, the first few regular ones are shown below, The Schläfli symbol represents a regular p-gon. The regular henagon and regular digon can be considered degenerate regular polygons and they can exist nondegenerately in non-Euclidean spaces like on a 2-sphere or a 2-torus. There exist infinitely many non-convex regular polytopes in two dimensions, whose Schläfli symbols consist of rational numbers and they are called star polygons and share the same vertex arrangements of the convex regular polygons
Two-dimensional space
–
Bi-dimensional
Cartesian coordinate system
41.
Centered triangular number
–
A centered triangular number is a centered figurate number that represents a triangle with a dot in the center and all other dots surrounding the center in successive triangular layers. The centered triangular number for n is given by the formula 3 n 2 +3 n +22, each centered triangular number from 10 onwards is the sum of three consecutive regular triangular numbers. Also each centered triangular number has a remainder of 1 when divided by three and the quotient is the regular triangular number. The sum of the first n centered triangular numbers is the constant for an n by n normal magic square for n >2. A centered triangular prime is a triangular number that is prime. The first few centered triangular primes are 19,31,109,199,409, lancelot Hogben, Mathematics for the Million. Republished by W. W. Norton & Company, ISBN 978-0-393-31071-9 Weisstein, Eric W. Centered Triangular Number
Centered triangular number
–
This article has an unclear citation style. The references used may be made clearer with a different or consistent style of
citation,
footnoting, or
external linking. (June 2014)
42.
Centered hexagonal number
–
The nth centered hexagonal number is given by the formula n 3 −3 =3 n +1. Expressing the formula as 1 +6 shows that the centered hexagonal number for n is 1 more than 6 times the th triangular number. The first few centered hexagonal numbers are,1,7,19,37,61,91,127,169,217,271,331,397,469,547,631,721,817,919. In base 10 one can notice that the hexagonal numbers rightmost digits follow the pattern 1–7–9–7–1, the sum of the first n centered hexagonal numbers is n3. That is, centered hexagonal pyramidal numbers and cubes are the same numbers, viewed from the opposite perspective, centered hexagonal numbers are differences of two consecutive cubes, so that the centered hexagonal numbers are the gnomon of the cubes. In particular, prime centered hexagonal numbers are cuban primes, the difference between 2 and the nth centered hexagonal number is a number of the form 3n2 + 3n −1, while the difference between 2 and the nth centered hexagonal number is a pronic number. Hexagonal number Magic hexagon Star number
Centered hexagonal number
43.
Centered octagonal number
–
A centered octagonal number is a centered figurate number that represents an octagon with a dot in the center and all other dots surrounding the center dot in successive octagonal layers. The centered octagonal numbers are the same as the odd square numbers, thus, the nth centered octagonal number is given by the formula 2 =4 n 2 −4 n +1. The first few centered octagonal numbers are 1,9,25,49,81,121,169,225,289,361,441,529,625,729,841,961,1089. Calculating Ramanujans tau function on an octagonal number yields an odd number
Centered octagonal number
–
See also [edit]
44.
Centered nonagonal number
–
A centered nonagonal number is a centered figurate number that represents a nonagon with a dot in the center and all other dots surrounding the center dot in successive nonagonal layers. The centered nonagonal number for n is given by the formula N c =2. Thus, the first few centered nonagonal numbers are 1,10,28,55,91,136,190,253,325,406,496,595,703,820,946, the list above includes the perfect numbers 28 and 496. All even perfect numbers are numbers whose index is an odd Mersenne prime. Since every Mersenne prime greater than 3 is congruent to 1 modulo 3, in 1850, Sir Frederick Pollock conjectured that every natural number is the sum of at most eleven centered nonagonal numbers, which has been neither proven nor disproven
Centered nonagonal number
–
See also [edit]
45.
Star number
–
A star number is a centered figurate number that represents a centered hexagram, such as the one that Chinese checkers is played on. The nth star number is given by the formula Sn = 6n +1, the digital root of a star number is always 1 or 4, and progresses in the sequence 1,4,1. The last two digits of a number in base 10 are always 01,13,21,33,37,41,53,61,73,81. Unique among the numbers is 35113, since its prime factors are also consecutive star numbers. Infinitely many star numbers are triangular numbers, the first four being S1 =1 = T1, S7 =253 = T22, S91 =49141 = T313. Infinitely many star numbers are also numbers, the first four being S1 =12, S5 =121 =112, S45 =11881 =1092. A star prime is a number that is prime. The first few star primes are 13,37,73,181,337,433,541,661,937, the term star number or stellate number is occasionally used to refer to octagonal numbers
Star number
–
Chinese checkers board has 121 holes.
46.
Triangular number
–
A triangular number or triangle number counts the objects that can form an equilateral triangle, as in the diagram on the right. The nth triangular number is the number of dots composing a triangle with n dots on a side and it represents the number of distinct pairs that can be selected from n +1 objects, and it is read aloud as n plus one choose two. Carl Friedrich Gauss is said to have found this relationship in his early youth, however, regardless of the truth of this story, Gauss was not the first to discover this formula, and some find it likely that its origin goes back to the Pythagoreans 5th century BC. The two formulae were described by the Irish monk Dicuil in about 816 in his Computus, the triangular number Tn solves the handshake problem of counting the number of handshakes if each person in a room with n +1 people shakes hands once with each person. In other words, the solution to the problem of n people is Tn−1. The function T is the analog of the factorial function. In the limit, the ratio between the two numbers, dots and line segments is lim n → ∞ T n L n =13, Triangular numbers have a wide variety of relations to other figurate numbers. Most simply, the sum of two triangular numbers is a square number, with the sum being the square of the difference between the two. Algebraically, T n + T n −1 = + = + = n 2 =2, alternatively, the same fact can be demonstrated graphically, There are infinitely many triangular numbers that are also square numbers, e. g.1,36,1225. Some of them can be generated by a recursive formula. All square triangular numbers are found from the recursion S n =34 S n −1 − S n −2 +2 with S0 =0 and S1 =1. Also, the square of the nth triangular number is the same as the sum of the cubes of the integers 1 to n and this can also be expressed as ∑ k =1 n k 3 =2. The sum of the all triangular numbers up to the nth triangular number is the nth tetrahedral number, more generally, the difference between the nth m-gonal number and the nth -gonal number is the th triangular number. For example, the sixth heptagonal number minus the sixth hexagonal number equals the triangular number,15. Every other triangular number is a hexagonal number, knowing the triangular numbers, one can reckon any centered polygonal number, the nth centered k-gonal number is obtained by the formula C k n = k T n −1 +1 where T is a triangular number. The positive difference of two numbers is a trapezoidal number. Triangular numbers correspond to the case of Faulhabers formula. Alternating triangular numbers are also hexagonal numbers, every even perfect number is triangular, given by the formula M p 2 p −1 = M p 2 = T M p where Mp is a Mersenne prime
Triangular number
–
The first six triangular numbers