

A125024


Minimal Goedel number of endofunctions on k points, by row and sorted within rows (number of points).


3



1, 2, 6, 12, 18, 30, 60, 90, 150, 540, 1500, 2250, 210, 420, 630, 1050, 1890, 2520, 3150, 3780, 7560, 9450, 15750, 18900, 28350, 75600, 113400, 126000, 141750, 216000, 246960, 5402250, 2310, 4620, 6930, 11550
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

If one writes an endofunction over n points (finite n) and numbers the points 1 through n, then each labeled sagittal graph of an endofunction from (1,2,3,..., z) to (a, b, c, ..., z) with a, b, c, ..., z elements of (1,2,3,..., z), is isomorphic to a Goedel number prime(1)^a * prime(2)^b * ... * prime(z)^z. Then, among all the Goedel numbers for different labeled endofunctions of the same (to isomorphism) unlabeled endofunction, there is a unique minimal Goedel number, which is thus the Goedel number for that unlabeled endofunction. Similarly, there is a minimal Goedel number for all the endofunctions on n points, for any n. Iterating the endofunction yields those x for which f^k(n) = x, allowing us to see the cycle index. The length of the nth row is A001372(n). Each row begins with primorial n# = A002110(n) corresponding to the endofunction (1, 2, 3, ..., n) > (1, 1, 1, ..., 1) which maps every integer other than 1 to 1 and loops 1 to itself; and ends with the Goedel number of the endofunction consisting only of a cycle of length n labeled (1, 2, 3, ..., n1, n) > (n1, n2, ..., n, 1). The sequence includes A074736(n) which corresponds to the identity endofunction on n points.


LINKS

Table of n, a(n) for n=0..35.


FORMULA

a(A125023(n)) = A002110(n).


EXAMPLE

For example, take the endofunction on 4 points which is composed of two 2cycles. We can write this as: (1, 2, 3, 4) > (2, 1, 4, 3) which has the Goedel number 2^2 * 3^1 * 5^4 * 7^3 = 2572500. We can also renumber the points (applying the symmetric group S_n: n^n > n^n) and write it: (1, 2, 3, 4) > (3, 4, 1, 2) which gives us the Goedel number 2^3 * 3*4 * 5^1 * 7^2 = 158760. But the minimal Goedel number for that endofunction comes from:
(1, 2, 3, 4) > (4, 3, 2, 1) which gives us 756000. Hence I can enumerate all the minimal Goedel numbers for the 7 endofunctions on 4 points as: 30, 60, 90, 150, 540, 1500, 2250.
Table begins:
n  row(n) of Goedel numbers
0  1. (formally defining prime(0) = 1)
1  2.
2  6, 12, 18.
3  30, 60, 90, 150, 540, 1500, 2250.
4  210, 420, 630, 1050, 1890, 2520, 3150, 3780, 7560, 9450, 15750, 18900, 28350, 75600, 113400, 126000, 141750, 216000, 246960, 5402250.
5  2310, 4620, 6930, 11550, ...
6  30030, 60060, 90090, 150150, ...
7  510510, 1021020, 1531530, ...
8  9699690, 19399380.


CROSSREFS

Cf. A001372, A002110, A074736 Goedel encoding of the prime factors of n, in increasing order and repeated according to multiplicity, A076954 Product_{i=1..n} prime(i)^i, A125023 Number of mappings (or mapping patterns) from k =< n points to themselves; number of endofunctions on k <= n points.
Sequence in context: A036913 A317089 A117311 * A178480 A053660 A104969
Adjacent sequences: A125021 A125022 A125023 * A125025 A125026 A125027


KEYWORD

easy,nonn,tabf


AUTHOR

Jonathan Vos Post, Nov 15 2006


STATUS

approved



