login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 n-th 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, ..., n-1, n) -> (n-1, n-2, ..., 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 2-cycles. 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 25 09:40 EDT 2021. Contains 347654 sequences. (Running on oeis4.)