Collatz-type Conjectures

Description of the problem

Assume \(p\>1\) is an integer. For any natural number \(n\in\mathbb{N}\) define two functions \[ f_p(n) = \begin{cases} f_p(n/p) & \text{if } n\text{ mod } p = 0 \\ n & \text{otherwise} \end{cases}\]

and \[ g_p(n) = \begin{cases} 1 & \text{if } n=1\\ f_p(n) & \text{if $n\>1$ and $n$ mod $p = 0$} \\ f_p(np + n + p - (n\text{ mod } p)) & \text{otherwise} \end{cases} \]

So, the question is given the recursive sequence \(a_{n+1} = g_p(a_n)\) with an initial \(a_0\in\mathbb{N}\), is it true that \(a_n\) always stabilizes at 1?

The case \(p=2\) is the famous Collatz Conjecture.

Some experiments

I am going to experiment with the sequence. First, let me define the two functions I defined at the beginning:

(defun f (n p)
   (if (zerop (mod n p))
      (f (/ n p) p)
      n))
F

(defun g (n p)
   (cond ((= n 1) 1)
         ((zerop (mod n p)) (f n p))
         (t (f (+ (* (1+ p) n) (- p (mod n p))) p))))
G

Now, a function which calculates the lengths of the recursive sequences for a given initial value. Here, the function terminates if g hits 1 or the recursive sequence \(a_{k+1} = g(a_k)\) contains a cycle. A cycle is a subsequence of elements \((a_k,a_{k+1}, \ldots,a_{k+m})\) such that \(a_k = a_{k+m}\).

(defun collatz-length (n p &optional (m 1) (tail nil))
   (let ((res (g n p)))
     (if (or (= res 1) (member res tail))
        m
        (collatz-length res p (1+ m) (cons res tail)))))
COLLATZ-LENGTH

Now, let us see what happens for some values:

(defun experiment (p n)
   (loop for i from (1+ p) to (+ n p) collect
       (collatz-length i p)))
EXPERIMENT

(experiment 3 100)
(2 8 2 8 10 1 8 9 3 2 8 9 9 10 2 8 1 8 8 9 11 15 8 1 12 3 8 8 10 10 14 8 3
 10 11 3 2 12 8 9 17 9 13 8 10 9 9 11 10 15 2 11 16 8 8 16 2 12 12 8 19 4 9
 8 15 10 9 14 11 11 10 16 15 15 8 15 16 1 11 11 13 12 18 4 12 17 8 14 13 9
 8 13 11 10 10 10 18 9 15 14)

(experiment 5 100)
(5 14 4 13 4 12 3 3 11 3 2 10 8 8 2 9 7 7 16 1 8 6 6 15 6 60 7 5 5 15 13 14
 59 6 5 4 5 67 12 14 58 5 13 5 4 4 66 11 4 13 57 4 12 4 4 65 3 65 10 4 3 12
 56 3 12 3 11 19 64 3 64 9 11 9 3 11 55 2 72 11 2 10 18 63 9 8 63 8 10 9 8
 8 10 54 2 71 45 71 1 10)

(experiment 1007 100)
(1508 3603 1507 3602 1506 3601 1505 3600 1504 3599 1503 3598 1502 3597 1501
 3596 1500 3595 1499 3594 1498 3593 1497 3592 1496 3591 1495 3590 1494 3589
 1493 3588 1492 3587 1491 3586 1490 3585 1489 3584 1488 3583 1487 3582 1486
 3581 1485 3580 1484 3579 1483 3578 1482 3577 1481 3576 1480 3575 1479 3574
 1478 3573 1477 3572 1476 3571 1475 3570 1474 3569 1473 3568 1472 3567 1471
 3566 1470 3565 1469 3564 1468 3563 1467 3562 1466 3561 1465 3560 1464 3559
 1463 3558 1462 3557 1461 3556 1460 3555 1459 3554)

So, the conjecture is for every \(p\>1\) and for every \(a_0\) initial value, the recursive sequence \(a_{k+1} = g_p(a_k)\) either contains a cycle or stabilizes at 1.