A sequence of non-negative integers a1, a2, a3,... is called exactly realizable if there is a map T : X® X on a set X with the property that T has exactly an points of period n. Define a transformation on sequences
by
| ORBIT |
It is easy to show that a sequence is exactly realizable if and only if its image under ORBIT is also a sequence of non-negative integers (see Puri's thesis [1] for the details). The table below records those sequence pairs of the form (Per,Orb) from the Encyclopedia of Integer Sequences. If you come across any sequences that are exactly realizable, please let me know. All the sequences are expected to have realizing maps - the inclusion of a map means that we know of a map that is natural in some sense (for example, has a finite description or is algebraic). Direct proofs of the congruence are cited in some brief fashion - a question mark indicates that we do not know a proof and seek one, e means it is easy, and a combinatorial counting problem suggests why the number of orbits is a non-negative integer. If there is a natural realizing map, then that fact in itself is usually the best proof of the congruence. Sequences marked with a question mark in the first column are not known to be exactly realizable at all: they just seem to satisfy the congruence for the first twenty or so terms. A star indicates that the initial term of the sequence is shifted by one. Of course any non-negative integer sequence at all can appear in the second column. Other questions about the range of ORBIT are addressed in [4]. Some systematic searches have been made - in particular all exactly realizable sequences from the paper [2] are included in the table.
| Sequence of periodic points | Number of orbits [number of points of least period] | Realizing map T | Direct proof of congruence if known |
| A00004 | A00004 [A00004] | irrational circle rotation | e |
| A00012 | A00007 [A00007] | map on a singleton | e |
| 1, 3, 7, 23, 71, 261, 925, 3455, 12877, 48693,... | A000108 [A000984] | - | e |
| A000079* | A001037 | full 2-shift | degree n irreducible polynomials over F_2; n-bead 2-colour necklaces without overturning of primitive period n; see [1] |
| A000203 | A00012 [A00027] | - | e |
| A000204 | A006206 | golden mean shift; see [3]) | aperiodic binary necklaces with no subsequence 00 |
| A000225* | A059966 | circle doubling map | Lie analogue to the partition numbers |
| A000244* | A027376* [A054718*] | full 3-shift | ternary irreducible polynomials of degree n |
| A000302* | A027377* [A054719*] | full 4-shift | irreducible polynomials of degree n over F_4 |
| A000351* | A001692* [A054720*] | full 5-shift | irreducible polynomials of degree n over F_5 |
| A000364*? | A060164 | - | - |
| A000400* | A032164* [A054721*] | full 6-shift | aperiodic necklaces of n beads of 6 colours |
| A000420* | A001693* | full 7-shift | degree n irreducible polynomials over F_7 |
| A000593 | A000035* | - | e |
| A000670* | A060223 | - | e |
| A000984* | A060165 [A007727*] | - | combinatorial |
| A001001 | A000203 | - | e |
| A001018* | A027380* | full 8-shift | irreducible polynomials of degree n over F_8 |
| A001019* | A027381* | full 9-shift | irreducible polynomials of degree n over F_9 |
| A001020* | A032166 | full 11-shift | aperiodic necklaces of n beads of 11 colours |
| A001021* | A032167 | full 12-shift | aperiodic necklaces of n beads of 12 colours |
| A001022* | A060216 | full 13-shift | - |
| A001023* | A060217 | full 14-shift | - |
| A001024* | A060218 | full 15-shift | - |
| A001025* | A060219 | full 16-shift | - |
| A001026* | A060220 | full 17-shift | - |
| A001027* | A060221 | full 18-shift | - |
| A001029* | A060222 | full 19-shift | - |
| A001067? | A060309 | - | follows from the Kummer and von Staudt congruences? |
| A001157 | A000027 | - | e |
| A001158 | A000290* | - | e |
| A001350 | A060280 | - | e |
| A001641? | A060166 | - | - |
| A001642? | A060167 | - | - |
| A001643? | A060168 | - | - |
| A001700? | A022553 | - | - |
| A001945 | A060169 | automorphism of the 3-torus | - |
| A002416* | 2,34,1538,262178,167772162,412316861986,... | - | Follows from a general result of Moss |
| A004146* | A032170 | automorphism of the 2-torus | `CHK' transform of 1,2,3,4,... |
| A005809* | A060170 | - | combinatorial |
| A006863 | A060334 | - | follows from the Kummer and von Staudt congruences |
| A006953 | A060171 | compact group automorphism - see [6] | follows from the Kummer and von Staudt congruences |
| A006954** | A060479 | compact group automorphism - see [6] | follows from the Kummer and von Staudt congruences |
| A011557* | A032165* | full 10-shift | aperiodic necklaces of n beads of 10 colours |
| A023890 | A005171 | - | e |
| A027306* | A060172 | - | combinatorial |
| A035316 | A010052* | - | e |
| A047863 | A060224 | - | - |
| A048578 | A060477 | union of two full 2-shifts and a map on a singleton | - |
| A056045 | A060173 | - | combinatorial |
| 0,2,0,6,0,8,0,14,... | A000035 | - | e |
| A059928 | A060478 | automorphism of the 10-torus | e |
| A059990 | A060480 | S-integer map with x = 2, S = {2,3}, k = Q (see [5]) | - |
| A059991 | A060481 | S-integer map with x = t, S = {t+1}, k = F2(t) (see [5]) | - |
| A061684*? | - | - | |
| A061685? | - | - | |
| A061686*? | - | - | |
| A061687*? | - | - | |
| A061688? | - | - | |
| A061693? | - | - | |
| A061694? | - | - |
[2] Peter Cameron, Sequences realized by oligomorphic permutation groups, Journal of Integer Sequences 3, 2000.
[3] Yash Puri and Thomas Ward, A dynamical property unique to the Lucas sequence, Fibonacci Quarterly, to appear.
[4] Yash Puri and Thomas Ward, Arithmetic and growth of periodic orbits, Journal of Integer Sequences 4, 2001.
[5] Vijay Chothi, Graham Everest & Thomas Ward: S-integer dynamical systems: periodic points, Journal für die riene und angewandte Mathematik 489, 1997, 99-132.
[6] Graham Everest, Alf van der Poorten, Yash Puri & Thomas Ward: Integer sequences and periodic points, Journal of Integer Sequences, 5:Article 02.2.3, 2002.