Determine if N is zibbable [closed]

The Zib sequence $${Z_N(M)}$$ = $$\{{a_i}\}$$ is a very simple sequence defined on a pair of numbers $$N \in \mathbb{N_{odds}}$$, $$M \in \mathbb{N}$$:

• $${a_0}$$ = $$M$$
• $${a_{i+1}}$$ = $$a_i+N$$ if $$a_i$$ is odd
• $${a_{i+1}}$$ = $$a_i/2$$ if $$a_i$$ is even

The sequence ends when $${a_i}$$ equals 1.

An odd $$N$$ is defined zibbable if the sequence ends for any $$M$$ such that $$M$$ is not divided by $$N$$.

Question: Is it possible to determine if $$N$$ is zibbable?

Example

$$N=11, M=72$$

$$Z_{11}(72)$$ = 72,36,18,9,20,10,5,16,8,4,2,1

• Do you know the answer?
– xnor
Commented Jul 17 at 9:37
• What do you mean "possible to determine"? Unlike the Collatz problem, it's easy to find, for any given N, an upper bound that any loop can never exceed, and so check for cycles in a bounded range. But this is pretty brute force, and there might be an efficient algorithm or direct characterization.
– xnor
Commented Jul 17 at 9:46
• @xnor No, i do not know the answer. I've just observed this morning that the sequence loops for any number pairs (passing through 1 or not) Commented Jul 17 at 9:58
• @xnor For the "possible to determine", i mean "just looking at the number N without computing Z_N for every M". I will edit the question. You can brute force it, but only for some M. Commented Jul 17 at 10:03

Let $$f_N$$ be the following function:

$$f_N(a) = \begin{cases} \frac{a}{2}, & \text{if } a \text{ is even} \\ \\ \frac{a+N}{2}, & \text{if } a \text{ is odd} \end{cases}$$

In the odd case this combines the $$+N$$ step with the inevitable $$/2$$ step that will follow it. So the question is, for which $$N$$ does repeated application of $$f_N$$ make every number reach $$1$$ (except for multiples of $$N$$). We call those $$N$$ zibbable.

First two simple observations:

1. To check if $$N$$ is zibbable, it is sufficient to test all $$M, cause any larger number always gets reduced until it is smaller than $$N$$ (excluding multiples of $$N$$ of course).

2. If $$N$$ is composite, say $$N=ab$$, then it is not zibbable, because the sequence starting at $$M=a$$ contains only multiples of $$a$$ so cannot reach $$1$$.

So the zibbable numbers $$N$$ are always prime. If we think of the numbers modulo $$N$$, then the function $$f_N$$ is simply division by $$2$$ in the field of integers modulo $$N$$.

For $$N$$ to be zibbable, any number $$M must reach $$1$$ if we repeatedly apply $$f_N$$, i.e. if we repeatedly divide by $$2$$ modulo $$N$$. So every number modulo $$N$$ is a power of $$2$$. Turning that around, we can say that the powers of $$2$$ modulo $$N$$ must generate all the integers modulo $$N$$, or that $$2$$ is a primitive root modulo $$N$$.

The zibbable numbers are the primes which have $$2$$ as a primitive root. These are on OEIS as sequence A001122. There does not seem to be a formula for it, though they do have to satisfy $$N\equiv3,5 \pmod 8$$ because $$2$$ cannot be a square (a quadratic residue) mod $$N$$.

Edit: As TimC pointed out in the comments, $$N=1$$ is also zibbable. It is vacuously zibbable because there is no $$M$$ to test (every value is a multiple of $$1$$).

• Minor addition - $1$ is zibbable and non-prime. I believe this answer covers the rest of all zibbable numbers. Commented Jul 17 at 19:47
• @TimC Yes, I forgot that edge case. It is vacuously zibbable because there is no $M$ to test (every value is a multiple of $1$). Commented Jul 18 at 5:00
• Elegant and simple, well done! Commented Jul 18 at 9:31