The big omega function (A001222) describes the number of prime divisors of a number counted with multiplicity: 0, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 3, 1, 2, 2, 4, 1, 3, 1, 3, 2, 2, 1, 4, 2, 2, 3, 3, 1, 3, 1, 5, 2, 2, 2, 4, 1, 2, 2, 4, 1, 3, 1, 3, 3, 2, 1, 5, 2, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 4, 1, 2, 3, 6, 2, 3, 1, 3, 2, 3, 1, 5, 1, 2, 3, 3, 2, 3, 1, 5, 4, 2, 1, 4, 2, 2, 2, 4, 1, 4, 2, 3, 2, 2, 2, 6, 1, 3, 3, 4, 1, 3, 1, 4, 3, 2, 1, 5, 1, 3, 2.
The numbers zero and one do not have any prime factors. The prime numbers (A000040) have one factor, the semiprimes (A001358) have two factors, and the k-almost primes have k factors.
The big omega function tells us about the maximum number of fields of a structure of some cardinality. In practice, many structures don't use the prime factorization so they have even fewer fields then they do factors.
The number of multiplicative partitions of a number n with k factors is in the interval from p(k) to B(k) where p is the number of of additive partitions of k and B is the number of equivalence relations of size k
Sunday, March 17, 2013
Saturday, March 16, 2013
Differences between primes
The differences between consecutive prime numbers are 1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 14, 4, 6, 2, 10, 2, 6, 6, 4, 6, 6, 2, 10, 2, 4, 2, 12, 12, 4, 2, 4, 6, 2, 10, 6, 6, 6, 2, 6, 4, 2, 10, 14, 4, 2, 4, 14, 6, 10, 2, 4, 6, 8, 6, 6, 4, 6, 8, 4, 8, 10, 2, 10, 2, 6, 4, 6, 8, 4, 2, 4, 12, 8, 4, 8, 4, 6, 12.
The only prime numbers that have an odd difference are the first two prime numbers two and three. Twin primes have a difference of two, cousin primes have a difference of four, and sexy primes have a difference of six.
Prime triplets have differences of either 2,4 or 4,2. Prime quadruplets have differences of 2,2,4 or 2,4,2 and prime quintuplets have differences of 2,4,2,4 or 4,2,4,2. Finally, prime sextuplets have differences 4,2,4,2,4. The twin primes conjecture states that the number of differences of 2 are infinite which is necessary for there to be an infinite number of these prime k-tuples.
The only prime numbers that have an odd difference are the first two prime numbers two and three. Twin primes have a difference of two, cousin primes have a difference of four, and sexy primes have a difference of six.
Prime triplets have differences of either 2,4 or 4,2. Prime quadruplets have differences of 2,2,4 or 2,4,2 and prime quintuplets have differences of 2,4,2,4 or 4,2,4,2. Finally, prime sextuplets have differences 4,2,4,2,4. The twin primes conjecture states that the number of differences of 2 are infinite which is necessary for there to be an infinite number of these prime k-tuples.
Friday, March 15, 2013
Enumerating labeled binary relations
Labeled binary relations on a set of size $n$ can be enumerated using the following counting sequences:
- All relations: $2^{n^2}$
- Commutative relations: $2^{n^{\underline 2}}$
- Endofunctions: $n^n$
- Permutations: $n!$
- Equivalence relations: $B_n$
- Weak orders: A000670
Wednesday, March 13, 2013
Algebraic combinatorics
A set of transformations on a data structure forms a transformation monoid. Place forms are a special type of transformation monoid. Another important type of transformation monoid is a permutation group. The permutation groups arise in combinatorics as the automorphism groups of graphs and various other discrete data structures such as lists.
The set of transformation monoids can be partially ordered to form a lattice. Transformation monoids that are disjoint with respect to one another and that commute with all the operations contained in each other set are independent of one another. Each transformation monoid of the cartesian product of zero or more independent transformation monoids.
By understanding transformational independence we can begin to develop an understanding of parallelism because independent operations can be run in parallel. We can also version independent objects separately to implement fine grained versioning.
The set of transformation monoids can be partially ordered to form a lattice. Transformation monoids that are disjoint with respect to one another and that commute with all the operations contained in each other set are independent of one another. Each transformation monoid of the cartesian product of zero or more independent transformation monoids.
By understanding transformational independence we can begin to develop an understanding of parallelism because independent operations can be run in parallel. We can also version independent objects separately to implement fine grained versioning.
Sunday, March 10, 2013
Describing structures by transformations
The automorphism group of a data structure transformations of that data structure that do not have any effect on it. The automorphism group of a list is the set of operations that map indexes to other indexes with equal value. We can enumerate all the orbits of this automorphism group on its parent symmetric group in order to enumerate all distinct permutations of the list.
Likewise, all graphs have an automorphism group of permutations that do not effect the underlying graph. Weak orderings have an automorphism group equivalent to that of a list, equivalence relations have an automorphism group that also includes exchanges of equally sized parts, and the automorphism group of an permutation is the set of all operations that commute with it.
Periodic sequences can be described by the effect of the rest operation on the sequence and finitely differentiable functions like sine and cosine can be described by the effect of differentiation on them. In this sense, the transformations on a data structure are important in both discrete and continuous mathematics.
Likewise, all graphs have an automorphism group of permutations that do not effect the underlying graph. Weak orderings have an automorphism group equivalent to that of a list, equivalence relations have an automorphism group that also includes exchanges of equally sized parts, and the automorphism group of an permutation is the set of all operations that commute with it.
Periodic sequences can be described by the effect of the rest operation on the sequence and finitely differentiable functions like sine and cosine can be described by the effect of differentiation on them. In this sense, the transformations on a data structure are important in both discrete and continuous mathematics.
Saturday, March 9, 2013
The well ordering principle
The set of natural numbers $\mathbb{N}$ is well ordered which means that every subset of the natural numbers can be described by a monotone increasing enumeration. Consider for example the set of prime numbers:
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53)
We can convert any prime number back into a natural number $\mathbb{N}$. For example, 547 can be converted to 100. These enumerations are endofunctions $\mathbb{N} \to \mathbb{N}$ that are reversible but not surjective. With finite functions all reversible surjective operations are automorphisms. The square numbers are another enumeration of natural numbers:
(0 1 4 9 16 25 36 49 64 81 100 121 144 169 196 225)
The set of all subsets of $\mathbb{N}$ under set union and set intersection forms a boolean algebra with $\mathbb{N} - S$ as the complement operation. The differences between elements of this enumeration form an integer sequence. Consider the sum of the totient function:
(0 1 2 4 6 10 12 18 22 28 32 42 46 58 64 72)
The additive differences of the sum of totients is the eulers totient function itself. In this sense, these monotone enumerations are related to integer sequences in general. We can generalize integer sequences by describing sequences of rational numbers $\mathbb{N} \to \mathbb{Q}$, however, an important difference is that the set of rational numbers $\mathbb{Q}$ is not well ordered.
Friday, March 8, 2013
Finitely differentiable functions
Functions that have a differentiation iteration type with a finite size are solutions to a simple two element homogeneous LODE with constant coefficients. The solutions to a LODE can be described by a basis which in this case can be ordered by the total ordering of rational number sequences.
The function $x^2+2x+1$ would become [1,2,1,0] for the LODE $y''''=y'''$. If we set the default value of each field in this ordered basis this vector could be reduced to [1,2,1] which is equivalent to description of this function as a polynomial. The function $e^x$ is unaffected by differentiation so it would simply be [1] for $y'=y$.
The hyperbolic trigonometric functions $cosh(x)$ and $sinh(x)$ are involutions under differentiation so they would be represented by [1/2,1/2] and [1/2,-1/2]. The trigonometric functions $sin(x)$ and $cos(x)$ have order four so they would be represented as [0,0,1,0] and [0,0,0,1].
The function $x^2+2x+1$ would become [1,2,1,0] for the LODE $y''''=y'''$. If we set the default value of each field in this ordered basis this vector could be reduced to [1,2,1] which is equivalent to description of this function as a polynomial. The function $e^x$ is unaffected by differentiation so it would simply be [1] for $y'=y$.
The hyperbolic trigonometric functions $cosh(x)$ and $sinh(x)$ are involutions under differentiation so they would be represented by [1/2,1/2] and [1/2,-1/2]. The trigonometric functions $sin(x)$ and $cos(x)$ have order four so they would be represented as [0,0,1,0] and [0,0,0,1].
Subscribe to:
Posts (Atom)