|
| |
|
|
A130769
|
|
Injection of the sequence of positive integers used in recursive calls (including initial call) in the execution of the Collatz (3n+1) function into the positive integers using the standard power-of-primes encoding (`Goedel-coding').
|
|
0
|
| |
|
|
|
OFFSET
|
1,1
|
|
|
REFERENCES
|
J. Shallit and D. Wilson, The "3x+1" Problem and Finite Automata, Bulletin of the EATCS #46 (1992) pp. 182-185.
R. K. Guy, Unsolved Problems in Number Theory, E16.
|
|
|
LINKS
|
|
|
|
FORMULA
|
Let f(n) be the Collatz (3n+1) function. Let F(n) be the sequence of positive integers m s.t. f(m) is called during the execution of f(n). (So F(1) = (1); F(2) = (2, 1); F(3) = (3, 10, 5, 15, 8, 4, 2, 1); and so on.) Assume that F(n) has k terms. Then, each instance of the sequence, G(n), is generated by encoding the sequence F(n) as a positive integer as follows: G(n) = 2^F(n)_0 * 3^F(n)_1 * 5^F(n)_2 * ... * p(k-1)^F(n)_{k-1} where F(n)_i is the i-th member of the sequence F(n) and p(i) is the i-th prime.
|
|
|
EXAMPLE
|
G(3) = 1649253940128607650037732224082865475000
because given F as described above,
F(3) = (3, 10, 5, 16, 8, 4, 2, 1)
and thus
G(3) = 2^3 * 3^10 * 5^5 * 7^16 * 11^8 * 13^4 * 17^2 * 19
= 1649253940128607650037732224082865475000.
|
|
|
PROG
|
LISP (main function to call is f-code with n and a list of primes): ; Generate F sequence for the Collatz (3n+1) function (defun F (n) (cond ((= n 1)) (list n)) ((evenp n) (cons n (F (/ n 2)))) (t (cons n (F (1+ (* 3 n))))))) ; The Goedel-coding function. Takes a list of integers and a list of primes and performs the standard powers-of-primes encoding. (defun goedel-code (l p) (cond ((endp l) 1) (t (* (expt (car p) (car l)) (goedel-code (cdr l) (cdr p)))))) ; Encode intermediate values of Collatz function, using a given list of primes (defun G (n) (goedel-code (F n) *list-of-primes*))
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
Grant Olney Passmore (grant(AT)math.utexas.edu), Jul 13 2007
|
|
|
STATUS
|
approved
|
| |
|
|
