E G Belaga

M Mignotte

Cyclic Structure of Dynamical Systems Associated with 3x + d Extensions of Collatz Problem

Keywords: . Primitive Cyclic Structure. 4. Primitive 3x + d Cycles. 5. Three Basic Primitive Cycles Conjectures. 6. Shift Number -Member Number Disparate Duality. Chapter III. Cyclic Diophantine Formalism. 7. Collatz Configurations, Numbers, and Coronas. 1 8. Exponential Diophantine Criteria for Memberships and Cycles . Shift Number Conjectures and Claims. 11. Member Number Conjectures and Claims. Chapter V. Calculating Primitive Cycles. 12. The Searching Algorithm. References

We study here, from both theoretical and experimental points of view, the cyclic structures, both general and primitive, of dynamical systems D d generated by iterations of the functions T d acting, for all d ≥ 1 relatively prime to 6, on positive integers :

, if n is odd.

In the case d = 1, the properties of the system D = D 1 are the subject of the well-known 3x + 1 conjecture. For every one of 6667 systems D d , 1 ≤ d ≤ 19999, we calculate its (complete, as we argue) list of primitive cycles. We unite in a single conceptual framework of primitive memberships, and we experimentally confirm three primitive cycles conjectures of Jeff Lagarias. An in-deep analysis of the diophantine formulae for primitive cycles, together with new rich experimental data, suggest several new conjectures, theoretically studied and experimentally confirmed in the present paper. As a part of this program, we prove a new upper bound to the number of primitive cycles of a given oddlength.

Contents.

Chapter I. The 3x + d Extention of Collatz Problem. 1. Preamble : the 3x + 1 Conjecture, or Collatz Problem. 2. The 3x + d Conjecture. 3. More of the 3x + d Dynamics : Recurrence, Collapse, and Attraction.

The present study is an experimental and theoretical sequel to our enquiry [START_REF] Belaga | Embedding the 3x+1 Conjecture in a 3x+d Context[END_REF]] into the cyclic structure of 3x + d extensions of the 3x + 1 conjecture (cf. §1 below), the extensions remarkably simple in form, but very rich and powerful in substance, § §2-4, 7, 8. We describe and study this cyclic structure, § §3, 4, in terms of primitive cycles, § §4, 6, 7, introduced in [Lagarias 1990], the building blocks of the general cyclic structure of 3x + d dynamical systems, § §2, 3, 10.

For 6667 such systems D d , with the shift number d relatively prime to 6, 1 ≤ d ≤ 19999, we have found experimentally on the whole 42765 primitive cycles and have confirmed three "Primitive Cycles Existence" conjectures of Jeff Lagarias, §5, as well as few others theoretically predicted phenomena, §10. The new rich experimental data, Tables 123456, Figures 123456789, delivered by an exteremely effective searching engine, §12, and coupled with an in-depth analysis of the diophantine formulae for primitive cycles, § §7-10, have led to the discovery of new, mostly unexpected and sometimes rather spectacular phenomena, -the subjects of several new conjectures, § §5, 6, 10, 11, which are introduced, theoretically studied, and experimentally confirmed in the present paper.

Our theoretical contibutions include the discovery of (a formal framework for) the disparated duality between shift numbers d and member numbers n of primitive cycles. In the framework of this duality, based on the primitive membership concept, finds its natural place and interpretation of experimentally discovered here irreducible and strongly irreducible memberships, §11.

We have also improved, both in form and substance, our upper bound [START_REF] Belaga | Embedding the 3x+1 Conjecture in a 3x+d Context[END_REF]] to the number of primitive cycles of the given oddlength, §10.

We have attempted to make the presentation of our results as full and accessible to the general mathematical public, as possible. In this regard, the present paper can be viewed as a tutorial-like, both theoretical and computational introduction into dynamical, recursive, and diophantine aspects of the 3x + d conjecture.

1. Preamble : the 3x + 1 Conjecture, or Collatz Problem.

We remind the reader the well-known and still open 3x + 1 conjecture, or Collatz problem [Lagarias 1985]. The reminder is concentrated around, and gives the reader a foretast of, the central topics persued in this study. We also lay down in this introductory section the basic conceptional and notational groundwork of this study. (The numerations of conjectures, tables, and figures are thorough : Conjecture 1, §1, Conjecture 7, §2. Other declarative items, such as definitions, lemmas, etc., bear the number of a corresponding section and are enumerated in the order of their appearence : Note 5.1, Aside 5.2, Notation 5.3, Lemma 5.4.)

Conjecture 1 : The 3x + 1 Conjecture. For any positive integer m, define :

T : N -→ N; T (m) = m 2
, if m is even;

3m+1 2
, if n is odd.

(1 : 1)

Then, for any positive integer n, the T -trajectory τ (n) of iterates of T starting at m, τ (m) = {T 0 (m) = m, T (m), T 2 (m) = T (T (m)), T 3 (m), . . .} (1 : 2) runs ultimately into the cycle

C o = 1 → 2 → 1 .
(1 : 3)

The problem has many mathematical facets [START_REF] Wirsching | [END_REF]]. But first and foremost it represents an intricate interplay between algorithmic (or recursive), dynamic, and diophantine insights. The embedding of Collatz problem into a wider 3x + d context [Lagarias 1990], [START_REF] Belaga | Embedding the 3x+1 Conjecture in a 3x+d Context[END_REF]] both sheds new light on this interplay and reveals new and remarkably deep phenomena.

(I) The 3x + 1 Dynamical System. As a mapping defined on the set N of positive integers, the function T (1:1) generates a dynamic system D with the only known cycle C o (1:3). From the dynamical point of view, the 3x + 1 conjecture might fail for two reasons :

(i) Either there exists a divergent T -trajectory,

lim k→∞ T k (m) = ∞.
Thus, the no-divergent-trajectories conjecture :

Conjecture 2 : (NDTC) 3x+1 T has no divergent trajectories.

(ii) Or the cycle C o is not unique. Hence, first, the finite-number-of-cycles conjecture, discarding the possibility of an infinite number of cycles :

Conjecture 3 : (FCC) 3x+1 T has only a finite number of cycles.

And then its (probably, most difficult to prove) refinement, the one-cycle conjecture :

Conjecture 4 : (UCC) 3x+1 T has one and only one (for short, unique) cycle, C o (1:3).

(II) The 3x + 1 Algorithm. The 3x + 1 conjecture can be naturally interpreted as a halting problem for the algorithm : (1 : 4) Hence, the unsolvability option, either in its strongest (and absolute) form of algorithmical undecidability, or in a weaker (and relative) sense of unprovability in an appropriate axiomatic setting [Belaga 1998] :

Note 1.1 : On Undecidability and an Eventual 3x + 1 Paradox. (1) It is true that the remarkable wealth of vast numerical checks and a host of plausible heuristic arguments [Lagarias 1985], [START_REF] Wirsching | [END_REF]] leave little doubt in the veracity of the 3x + 1 conjecture.

(2) However, Conway's example of a periodically linear function naturally generalizing (1:1) and simulating a universal Turing machine [Conway 1972] demonstrates how extraordinary close are we here to the unsolvability realm. (See also [START_REF] Maslov | [END_REF]], [START_REF] Matijasevič | Simple examples of unsolvable canonical calculi[END_REF]] for similar earlier, albeit less accessible results.)

(3) The sets N cyclic and N ucyclic of integers m ∈ N with, respectively, cyclic and ultimately cyclic trajectories τ (m) are effectively enumerable [START_REF] Enderton | [END_REF]] and [Davis 1977] are good recursion theory and solvability reference sources). This can be shown by the standard universal argument of recursion theory, namely : if R(n, q) is the value of m after the the q-th iteration of the loop while of the algorithm A 3x+1 (we assume R(n, q) = m = 1, if the loop terminates on an earlier step 1 ≤ q < q), then any effective enumeration of the set N 2 of pairs of positive integers will permit us to effectively enumerate all n with at least one case of equality R(n, q ) = R(n, q), 1 ≤ q < q.

(4) Moreover, the diophantine interpretation of the cyclic part of the 3x+1 conjecture (see the subdivision (III) of this section and Chapter III below) gives rise to a much more transparent, pure diophantine enumeration procedures.

(5) However, nothing is known about recursive enumerability of the set N ∞ of integers where divergent trajectories start, and therefore, about the recursive decidability of the no-divergent-trajectories conjecture (Conjecture 2).

(6) It might even happen that, on the one hand, a proof would be available of the recursive undecidability of Conjecture 2, whereas, on the other hand, one could be "absolutely certain" that, "in reality," the set N ∞ is empty : see [Belaga 1998] for the precise sense, implications and a plausible "ways out" of such a paradox.

(III) Exponential Diophantine Machinery. Iterating the arithmetic procedure (1:1), one gets explicit exponential diophantine formulae for iterations T i . These cumbersome formulae are apparently of not much use in studying the no-divergent-trajectories conjecture, Conjecture 2. Not so with the cyclic conjectures, Conjectures 3, 4, with their beautiful arithmetical equivalents, Lemma 1.4 and Conjecture 5. (See more about this arithmetical connection below, § §7-10.)

The following definition is a considerably simplified and trimmed version of the below Definition 7.1. Definition 1.2. For any pair (k, ) ∈ N × N of positive integers, satisying the inequality k • log 2 3 < , we define the corresponding Collatz number B = B k, and its Collatz corona A = A k, , which is a finite set of positive integers, as follows.

(1) Collatz (k, )-number :

B = B k, = 2 -3 k .
(1 : 5)

By definition, a Collatz number is an odd positive integer not divisible by 3.

(2) Collatz (k, )-corona A = A k, of the Collatz number B = B k, :

(a) If k = 1, then

A 1, = 1 .

(1 : 6) (b) If k > 1, then for any aperiodic (k -1)-tuple P = p 1 , . . . , p k-1 of positive integers (for a definition of the term "aperiodic," see Definition 7.1(2)) satisfying the inequality p 1 + . . . + p k-1 < ,

(1 : 7) the following number belongs to A :

A = A(P) = 3 k-1 + 3 k-2 • 2 p 1 + . . . + 3 • 2 p 1 +...+p k-2 + 2 p 1 +...+p k-1 .
(1 : 8)

By definition, members of Collatz corona are odd positive integers not divisible by 3.

Lemma 1.3. (1) Collatz corona A k, is a one-element set iff k = 1 (1:6) (2) Otherwise, Collatz corona A of a Collatz number B is a finite set, #A > 1 of mutually distinct positive integers not equal to B.

(3) Moreover, if > 1 + k • log 2 3, then A extends both below and above B.

See Lemma 7.2 for more general and detailed assertions, with explicitly calculated values of #A, inf A , and sup A .

Here is a diophantine interpretation of the T -cyclicity condition (see Corollary 8.4(2) for a proof) : Lemma 1.4. A T -trajectory τ (m) (1:2) starting at a positive odd integer n is a cycle of the length iff there exists such Collatz number B = B k, (1:5) that for some A ∈ A k, ,

B | A , n = A B .
(1 : 9)

Note that any cycle has at least one odd member, so the oddness condition on n is not restictive.

Thus, the following pure diophantine conjecture implies Conjecture 4 :

Conjecture 5. Excluding the case

B 2,1 = 2 2 -3 1 = 1 , (1 : 10)
no Collatz number divides a number from its Collatz corona.

Note 1.5. (1) According to Lemma 1.4, the Collatz number B 2,1 corresponds to the cycle (1:3), with the values n = A = 1.

(2) A Collatz number B k, , k ≥ 2, equal to 1 would be a divisor of any member of its Collatz corona. According to [Ribenboim 1994], already some mediaeval mathematicians knew that the number (1:10) is the only Collatz number equal to 1. (This is a particular, completely resolved case of still open Catalan's conjecture [Ribenboim 1994]; see also below Conjecture 6.) Conjecture 5 suggests the following diophantine hypothesis (see Conjecture 13, §2, for its d extension) : Conjecture 6. For any pair of nonequal prime numbers r, q, 2 ≤ r < q and any pair (k, ) of positive integers, with the exception of the following two cases,

r = 2, q = 3, k = 2, = 1 and r = 2, q = 3, k = 3, = 2 ,
(1 : 11) there exist either no, or at most a finite number of (k -1)-tuples of positive integers p 1 , . . . , p k-1 , p 1 + . . . + p k-1 < , satisfying the congruence

q k-1 + r p 1 • q k-2 + r p 1 +p 2 • q k-3 + . . . + r p 1 +...+p k-2 • q+r p 1 +...+p k-1 ≡ 0 (mod |r -q k |) .
(1 : 12) Note that if |rq k | = 1, then the divisibility in (1:12) would be assured for any k-tuple p 1 , . . . , p k . This scenario (which generalizes the plot of Note 1.5(2)) is excluded by the above condition (1:11), according to the following special (and also completely resolved [Ribenboim 1994]) case of Catalan's conjecture :

Catalan's Conjecture. The only solutions in positive integers r, q, , k of the equation | rq k |= 1 are listed in (1:11). The below (3x + d) conjectures imply (and our calculations strongly confirm) that any number d is a key for at least one and at most a finite number of Collatz numbers. And, as our calculations show, in many cases "relatively small" d are keys to "very big" Collatz numbers (a phenomenon conjectured in [Lagarias 1990]; see for details §10).

Thus, for d = 3299, k = 1000, = 1992 and some "very big" A ∈ A 1000,1992 (cf. also Example 2.4), B = 2 1922 -3 1000 > 10 577 and B divides 3299 • A (1 : 13) These new, surprizing, and absolutely nontrivial insights into arithmetic of simple combinations of exponents of 2 and 3 represent a unique contribution of Collatz problem and its 3x + d generalization to number theory.

2. The 3x + d Conjecture.

It was with the purpose of better understanding of the interplay of dynamic, algorithmic, and diophantine factors in the 3x + 1 case that its 3x + d generalization, for all d ≥ 1 relatively prime to 6, has been proposed in [Lagarias 1990] and, independently, in [Belaga 1995] and [START_REF] Belaga | Embedding the 3x+1 Conjecture in a 3x+d Context[END_REF] 1 . One can now say with hindsight that this quantum d-increment of the 3x + 1 conjecture turned out to be its most natural and elucidative extension :

(i) dynamically, only the 3x + 1 cycle uniqueness claim, Conjecture 5(UCC) 3x+1 , has to be withdrawn in the general 3x + d context, with two other conjectures, no-divergenttrajectories (Conjectures 6(NDTC) 3x+d and 7(URCC) 3x+d below) and finite-number-ofcycles (Conjecture 8(NDTC) 3x+d ), upholded;

(ii) algorithmically, the respective change boils down to the replacement of the constant 1 in the algorithm (1:4) by an appropriate positive integer, see (2:5) below;

(iii) as it has been already mentioned above, §1(IV), the corresponding 3x + d diophantine interpretation extends the problem of divisibility (1:6) of the number A by B (1:5) to the problem of divisibility of d • A by B.

Define the 3x + d transform, with the shift number d being a positive odd integer not divisible by 3 (or, in other words, d ≥ 1 relatively prime to 6), as follows :

T d : N -→ N ; T d (m) = m 2 , if m is even; 3m+d 2
, if m is odd.

(2 : 1)

Then, for any positive integer n ∈ N, define a T d -trajectory and T d -cycle starting at m, as follows :

           τ d (m) = m = T 0 d (m), m 1 = T d (m), m 2 = T 2 d (m) = T d (T d (m)), . . . τ d (m) is a T d -cycle of the length ⇐⇒        ∃ ≥ 1 , m = T d (m) = m ∀r(1 ≤ r < ) , m r = T r d (m) = m .
(2 : 2)

1 We are grateful to the anonymous referee of [START_REF] Belaga | Embedding the 3x+1 Conjecture in a 3x+d Context[END_REF]], who brought our attention to the important paper [Lagarias 1990].

It is worth to mention here that, in [START_REF] Belaga | Embedding the 3x+1 Conjecture in a 3x+d Context[END_REF]], we also study the case d = -1. It has been dropped here, to avoid too much techincal particalurization of our notations and claims.

The last condition (T r d (m) = m, if r ≡ 0 (mod )) guarantees that a cycle of the length is not a cycle of a smaller length.

(I) The 3x + d Dynamics. We use the shorthand notations D, {ξ, η}, and D d for, respectively, the set of positive odd integers not divisible by 3, its enumeration functions, and its subset of integers relatively prime to d : 5, 7, 11, 13, 17, 19 . . . ;

               D = n ∈ N | gcd(n, 6) = 1 = 1,
D d = n ∈ D | gcd(n, d) = 1 ;      ∀t ∈ N , ξ(t) = 6 • t 2 -(-1) t ∈ D ; ∀n ∈ D , η(n) = n 3 ∈ N ; N ξ -→ D η -→ N ξ -→ D ; ξ • η = id D , η • ξ = id N .
(2 : 3)

For any d ∈ D, the dynamical system D d has a cycle closely resembling C o (1:3) : This loss of the unique cyclic attractor, similar to C o (1:3) in the 3x + 1 case, does not apparently affect the general dynamical pattern. In the 3x + d case, too, heuristic arguments and numerical checks carried in this study lead us to believe that, for all d ∈ D, both no-divergent-trajectories and finite-number-of-cycles conjectures hold : The total number of T d -cycles will be the subject of our formula (4:12) and conjectures, old and new, § §5,6.

C o d = {d → 2d → d} (2 : 4) (cf.
Taken together, the above conjectures imply that any T d -trajectory collapses into a bounded vicinity of 1. We define below, § §3, 10, three numerical characteristics of systems D d implicit in this assumption. One of these characteristics, the recurrence threshold R d , appears in the below 3x + d extension (2:7) of the 3x + 1 halting problem (1:4).

An important dynamical insight into the 3x + d conjecture represents the technique of primitive cycles [Lagarias 1990] and the related conjectures, old and new, § §4-6, 9. It is noteworthy, however, that at least seven of the new conjectures, presented below, cannot be properly formulated and understood in the pure dynamical context : they are inspired by, and substantially rely on the diophantine interpretation and analysis of the conjecture Conjecture 9(FCC) 3x+d , § §7, 8; see also the subsection (III) below.

(II) The 3x + d Conjecture as a Halting Problem. Taken together, the above conjectures are equivalent to the following halting problem :

Conjecture 10 : Algorithmic Version of Conjectures 7-9. For any d ∈ D, there exists such a positive integer R, that the following algorithm halts for all input (positive integer) values of n :

A 3x+d :      m := n while m > R do m := T d (m) endwhile .
(2 : 5) Note that in the special case d = R = 1, the procedure (2:5) becomes the 3x + 1 algorithm (1:4). Note also that the minimal value of R, for a given shift number d, is the recurrence threshold R d mentioned in the subsection (II) above and defined below, §3.

The affirmative version of the no-divergent-trajectories conjecture can be naturally interpreted as the following separate halting problem. (For the proof, see §12, Lemma 12.2.) We do not know a similarly transparent interpretation for the finite-number-ofcycles conjecture.

Conjecture 11 : Algorithmic Version of Conjecture 8. For any d ∈ D, the following algorithm always halts :

A cyclic 3x+d :      m := n := j while m = n do m := T d (m); n := T d (n); n := T d (n); endwhile .
(2 : 6) For a proof that A cyclic 3x+d detects all T d -cycles, see Proposition 12.2. This equivalence intimates the idea of a simple algorithm for checking both Conjectures 7(NDTC) 3x+d and 9(FCC) 3x+d and, in the case they hold, for computing all T d -cycles. Namely, starting with m = 1, and then going on and on, follow the T d -trajectory τ d (m) (2:2), until it runs ultimately into a T d -cycle. Using enhanced versions of this algorithm, §11, we will experimentally confirm (cf. Tables 123456, Figures 123456789, and the searching algorithm, §12) several well-known and new 3x + d related phenomena and conjectures, § §3-6, 8-11.

(III) The Exponential Diophantine Paraphrase of the Cyclic Part of the 3x + d Conjecture. The diophantine formalism turns out to be strictly complementary to the algorithmic one : it becomes effective where the algorithmic approach fails, and vice versa. Namely, as in the 3x + 1 case, explicit arithmetic formulae for T d iterations are apparently of no help in studying the no-divergent-trajectories conjecture, in either of its two forms (Conjectures 7, 8). Not so with the cyclic part of the 3x + d conjecture (Conjecture 9) : Lemma 2.3. [START_REF] Belaga | Embedding the 3x+1 Conjecture in a 3x+d Context[END_REF]] For any d ∈ D, there exists a T d -cycle meeting an odd positive integer n iff, there exists such a Collatz number B = B k, (1:5) that for some

A ∈ A k, , d • A ≡ 0 (mod B) , n = d • A B .
(2 : 7) (A similar result has been proved in [Lagarias 1990].) Cf. these formulae with their 3x + 1 version (1:9), Lemma 1.4. Hence, the following exponential diophantine version of the above finite-number-ofcycles conjecture (cf. §1(IV) and see for details § §7, 8) : This should be expected [Lagarias 1990], if each system D d has at least one primitive T d -cycle. Now, the experimental data show the pervasiveness of this phenomenon on a scale far surpassing the available theoretical expectations; cf. Table5, §9.

Finally, the 3x+d-extention (2:7) of the diophantine version (1:5-9) of Collatz problem suggests the following 3x + d-extension of our Conjecture 6 (1:12) : Conjecture 13. For any pair of nonequal prime numbers r, q, 2 ≤ r < q and any positive integer d relatively prime to both p and q, gcd(d, p • q) = 1, the exist either no, or at most a finite number of k-tuples of positive integers p 1 , . . . , p k , 1 ≤ k < ∞, satisfying the following congruence :

d • q k-1 + r p 1 • q k-2 r p 1 +p 2 • q k-3 + . . . + r p 1 +...+p k-2 • q + r p 1 +...+p k-1 ≡ 0 (mod |r -q k |) .
(2 : 9)

3. More of 3x + d Dynamics : Recurrence, Collapse, and Attraction.

Taken together, Conjecture 7(NDTC) 3x+d and Conjecture 9(FCC) 3x+d are obviously equivalent to each one of the following three conjectures (the second and third conjectures, united in a single, less elaborated and slightly different hypothesis, can be found in [START_REF] Belaga | Embedding the 3x+1 Conjecture in a 3x+d Context[END_REF]] under the name of Termination Set Conjecture) : Cf. also the below 4.7(3) (4:14).

These equivalent re-formulations have at least three advantages. First, they spell explicitly out the existence of a "collapsing" phenomenon observed in all studied until now systems D d , -the possible "key" to understanding of other T d -phenomena.

Second, they define three important characteristics of the cyclic structure of the system D d . Namely, assuming Conjectures 7(NDTC) 3x+d and 9(FCC) 3x+d hold, (i) T d -recurrence threshold R d is the maximal of minimal members of T d -cycles;

(ii) T d -collapse threshold L d is the maximal of maximal members of T d -cycles;

(iii) T d -attractor U d is the union of members of all T d -cycles. These characteristics can be computed from their respective primitive T d -analogues, §4 (4:11-14).

Finally, algorithmic re-formulations of the above conjectures makes manifest in a most transparent way the "halting" nature of 3x + d related problems. In particular, Conjecture 12 is the precise equivalent of the halting problem (2:5), §2.

Chapter II. Primitive Cyclic Structure.

Further progress in studying the fine cyclic structure of systems D d becomes possible thanks to the technique of primitive cycles [Lagarias 1990]. Intuitively, a primitive cycle is a T d -cycle which is not a q-multiple of a T r -cycle, with q • r = d, r < d.

One of the main purposes of the present paper is to theoretically and experimentally explore the primitive cyclic structure of dynamical systems D d . In particular, for 6667 dynamical systems D d , in the interval d ∈ D, d ≤ 19999, we calculate (as we argue, §13, all) their primitive cycles.

The analysis of this experimental data permits us to confirm with different degrees of certainty (which should, and will be made exact below, Note 5.2, §13) the aforementioned no-divergent-trajectories conjecture and, via the conjectures of Jeff Lagarias [Lagarias 1990], the finite-number-of-cycles conjecture, §11. Our dual interpretation of Lagarias conjectures is new, § §5,7. So are the insights which lead inextricably to our shift number and member number conjectures, § §10, 11. All our new conjectures, § §6,8-11, are solidly confirmed by the experimental data, cf. Tables 123456, Figures 123456789, and the searching algorithm, §12.

4. Primitive 3x + d Cycles.

We start with a few trivial technical observations. Notation 4.1. We remind that the shift number d ≥ 1 is relatively prime to 6, d ∈ D (2:3). For any positive integer m ∈ N, define the number odd (m) obtained by factoring out of m the highest possible power of 2; thus odd (m) is odd and m = odd (m) • 2 j , for some j. Hence the notations : m) .

∀m ∈ N , ν 2 (m) = max j ≥ 0 m • 2 -j ∈ N , m = odd (m) • 2 ν 2 (
∀m, r ∈ N ∀d ∈ D , gcd(3, T r d (m)) = 1 . (4 : 2)
Thus, all odd members of the trajectory τ d (m) different from m (and, in the case of a T d -cycle, all its odd members), n, n 1 , . . ., are relatively prime to 6, n, n 1 , . . . ∈ D.

(2). In particular, the minimal member n of a T d -cycle is odd and n ∈ D. And without the loss of generality, we can assume that any T d -traectory starts at an integer relqtively prime to 6. Then, the full sequence of odd members, in the order of their appearance in a T d -trajectory τ d (n) starting at m = n 0 ∈ D (cf. (2:2), (4:1)), is denoted by Odd (n, d), and the full sequence of the corresponding exponents of 2, by Even(n, d) :

∀n, d ∈ D                    (1) τ d (n) = m 0 = n, m 1 , m 2 , . . . ; (2) Even(n, d) = e 1 , e 2 , . . . ⊂ N , ∀j ≥ 1 , e j = ν 2 (3n j-1 + d) ; (3) Odd (n, d) = n 0 = n, n 1 , n 2 , . . . ⊂ D , ∀j ≥ 1 , n j = odd (3n j-1 + d) = m r j , r j = 1≤i≤j e i .
(4 : 3)

(3) In the case of a T d -cycle C of the length (2:2), the periodic sequence (4:3(3)) is called the oddcycle associated with C and denoted by Odd (C), with the period k < called the oddlength of the cycle, with the minimal member n = n 0 ∈ D listed as the first member of the cycle C (cf. (4:4(2) below), and with the respective list Even(C) of exponents defined as above (4:3(2)). The sets of members and of odd members of a cycle are denoted by Set(C) and Oddset(C)), respectively :

                               (1) C = m 0 , . . . , m -1 ; m 0 = min 0≤j≤ -1 {m j } ; T d (m -1 ) = m 0 , T d (m i ) = m i+1 = m 0 , 0 ≤ i ≤ -2 ; (2) Odd (C) = n 0 , . . . , n k-1 ; n 0 = m 0 = min{m 0 , . . . , m -1 } = n j , 1 ≤ j ≤ k -1 , n j = odd (3n j-1 + d), 1 ≤ j ≤ k -1 ; n 0 = odd (3n -1 + d) ; (3) Even(C) = e 1 , . . . , e k ; e j = ν 2 (3n j-1 + d), 1 ≤ j ≤ k; e 1 + . . . + e k = ; (4) Set(C) = m i | 0 ≤ i ≤ -1 ; Oddset(C)) = n j | 0 ≤ j ≤ k -1 .
(4 : 4) Thus, e. g., a T 2 r -3 -cycle C o 2 r -3 , r > 1, of the length r + 1, starting at (the odd number) 1, has no other odd members (4:4), oddlength(C o 2 r -3 )1 :

C o 2 r -3 = 1, 2 r-1 , 2 r-2 , . . . , 2 ; Odd (C o 2 r -3 ) = 1 ; Even(C o 2 r -3 ) = r .
(4) For any odd q > 1, the q-multiple of a T d -trajectory τ d (m) is identical to the T q•d -trajectory starting at q • m (2:2) :

τ q•d (q • m) = q • τ d (m) = q • m, q • T d (m), q • T 2 d (m), q • T 3 d (m), . . . . (4 : 5) In particular, if C = τ d (m) is a T d -cycle of the length and oddlength k, then q • C = τ q•d (q • m) is a T q•d
-cycle of the same length and oddlength.

(5) And vice versa, if , for some odd q > 1, gcd(d, m) = q ≥ 1, then the

T d -trajectory τ d (m) is the q-multiple of a T d q -trajectory : gcd(d, m) = q > 1 ⇐⇒ τ d (m) = q • τ d q m q .
(4 : 6)

Proof : Straightforward verification.

End of the Proof.

Definition 4.3. (1) A T d -cycle C = τ d (m) is called primitive, if gcd(d, m) = gcd(d, T r d (m) = 1, for all r ≥ 1 . Or, in other words, if for any divisor q > 1 of d, C is not a q-multiple of a T d q -cycle.
(2) For any d ∈ D, let C(d), P(d , and P n) be, respectively, the sets of all T d -cycles, all primitive T d -cycles, and all primitive cycles meeting an integer n (we postpone the detailed definition of sets P n) till §6) :

∀d ∈ D , P(d ⊂ C(d) ; d∈D P(d = P ⊂ C = d∈D C(d) .
(4 : 7)

A priori, all three sets might be finite (in particular, empty) or infinite, with P(d = C(d) for all d > 1 : cf. Example 4.5(2). And so might be their cardinalities : (

∀d ∈ D , (d) = #P(d < ς(d) = #C(d).
) If a cycle C = τ d (m) is not primitive, gcd(d, m) = q > 1, then the cycle 1 q • C = τ d q m q (4:6) is primitive. Example 4.5. (1) The T -cycle C o (1:3) is primitive. 2
(2) According to (2:4), for any

d > 1, d ∈ D, the T d -cycle C o d is a d-multiple of the primitive T -cycle C o (1:3).
(3) Keith Matthews asserts in [Matthews 1999] that, in our terminology, the system D 371 has four cycles, with the minimal members 25, 265, 371, 721 and lengths 222, 4, 2, 29, respectively, or for short, [25(222)] 371 , [265( 4 2)). For any positive integer q ∈ D and any T d -cycle C (4:1) define the T q•d -cycle q • C as the collection of q-multiples of members of C (4:2). Define further

q • P(d = q • C ∀C ∈ P(d ⊂ C(q • d) . (4 : 9)
Then the followingequality hods :

C(d) = d=q•r q,r ∈ D q • P(r) .
(4 : 10)

Proof : Straightforward verification. End of Proof.

Corollary 4.7. ( 1) Let (d) and ς(d) be the total numbers of primitive and, respectively, all T d -cycles (4:8). If for some d ∈ D, the set C(d) is infinite, then so is the set P(r) for at least one divisor r of d (r|d, 1 ≤ r ≤ d) :

∀d ∈ D , ς(d) = ∞ ⇐⇒ ∃ r | d (1 ≤ r ≤ d) , (d) = ∞.
(4 : 11)

(2) Moreover, the equality (4:9) implies the following formula (which, according to (4:11), becomes the trivial identity ∞ = ∞, if the set C(d) would be infinite) :

ς(d) = d=q•r q,r ∈ D (r) = 1 + d=q•r,r≥2 q,r ∈ D (r) .
(4 : 12)

(3) Let respectively, the sets of primitive and general cycles found experimentally in this study, as well as the corresponding Td -characteristics calculated according to the formulae (4:11-14), with P(d everywhere replaced by Pd .

n o (C) = min(m, m 1 , . . . , m -1 ), m o (C) = max(m, m 1 , . . . , m -
               (1) R o d = max n o (C) C ∈ P(d ; (2) R d = max q • R o r d = q • r & q, r ∈ D ; (3) L o d = max m o (C) C ∈ P(d ; (4) L d = max q • L o r d = q • r & q, r ∈ D ; (5) U d = m ∈ C) C ∈ P(d .
(2) This tilde-device will be used throughout the paper, to distinguish between theoretical (or absolute) values of parameters and their experimental estimates.

(3) It is clear that all tilde-parameters represent experimental lower bounds to their respective original counterparts, as, e. g., Rd , Ld , Ũd , ˜ (d), and ςd :

Rd ≤ R d , Ld ≤ L d , Ãd ⊆ A d , ˜ (d) ≤ (d), ς(d) ≤ ς(d).
(4 : 16)

Conjectural Claim 4.9. In the interval d ∈ D, 1 ≤ d ≤ 19999 of values d experimentally studied in the present paper, the inequalities and inclusion of (4:16) are, in fact, equalities.

We justify this claim below, §12, where we will privide the evidence that, in this study, we have actually found all primitive T d -cycles (and, thus, all general T d -cycles, too), for all d from the above interval.

Example 4.10. (1) We have found only two primitive T 1715 -cycles, with the minimal andmaximal members 941, 773, and28,876, 55,876 1)) to be met by such a cycle, for some d ∈ D, gcd(d, n) = 1 ? These are the subjects of three original conjectures of Lagarias [Lagarias 1990].

The two first conjectures of Lagarias are straightforward restrictions to primitive cycles of, respectively, the no-divergent-trajectories and finite-number-of-cycles conjectures, §2. Conversely, the second conjecture implies, according to Corollary 4.7(1,2), (4:12), the finite-number-of-cycles conjecture.

The no-divergent-trajectories conjecture (in its "ultimately-cyclic" form, Conjecture 8, §2), together with Corollary 4.4 (1) (a non-divergent trajectory τ d (m) starting at n ∈ D d (2:3) either is a primitive cycle, or ultimately enters such a cycle) immediately imply the first conjecture of Lagarias : (5 : 1)

The second conjecture of Lagarias is a formal restriction of the finite-number-of-cycles conjecture (Conjecture 9, §2) to primitive cycles. In fact, according to (4:12), Corollary 4.7(1.2), both conjectures are equivalent :

Conjecture 18 : Finiteness of the Set of Primitive T d -cycles. For any d ∈ D, the number (d) (4:8) of primitive T d -cycles is finite :

∀d ∈ D , (d) < ∞ .
(5 : 2)

The third conjecture of Lagarias has no immediately apparent 3x + 1 analogue. We interpret it here and in § §6, 8, as a double conjecture, dual to the first and second conjectures, with the emerging disparate duality between d-and n-related phenomena being an important new and all-pervading intuition behind the present study. Of course, Conjecture 20 tautologically implies Conjecture 19. Still, it is worth to state explicitely both conjectures, and for the following reasons : Note 5.1. (1) The apparently weaker Conjecture 19 might be more amenable to a proof.

(2) On the other hand, as it has been proved in [Lagarias 1990], an integer n ∈ D belonging to a primitive cycle of the oddlength k, belongs to an infinite series of primitive cycles of the same oddlength and with an almost identical diophantine structure (see for details §11, Theorem 11.3(3)). Thus, Conjecture 19 formally implies the apparently stronger Conjecture 20.

(3) However, as our experimental data (which stronly confirm Conjecture 19 and provide a reasonable, in fact, the best possible in the circumstrances, Note 5.2, confirmation of Conjecture 20 : cf. Figure 2 (2) In fact, to fully experimentally confirm, in the chosen range of input parameters, the claims of Conjectures 17, 19 (the existence of at least one primitive cycle with a fixed shift number or member), it is necessary and sufficient to find such a primitive cycle, with d or n from the chosen range : cf. Figures 3,4 and, respectively, 2.

(3) Another matter, however, is to experimentally confirm a conjecture which claims that some set of primitive cycles is not just nonempty (Conjectures 17, 19), but is finite (i. e., not infinite, -Conjecture 18) or even infinite (Conjecture 20). Here the confirmation depends on the quality of available evidence that the search was exhaustive. We postpone this discussion to §12.

We start with some preliminary notations.

Notation 5.3. For any pair of odd integers Q, R ∈ D, define an interval I Q,R ⊂ D, as follows :

Q, R ∈ D =⇒ I Q,R = [Q, R] ∩ D . (5 : 4) By definition, I Q,R = ∅ if Q > R.
Lemma 5.4. According to (2:3), the number ι(Q, R) of integers in the interval I Q,R (5:4) is equal to

ι(Q, R) = #I Q,R = R 3 -Q 3 + 1, if Q ≤ R ; 0 , otherwise .
(5 : 5)

In these notations, the range of our experimental study becomes: (2) Conjecture 18. As it has been mentioned above, Note 5.2, the experimental evidence for this conjecture can be only circumstantial. The experimentally found sets Pd of primitive cycles and their cardinalities ˜ (d) (4:15) cannot be but finite. We will argue below, $12, why the sets and numbers, experimentally found in this study, are not just experimental samples, providing us with the lower bounds (4:16), but, in fact, are the actual sets and numbers of primitive cycles in the given range of shift numbers d. What follows, is a digest of our experimental findings.

d ∈ I 1,19999 , ι(1, 19999) =
(a) The total number of found here primitive T d -cycles is 42765, with the maximal value ˜ (d) = 944 attained at d = 14303 :

d∈I 1,19999 ˜ (d) = 42765 ; max d∈I 1,19999 ˜ (d) = 944 = ˜ (14303).
(5 : 8) (b) More than a half of 6667 dynamical systems D d explored in this study have less than 3 primitive cycles. To describe the distribution of these systems according to the values ˜ (d), let us define δ D,E (r) as the total number of systems D d , with d ∈ I D,E and with exactly r primitive cycles; then the corresponding function δ will be its experimentally found lower bound to :

δ D,E (r) = # d ∈ I D,E (d) = r .
(5 : 9)

The below table (Table 3) gives the values of the experimental function δ1,19999 in the interval 1 ≤ P ≤ 160. We have found only eleven systems D d with the numbers of primitive cycles bigger than 160, see Table 2.

Table 1.

The numbers ˜ (d) of the primitive T d -cycles traced in this study, for 500 values of d from 1 to 1499. For a given d ∈ I 1,1499 , find d ∈ I 1,59 , d ≡ d (mod 60) and q = d-d 60 . The value ˜ (d) can be found on the intersection of the q-th row and d -th column. 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 1 5 1 2 9 2 1 3 2 4 1 2 3 1 1 7 1 1 3 7 2 1 1 7 3 1 4 3 1 1 3 3 2 7 2 1 1 1 2 5 2 4 2 3 2 5 1 3 3 2 2 1 1 4 2 3 2 2 7 1 3 1 2 3 4 1 2 2 1 4 1 3 2 1 2 1 8 19 3 4 2 2 6 2 3 3 7 3 3 18 1 1 1 7 3 6 2 1 17 3 2 3 7 2 4 2 1 1 2 4 2 3 8 2 3 2 2 5 20 11 10 4 1 1 2 2 3 2 3 3 4 5 1 1 1 4 3 3 1 2 2 4 1 23 4 3 10 5 2 1 1 4 4 1 1 3 1 1 2 4 13 15 2 2 1 7 52 7 5 2 5 2 12 1 3 3 3 1 3 2 1 2 3 10 3 4 1 1 2 1 2 2 10 1 1 3 2 4 3 3 12 2 5 5 3 3 1 2 2 3 1 2 1 1 6 3 3 1 1 2 2 2 10 6 3 2 4 1 2 1 1 2 11 1 2 2 1 2 4 6 3 4 5 2 3 1 1 3 13 2 1 8 2 1 2 2 3 2 1 3 31 6 2 2 2 2 2 9 2 1 5 4 4 1 2 7 2 4 6 4 1 1 1 4 1 1 2 3 7 2 1 1 1 6 2 4 8 23 2 2 3 2 3 4 2 1 4 2 8 3 2 2 7 1 24 1 2 1 2 6 2 9 4 1 3 1 1 3 4 3 6 1 13 2 1 5 2 3 6 1 4 1 6 2 4 2 1 3 7 2 4 2 3 1 2 6 2 2 3 7 6 4 3 2 7 10 1 3 6 1 1 1 1 1 4 5 4 2 1 1 6 2 3 2 7 3 1 1 1 4 1 3 6 2 2 2 2 1 3 2 33 5 4 2 1 2 2 6 2 1 2 10 1 6 1 3 2 1 1 5 10 9 17 3 2 3 2 3 1 1 1 9 5 10 3 1 3 1 3 53 3 3 10 1 5 3 2 3 15 3 9 2 7 2 5 3 1 1 4 2 1 1 3 5 17 2 22 12 1 5 2 3 7 2 3 1 1 2 2 3 3 2 1 2 1 3 2 4 3 2 1 1 1 2 2 5 4 4 9

6 3 3 3 4 4 2 4 0 2 7 2 1 4 2 4 1 4 3 2 8 0 0 1 1 0 3 0 1 2 9 2 0 2 3 1 1 0 0 2 10 2 0 0 0 0 0 2 0 0 11 0 0 0 0 0 1 1 0 0 12 1 0 0 1 0 0 1 0 0 13 0 0 0 0 0 0 0 0 0 14 0 0 0 0 0 0 0 2 1 15 0 2 0 0 0 0 0 0 0 16 0 0 1 0 0 2 0 0 1
Experimental Evidence 5.6 : Conjecture 21. Both distributions count only systems D d with the numbers of cycles ranging from 1 to 120. (We remind the reader that the maximal number ˜ (d) of cycles found in this study is 944 (5:8), and, according to Table 3, only twenty out of 6667 systems have more than 120 primitive cycles). We have found that any n from the chosen range is a member of at least 18 primitive T d -cycles. Or, using a version of the notations (4:8) : (5 : 13)

(2) To present this statistic handily in a graphic form, Figure 2, we number the 20000 values of n ∈ I 1,59999 by the parameter q ∈ [1, 20000], according to (2:3), and denote by t(q) the number of primitive T d -cycles meeting n = ξ(q), d ∈ I 1,19999 :

     t(q) = ˜ ξ(q) 19999 1 = ˜ 6 • q 2 -(-1) q 19999 1 ; 1 ≤ q ≤ 20000 ⇐⇒ n = ξ(q) ∈ I 1,59999 .
(5 : 14)

(3) We give here also a more detailed sample of the experimental data, the first twenty values of the function t

(q) = ˜ n) 19999 1 , 1 ≤ n ≤ 59, Table 4.
Table 4. The first twenty values of the function t(q) = ˜ n(q)) 19999 1

, 1 ≤ q ≤ 20. Thus, for example, among 42765 primitive cycles discovered here, 452 cycles start at the first value of n, n = 1, and 440 meet the 18-th value, n = 53. 452, 354,359,414,396,410,423,399,324,409,426,265,407,415,418,422,395,440,300,406 Figure 2. The graph of the function t(q) = ˜ n(q)) 19999 1

, 1 ≤ q ≤ 20000. Notice three distinct and mysterious "depressions"6

. Shift Number -Member Number Disparate Duality.

In this section, we lay down a groundwork for the study of (disparate) duality between related shift number and member number properties. The impetus for this approach comes from the comparison between two sets of conjectures of §5 (Conjectures 18,19 versus Conjecture 20). The true meaning of this duality will become apparent, and the adequate diophantine formalism for its study will emerge in the next section.

The three conjectures of Lagarias can be viewed as a dual conjecture about projections of the set of memberships, as follows : Definition 6.1. (1) If a primitive T d -cycle C meets a number n ∈ D, then gcd(n, d) = 1 (Corollary 4.4(1)) and the pair n, d is called a primitive membership pair, or primitive membership, or simply membership. We denote by P the set of all primitive cycles and by M the set of all memberships.

(2) Since, for a given membership n, d , the corresponding primitive T d -cycle meeting n is unique, C = τ d (n) (2:2), one can extend to memberships the cyclic notations of length and oddlength, Lemma-Definition 4.2 (4:4). A membership of the length and oddlength k will be sometimes referred to as a (k, )-membership, with M (k) being the set of (k, )-memberships : k) .

                       ∆ = (n, d) ∈ D 2 gcd(n, d) = 1 ; M = (n, d) ∈ ∆ ; n, d is a membership ⇐⇒ C = τ d (n) ∈ P(d ; ζ : M -→ P ; ∀ n, d ∈ M , ζ n, d = C ∈ P(d ; length n, d = length(C) = ; oddlength n, d = oddlength(C) = k ; M (k) = n, d ∈ M ; oddlength n, d = k , length n, d = ; µ (k) = #M (
(6 : 1)

A diophantine interpretation of sets M (k) , § §7-9, (8:6), will result in a simple formula for their cardinalities (9:2).

(3) For the same reason, the set M n) of all memberships with a fixed first component (or, member number) n can be identified with both the set P n) of all primitive cycles meeting n and the (sub)set of all shift numbers d ∈ D n (2:3), with a T d -cycle (always exactly one) meeting n : (6 : 3)

∀n ∈ D , M n) = C ∈ P n)| n ∈ Set(C) ∼ = P n) = d ∈ D n | C = τ d (n) ∈ P(d .
(5) Through the mapping ζ (6:1) and natural projections of the set M of memberships, (6 : 4) the four above sets are formally related, as follows : (1) We introduce here and in the next section some well-known, but still very poorly understood diophantine formulae for primitive T d -cycles [Lagarias1990], [START_REF] Belaga | Embedding the 3x+1 Conjecture in a 3x+d Context[END_REF]], and we extend them to primitive memberships (Definition 5.4). These formulae are an indispensable tool in our analysis, § §9,10, of the above old and new conjectures, § §5, 6, as well as of the related experimental data. This analysis will result, in particular, in both the refinement of some known 3x + d conjectures and the introduction of a few new ones, § §9,10.

D ∇ memb ←-M ∇ shift -→ D , ∀ n, d ∈ M , ∇ memb n, d = n , ∇ shift n, d = d ,
       ∀n ∈ D , M n) = ∇ -1 memb (n) ⊂ M ; ζ M n) = P n) ζ : M n) ∼ = -→ P n) ; ∀d ∈ D , M(d = ∇ -1 shift (d) ⊂ M ; ζ M(d = P(d .
∀n ∈ D , 1 < µ n) = #M n) = #∇ -1 memb (n) = ∞ ; (2) ∀d ∈ D , 1 ≤ µ(d = #M(d = #∇ -1 shift (d) < ∞ .
Note that all our previous theoretical and experimental constructions, facts, claims, and observations, § §2-6, are restricted to, or derived from the study of (numerical results of) iterations of the algorithms (2:1,5,6).

The strength of our diophantine machinery is best illustrated by the fact that it permits to effectively construct (which means here, to produce a simple, transparent, and straightforward procedure for computation of) all primitive memberships and cycles, -and not just effectively enumerate primitive cycles, Note 1.1(3,4), -which means in recursion theory, to prove by "recursive trial and error" that there exists a recursive, or more strongly, primitively recursive one-to-one mapping from the set of natural numbers onto the set of primitive cycles.

To be sure, the specific "recursive trial and error" procedure developed in this study turns out to be very effective in localizing (as we belieive, all) primitive T d -cycles in the rather extensive range 1 ≤ d ≤ 19999, d ∈ D, cf. § §13,14. On the other hand, many important questions concerning primitive cycles and memberships remain out of reach even for the diophantine formalism.

It is true that it is only using this formalism that one is able not only to directly construct primitive cycles and memberships, but also to effectively evaluate the cardinalities of sets of such cycles or memberships with given lengths and/or oddlengths, §9.

Yet, no such formulae are known either for the number µ(d (6:6) of primitive memberships with a given shift number d, or for the numbers µ (k) (d , µ (k) (d , µ (d and µ (k) n), µ n) of such memberships with either second, or first component fixed and of the given length and/or oddlength, cf. §9 (according to Conjecture 22 (6:7), the cardinalities µ n) and µ (k) n) are presumed to be infinite). Moreover, one cannot as yet discard the option [Belaga 1998] that the very existence of such a formula is an unsolvable problem, -in the spirit of the negative solution [START_REF] Jones | Proof of Recursive Unsolvability of Hilbert's Tenth Problem[END_REF]] of Hilbert's Tenth Problem.

The actuality of the unsolvability option is best illustrated by the fact that many (3x+ d)-related question actually depend on intricate properties of exponential diophantine polynomials involving the numbers 2 and 3. Take, for example, the erratic behaviour, depending on the obscure rate of diophantine approximations of the logarithm log 2 3, of marginal Collatz numbers, Definition 7.1(5). As our calculations show (Figure 6, §10), such numbers are responsible for a disproportionally big chunk of primitive cycles with relatively small shift numbers d. This is why their unpredictable diophantine oscillations (Lemma 7.2(4), (7:13)) represent one of the most explicitly mysterious facets (and, probably, the most formidable single technical challenge in our search for a solution) of the 3x + 1 and 3x + d problems.

7. Collatz Configurations, Numbers, and Coronas.

We describe in this and the next sections a simple diophantine procedure which, from a given k-tuple P of positive integers (satisfying some elementary supplementary conditions and called here Collatz configuration), constructs a primitive membership of the oddlength k and length = |P|, with the norm | . . . | (or length) of a k-tuple defined as the sum of its components. And we show that this construction yields a natural oneto-one correspondence between the sets of primitive (k, )-memberships (Definition 6.1, above) and Collatz (k, )-configurations (Definition 7.1, below).

Most of the formulae of these two sections are well known (cf., e. g., Corollary 8.5), but their extensions to primitive memberships (Definition 7.1, Lemma 7.2, Theorems 8.1,3, Lemmas 8.4, 8.9) are new and carry some important theoretical and methodological implications.

In this section, we give precise definitions and detailed treatment of Collatz numbers and coronas, mentioned already in §1. Our notations follow those of [START_REF] Belaga | Embedding the 3x+1 Conjecture in a 3x+d Context[END_REF]], with some modifications and extensions. Definition 7.1. (1) Let Λ ⊂ N 2 be the set of all pairs of positive integers (k, ), satisfying the following equivalent inequalities :

λ k, = -k • log 2 3 ≥ 0 ⇐⇒ 2 -3 k > 0 , (7 : 1)
with the number λ k, called the (k, )-margin.

(2) Let σ k be the circular (counterclockwise) permutation on k-tuples of objects from a given domain. In this paper, we deal only with k-tuples of positive integers omit the subscript k when its value is implied by the context) :

∀P = p 1 , . . . , p k ∈ N k , σ(P) = σ k (P) = p 2 , . . . , p k , p 1 .
(7 : 2)

For any k ≥ 1, a k-tuple P k of positive integers is called aperiodic, if all k outcomes of its circular permutations are different :

σ j (P) = P = σ k (P) , 1 ≤ j < k .

(7 : 3)

(3) An aperiodic k-tuple P, satisfying the condition (cf. (7:1))

= |P| = p 1 + . . . + p k ≥ k • log 2 3 , (7 : 4)
is called a Collatz (k, )-configuration, or (Collatz) k-configuration of the length . We denote by Π (k) the set of all Collatz (k, )-configurations, and by Π their (disjoint) union :

∀(k, ) ∈ Λ , Π (k) ⊂ N k , π (k) = #Π (k) ; Π = (k, )∈Λ Π (k) .
(7 : 5)

(4) For any Collatz configuration P (7:1-5), define the integers A, B, F, G, H ∈ D, as follows :

a, b, f, g, h : Π -→ D ; ∀(k, ) ∈ Λ ∀P = p 1 , . . . , p k ∈ Π (k) ,              A = a(P) , B = B k, = b(P) , F = f (P) , G = g(P) , H = h(P) ; A = 1, if k = 1 ; 3 k-1 + 2 p 1 • 3 k-2 + . . . + 2 p 1 +...+p k-2 • 3 + 2 p 1 +...+p k-1 , otherwise ; B = 2 -3 k ; H = gcd(A, B) ; F = A H ; G = B H ; gcd(F, G) = 1 .
(7 : 6)

(5) According to (7:1), the integer B = B k, is positive; it is called here Collatz (k, )-number. A Collatz number B k, is called marginal, if = k •log 2 3 or, equivalently, if the (k, )-margin is zero, λ k, = 0 (7:1).

(6) The set of values A for all Collatz (k, )-configurations,

A k, = Image a Π (k) = a Π (k) ⊂ D , (7 : 7)
is called Collatz (k, )-corona, or Collatz B k, -corona, or simply corona.

Lemma 7.2. (1) The total number χ k, of Collatz (k, )-configurations can be calculated according to the following formula :

∀(k, ) ∈ Λ        χ k, = #Π (k) = -1 k-1 , if gcd(k, ) = 1 , r| gcd(k, ) µ(r) • r -1 k r -1 , otherwise , χ k, ≡ 0 (mod k) , (7 : 8)
where µ is the Möbius function [Nathanson 2000] :

µ(m) = 1 , if m = 1 , (-1) q , if m is the product of q distinct primes , 0 ,
if m is divisible by a square of a prime .

The low part of the formula (7:8), defined for pairs (k, ) with the property gcd(k, ) > 1, is universal and covers -but also obscures -the special upper case gcd(k, ) = 1. (See [Lagarias 1990] for an analogue of the formula (7:8).)

(2) The below lower and upper bounds to members A of Collatz corona are sharp :

∀(k, ) ∈ Λ ∀A ∈ A k, A k, = 3 k -2 k , A k, = 2 -k+1 • 3 k-1 -2 k-1 + 3 k-1 ; 3 k-1 < A k, ≤ A ≤ A k, < 2 -k+1 • 3 k-1 .
(7 : 9)

(3) The function a does not actually depend on the k-th component p k of a Collatz configuration (7:2-4), and its values for two k-configurations of different lengths can be equal. More precisely,

∀(k, ) ∈ Λ ∀j ≥ 1 , (k, + j) ∈ Λ & A k, ⊂ A k, +j .
(7 : 10) (4) With the exception of the trivial case (corresponding to the primitive T 1 -cycle (1:3) : cf. Corollary 8.5)

k = 1, = 2, A 1,2 = {1}, B = 1 ,
a Collatz number never belongs to the respective Collatz corona and, if k ≥ 4, is located below the upper bound (7:9) of the corona,

∀(k, ) ∈ Λ , B = B k, < 2 < A k, , if k ≥ 4 .
(7 : 11)

Non-marginal Collatz numbers (Definition 7.1(5)) are located above the lower bound (7:9) to Collatz corona (cf. (7:1)) :

∀(k, ) ∈ Λ , λ k, = -k • log 2 3 ≥ 1 =⇒ B k, > 3 k • 2 λ k, -1 > A k, . (7 : 12)
Some marginal Collatz numbers"descend" far below this limit, with the following (apparently, the best known and absolutely) nontrivial lower bound (10:25) [Rhin 1987] : (7 : 14) are injective. The injectivity of a (k) implies, according to (7:8),

∀(k, ) ∈ Λ , = k•log 2 3 =⇒      B k, = 3 k • 2 • 3 -k -1 = 3 k • 2 k -1 , 0 < k = k • log 2 3 -k • log 2 3 < 1 , 3 k-1 • k -13.3 < B k, < 20 • k -1 • A k, (7 : 13) (5) The mappings      ∀(k, ) ∈ Λ , a (k) : Π (k) → D ; b : Λ → D ; β = (a, b) : Π → D 2 ; γ = (f, g) : Π → D 2 ,
∀(k, ) ∈ Λ , #A k, = #a Π (k) = #Π (k) = χ k, . (7 : 15)
(6) The Collatz number B = B k, (7:6) depends only on the dimension k and length of its Collatz configuration. In particular, the mapping b is invariant under the action of the circular permutation σ (7:2), k) , b(P) = b σ(P) .

∀(k, ) ∈ Λ ∀P ∈ Π (
(7 : 16) (7) As to the mapping a, its injectivity implies that its actions on all k iterations of the permutation σ of any Collatz k-configuration are different : (7 : 17) This property justifies the following shorthand notation (cf. Definition 7.1(2)) : k) , A = a(P) ; define : σ(A) = a σ(P) .

∀(k, ) ∈ Λ ∀P ∈ Π (k) , a σ i (P) = a σ j (P) , 0 ≤ i < j ≤ k -1 .
∀(k, ) ∈ Λ ∀A ∈ A k, ∃ ! P = a -1 (A) ∈ Π (
∀(k, ) ∈ Λ ∀P = p 1 , . . . , p k ∈ Π (k) A = a(P) B = b(P) =⇒ 3A + B = 2 p 1 • σ(A) ; σ(A) = odd (3A + B) . (7 : 19) (9)
The last identity implies that, according to (7:6),

∀(k, ) ∈ Λ ∀A ∈ A k, , H = gcd(A, B) = gcd A, σ(A), σ 2 (A), . . . , σ k-1 (A), B .
(7 : 20) (10) In particular, according to (4:1), (7:16-18,19), the mapping h is invariant under the action of σ, albeit it substantially depends on P ∈ Π k, , and not just, as b, only on its dimension parameters k, . And so is the mapping g :

∀P ∈ Π      σ(H) = h σ(P) = gcd a σ(P) , b σ(P) = gcd σ(A), B = H ; σ(G) = g σ(P) = σ(B) σ(H) = B H = G .
(7 : 21) (10) Respectively, the action of σ on f is described by the formula similar to that for a (7:19) :

∀P ∈ Π , σ(F ) = f σ(P) = σ(A) σ(H) = odd 3A H + B H = odd (3F + G) , (7 : 22)
with all k numbers σ j (F ) = f σ j (P) being different : (7 : 23) Proof : (1) (A binary version of the formula (7:8) can been found in [Lagarias 1990])

∀(k, ) ∈ Λ ∀P ∈ Π (k) , σ i (F ) = σ j (F ) , 0 ≤ i < j ≤ k -1 .
We omit first the aperiodicity condition and prove the upper part of the formula (7:8) : the number of different representations of a positive integer as a sum of k < positive integers, p 1 + . . . + p k , with the fixed order of summands p j , is equal to -1 k-1 . A pure combinatorial proof is to decompose a -tuple of ones in k consequitive (say, from left to right) non-empty segments of ones, by choosing the ends of these segments, with the end of the k-th (rightmost) segment being the rightmost one of the -tuple. This leaves us with the choice of k -1 remainging ends out of -1 free ones. Now, if gcd(k, ) = 1, all such representations are aperiodic. Otherwise, gcd(k, ) = q > 1, with a periodic representation appearing, for any divisor r | q, as the concatenation of r identical aperiodic representations of r by k r summands. The rest is the ususal techniques of Möbius inclusion-exclusion formula.

(2-10) Straightforward verification.

End of the Proof.

Exponential Diophantine Criteria for Memberships and Cycles.

The recursive formulae (7:21,22) for the action of σ on the pair of mappings f, g mirrors the iterative formulae (4:4(2,3)) for calculation of an odd member of a primitive cycle from the previous one. This mirroring is at the heart of the following pair of dual constructions.

The first construction builds, from any Collatz configuration, a primitive membership, Theorem 8.1. The second one, inversely, reconstructs from any primitive membership its unique Collatz configuration prototype, Theorem 8.3.

Theorem 8.1. (1) For any Collatz configuration P, the pair γ(P) of positive integers (7:14) is a primitive membership : k) .

γ : Π -→ M ; ∀(k, ) ∈ Λ ∀P ∈ Π (k) , γ k, : Π (k) -→ M (k) ; γ k, (P) = f (P), g(P) = F, G ∈ M (
(8 : 1)

(2) The corresponding primitive T G -cycle with the odd member number F, C = ζ F, G (6:1) is constructed, as follows. According to (7:23), for any k-configuration P, all components of the k-tuple

Φ(P) = F = f (P), σ(F ) = f σ(P) , . . . , σ k-1 (F ) = f σ k-1 (P) ∈ D k (8 : 2)
are different. Suppose n 0 = σ j (F ), for some j, 0 ≤ j ≤ k -1, is the minimal member of the k-tuple Φ(P) (8:2). Then the k-tuple σ j Φ(P) is the odd-part Odd (C) (4:4(2)) of a primitive T G -cycle C.

According to Lemma 7.2(5), the mapping γ is injective : to different Collatz configurations correspond different primitive memberships. It is also surjective, and thus, represents a natural one-to-one correspondence between Collatz configurations and memberships. We shall prove it by displaying a procedure θ, inverse to γ, which assigns to a membership its unique Collatz configuration counterpart.

The procedure θ will be initially defined on the set M of lowermost primitive memberships (Definition 8.2, Theorem 8.3(1-4)), and then extended to all mamberships (Theorem 8.3(5)) : Definition 8.2. (1) A primitive membership n, d is called lowermost if its left component n is the minimal (odd) member of the corresponding primitive cycle. Thus, in accordance with the notations (4:4(2)),

n, d is lowermost ⇐⇒ C = ζ n, d = n = m 0 , m 1 , . . . , m -1 .
(8 : 3)

(2) Respectively, Collatz (k, )-configuration P is called lowermost if the primitive membership γ(P) (8:1) is lowermost. We use tilde sign for notations for sets of lowermost primitive memberships and Collatz configurations : M, Π(k) , etc.

(Some basic properties of lowermost memberships and configuration will be the subject of the below Lemma 8.7, and their applications to Conjecture 20, §5, can be found in §9.)

Theorem 8.3. (1) Let C be a primitive T d -cycle (4:4) of the length and oddlength k, and let P k be the set of all such cycles. Then (k, ) ∈ Λ.

(2) Let P k be the set of all primitive cycles of the length and oddlength k.

Let C be a primitive T d -cycle, and let n 0 be its minimal member. Then, tautologically, the pair (n 0 , d) = ω(C) is the lowermost primitive membership uniquely characterising C, and this one-to-one correspondence is inverse to ζ, Definition 6.12 (6:1) :

P ω -→ ←- ζ M : ∀(k, ) ∈ Λ , P k ω -→ ←- ζ M(k) .
(8 : 4)

(3) For any C ∈ P k , let the k-tuple Even(C) be defined as above, (4:4(3)). Then, Even(C) is Collatz (k, )-configuration.

(4) Moreover, Even(C) is a lowermost configuration, such that γ Even(C) = ω(C). Accordingly, the construction θ can be defined for the subsets M, Π of lowermost memberships and configurations, as follows :

P ω -→ ←- ζ M Even γ θ | M = Even • ζ : M ω -→ P Even -→ Π .
Π (8 : 5)

(5) Let now, for some (k, ) ∈ Λ, n, d ∈ M (k) be a primitive (not necessary, lowermost) membership, and let C = ζ n, d be the corresponding primitive T d -cycle (6:1) meeting n, of the length and oddlength k. Being an odd member of C, the integer n can be identified with some n r ∈ Odd (C), 0 ≤ r ≤ k -1 (4:4(2)). The k-tuple Even(C) being Collatz configuration, so is its σ r -permutation. Define θ n, d = σ r Even(C) and verify that θ is inverse to γ : k) .

Π γ -→ ←- θ M :                                        ∀ n, d ∈ M ⊂ M , θ n, d = Even ζ n, d ; cf. (8 : 5) ∀ n, d ∈ M ,          θ n, d = σ r Even ζ n, d , n = n r ∈ Odd ζ n, d ; γ θ n, d = n, d ; ∀P ∈ Π , θ γ(P) = P ; ∀(k, ) ∈ Λ , Π (k) ∼ = M (k) : Π (k) γ (k) -→ ←- θ (k) M (k) ; µ (k) = #M (k) = π (k) = #Π (
(8 : 6)

Or at greater length,

∀(k, ) ∈ Λ ∀ n, d ∈ M (k)                                C = ζ n, d , k = oddlength(C) , = length(C) , n = n r ∈ Odd (C), 0 ≤ r ≤ k -1 ; θ n, d = P = p 1 , . . . , p k = σ r Even(C) = σ r e 1 , . . . , e k ∈ N k ; ∀j (1 ≤ j ≤ k) , p j = e j+r , if 1 ≤ j ≤ k -r e j+r-k , otherwise ; |P| = p 1 + . . . + p k = e 1 + . . . + e k = .
(8 : 7)

Proof : Straightforward verification based on the assertions of Lemma 7.2.

End of the Proof.

The constructions of Theorems 8.1, 8.3 imply the following well-known diophantine criteria [Lagarias1990], [START_REF] Belaga | Embedding the 3x+1 Conjecture in a 3x+d Context[END_REF]] for the existence of primitive cycles with given parameters n and/or d : Corollary 8.4. (1) Given a shift number d and an integer n (d, n ∈ D), there exists a (not necessary primitive) cycle T d -cycle of the length and oddlength k meeting n iff there exists a member A of Collatz B k, -corona, A ∈ A k, , such that

d • A = n • B k, .
(8 : 8)

(2) Given a shift number d ∈ D, there exists a primitive T d -cycle of the length and oddlength k, iff there exists a member A of Collatz B k, -corona, such that

d = B k, gcd(A, B k, )
.

(8 : 9)

Using (8:9), one can "translate" Conjectures 17, 18 into their diophantine equivalent, Conjecture 23 below.

(3) The formula (8:9) implies the following congruences :

d = B k, gcd(A, B k, ) =⇒ (1) B k, ≡ 0 (mod d) ; (2) d • A ≡ 0 (mod B k, ) .
(8 : 10)

The first congruence is a necessary condition for a T d -cycle to be of the length and oddlength k. The necessary condition provided by the second congruence is also sufficient,

if d = 1 or if d is prime. In particular, if d = 1, then B k, | A.
Which implies the equivalence between the cyclic part of the 3x + 1 conjecture, Conjecture 4, §1, and its diophantine version, Conjecture 5, §1.

(4) According to (8:10), below Conjecture 24 is formally stronger than to the finitenumber-of-primitive-cycles conjecture (Conjectures 18, 22(2) (6:7(2 right))), but, in fact, is equivalent to it.

(5) Similarly, given an integer n ∈ D, there exists a primitive cycle of the length and oddlength k meeting n iff there exists a member A of Collatz (k, )-corona, such that

n = A gcd(A, B k, )
.

(8 : 11)

Thus, Conjectures 19, 20 are equivalent to the below diophantine Conjecture 25.

(6) The formula (8:9) implies the following congruence :

n = A gcd(A, B k, ) =⇒ (1) A ≡ 0 (mod n) ; (2) n • B k, ≡ 0 (mod A) . (8 : 12)
In particular, if n = 1 or n ≥ 5 is prime and (k, ) ∈ Λ, there exists a primitive (k, )-membership with the member number n, iff the congruence (8:12(2)) holds for some A ∈ A k, .

(7) For composite n ∈ D, the member-number analogue, based on the condition (8:12), of below Conjecture 24 does not imply the infinite-number-of-member-numbers Conjecture 20. In fact, an assumption that the congruence in (8:12) has an infinite number of solutions formally implies only that (i) n is a member of an infinite number of cycles, not necessary primitive, and (ii) that some divisor q of n, 1 < q < n, belongs to an infinite number of primitive cycles.

(8) Finally, the combination of the above claims (8:9,11) yields the following criterion. A pair of integers (n, d) ∈ D 2 is a primitive membership of the length and oddlength k iff gcd(n, d) = 1 and there exists a member A of Collatz (k, )-corona, such that

n = A gcd(A, B k, ) , d = B k, gcd(A, B k, )
.

(8 : 13)

Conjecture 23. For any d ∈ D, there exists (1) at least one and (2) at most finite number of pairs (k, ) ∈ Λ, such that the equlity (8:9) holds for at least one A ∈ A k, . Moreover (cf. the notations (6:6)),

∀d ∈ D ∀(k, ) ∈ Λ , µ (k) (d = # P ∈ Π (k) B k, = d • gcd(a(P), B k, ) . (8 : 14)
Conjecture 24. For any d ∈ D, there exists only finite number of pairs (k, ) ∈ Λ, such that the congruence (8:10) holds for some A ∈ A k, .

Conjecture 25. For any n ∈ D, there exists an infinite number of pairs (k, ) ∈ Λ, such that the congruence (8:11) holds for some A ∈ A k, . Moreover (6:6), = 6487 , and thus, corresponds to a primitive T 6487 -cycle of the length 16 and oddlength 10. It is feasible to check even by hand that there are 456 such solutions. We have found also 78 solutions (among 534 primitive T 6487 -cycles altogether), corresponding to the below congruences, 2 32 -3 20 ≡ 2 48 -3 30 ≡ 2 64 -3 40 ≡ 2 96 -3 60 ≡ 0 (mod 6487) .

∀n ∈ D ∀(k, ) ∈ Λ , µ (k) n) = # P ∈ Π (k) a(P) = n • gcd(a(P), B k, ) .
But "why" are elimintated an infinite number of other possible candidates for the congruence B k, ≡ 0 (mod d) (8:10(1)) ? (2) In the case d = 827, the smallest congruence of the type (8:10(1)) is : 15 182 893 = 2 24 -3 13 ≡ 0 (mod 827), with experimentally found 4 solutions. Two more solutions correspond to the pair ( , k) = (48, 26), with one solution corresponding to (72, 39). But, again, "why" not others ? Say, 2 96 -3 52 , or maybe 2 82 -3 10 , with its prime factorization : (

3) The answer, suggested by the last example, might be that the prime factorization "signature" of numbers 2 -3 k cannot be "captured" in the congruence (8:10(2)), beyond a certain finite limit, by numbers of the type A ∈ A k, . In other words, relatively big prime factors are, apparently, common to all Collatz numbers above certain limits, and such factors are beyond the prime factorization "power" of members of respective Collatz coronas.

(4) On the other hand, as Conjectures 20, §5, and 28, 29, §11, suggest, there exist no similar obstacles in solving the congruence (8:12(2)), probably because there exist enough Collatz numbers with relatively big divisors whose prime factorizations comprise only relatively small prime factors. These insights show the apparent importance of surprising sporadic properties of numbers 2 -3 k in an eventual solution of 3x + 1 and 3x + d problems.

Notations 8.6. The mutually inverse isomorphisms γ, θ (8:6) between the corresponding (sub)sets of Collatz configurations and primitive memberships permit us to extend to Collatz configurations the notations (6:5,6) for the sets of Collatz configurations yielding either n, or d, as, respectively, the corresponding member-or shift-number :

                                               (1) ∀n ∈ D , Π n) = θ M n) ; π n) = #Π n) ; (2) ∀(k, ) ∈ Λ , Π (k) n) = θ (k) M (k) n) ; (3) π (k) n) = #Π (k) n) = µ (k) n) = #M (k) n) ; (4) ∀ ≥ 1 , Π (k) n) = θ (k) M (k) n) ; (5) π (k) n) = #Π (k) n) = µ (k) n) = #M (k) n) ; (6) ∀d ∈ D , Π(d = θ M(d ; π(d = #Π(d ; (7) ∀(k, ) ∈ Λ , Π (k) (d = θ (k) M (k) (d ; (8) π (k) (d = #Π (k) (d = µ (k) (d = #M (k) (d . (9) ∀k ≥ 1 , Π (k) (d = θ k M (k) (d ; (10) π (k) (d = #Π (k) (d = µ (k) (d = #M (k) (d .
(8 : 16)

Chapter IV. The Primitive Cyclic Structure of Systems D d .

The diophantine formalism of Chapter III, with its fundamental isomorphism between sets of Collatz configurations and primitive memberships, Π γ -→ ←θ M (8:6), can be used in two ways to extract new information about properties of (sets of) primitive memberships and/or cycles. Namely, the formalism can be applied either directly, by constructing (sets of) primitive memberships/cycles as γ-images of some well-defined (sets of) Collatz configurations. Or inversely, one can study properties of ω-images of well-defined (sets of) primitive memberships/cycles.

The direct approach will be the main subject of the next two sections. The inverse procedure will be instrumental in the study of (sets of) primitive memberships/cycles with a given, first, shift number, §10, and then, member number n, §11.

Memberships and Cycles with Fixed Shift Number and/or Member Number.

A fine example of the effectiveness of the direct approach mentioned above represent elementaty solutions of the following problems (see also [Lagarias 1990]) : Problem 9.1. (1) For a given pair (k, ) ∈ Λ, find the number of all primitive cycles of the length and oddlength k.

(2) Find the number of all primitive cycles of the length ≥ 2.

According to the below notations (9:1), we need actually to calculate the parameters (k) and :

Notations 9.2. Let Z, Z (k) , Z , Z (k) and be the generic notations for the sets of primitive memberships M, Collatz configurations Π, or primitive cycles P, respectively, of the length and/or oddlength k, and let z, z (k) , z , z (k) and z(x), z (k) (x), z (x), z (k) (x) be the correspondingc notations for the cardinalities of such sets, µ n), µ(d , π n), π(d , (d) (defined in (6:6), (8:16), and (4:8), respectively). These sets and cardinalities are related by the following obvious equalities :

                             Z = •log 3 2 k=1 Z (k) , Z (k) = ∞ = k•log 2 3 Z (k) , Z = k≥1 Z (k) = ≥2 Z ; z = •log 3 2 k=1 z (k) , z (k) = ∞ = k•log 2 3 z (k) , z = k≥1 ≥ k•log 2 3 z (k) = k≥1 z (k) = ≥2 z ; z (x) = •log 3 2 k=1 z (k) (x) , z (k) (x) = . . . , z(x) = . . . .
(9 : 1) In the above notations, the following lemma solves Problem 9.1 (a different solution can be found in [Lagarias 1990]) : Lemma 9.3. (1) According to Theorems 8.1, 8.3, Lemma 7.2(1), and the formulae (8:6) the number of primitive memberships of the length and oddlength k (6:1) is equal to χ k, (7:8) :

∀(k, ) ∈ Λ , µ (k) = π (k) = χ k, ≡ 0 (mod k) . (9 : 2)
Respectively, the number (k) of primitive cycles of the length and oddlength k is equal to :

∀(k, ) ∈ Λ , (k) = #P (k) = χ k, k . (9 : 3)
(2) The number of primitive cycles of a fixed length ≥ 2 is equal to (cf. the summation formulae (9:1)) :

∀ ∈ N, ≥ 2 , = •log 3 2 k=1 χ k, k .
(9 : 4)

Example 9.4 : Case = 14, k = 3 < 8 = • log 3 2 . According to (7:8), gcd(3, 14) = 1 implies :

3 14 = χ 3,14 3 = 1 3 2 13 = 26 .
We have found experimentally all these 26 primitive cycles, namely : two T 1487 -cycles, starting at n = 11, 13, respectively, and 24 T 16357 -cycles, starting at, respectively, = 19, 23, 29, 31, 37, 47, 49, 53, 65, 79, 85, 89, 97, 149, 161, 169, 185, 277, 233, 271, 289, 313, 361, 569 . This example is representative of one of the series of (successful) controlling checks of the exhaustiveness of our search procedure. In fact, according to the below limits (9:5) on values of shift numbers of primitive cycles with given length and oddlength, the possible values of d for a cycle C ∈ P 3 14 belong to the range of this study, d ≤ B 3,14 = 16357 < 19999, and a really thorough search should locate all 26 candidates. As to the "full" cardinalities µ n), µ(d and (d) (the subjects of Conjectures 17-22, § §5, 6), or even their "oddlength" versions, µ (k) n), µ (k) (d , (k) (d), there do not apparently exist as elementary or, at least, as transparent formulae for their (k, )-and -refinements, as the above (9:2-4). Still, the below basic diophantine reductions of Conjecture 22, §6, provide us with new insights, otherwise unavailable, into the properties of the parameters in question : see Conjecture 23, §10, and Conjecture 25, §11.

n
The following, only partially understood phenomena, illustrate the underlying arithmetical difficulty : the absense of almost any predictable correlation betweeen the pair of parameters (k, ) and the values of components of the corresponding primitive membership n, d . Another salient feature of the emerging picture is the pervasiveness of the disparate (n, d)-duality, §5 : not only are the corresponding (n, d)-properties complementary, the levels of difficulty of their existing and/or prospective proofs are complementary, too.

Problem 9.5 The bounds (7:9) and (7:11-13) to values of, respectively, A ∈ A k, and B = B k, imply the following, a priori exponentially wide bounds to the components n = f (P), d = g(P) (7:6) of a primitive membership of given length and oddlength :

∀(k, ) ∈ Λ ∀P ∈ Π (k) , 1 ≤ n = f (P) ≤ A k, < 2 -k+1 • 3 k-1 ; 1 ≤ d = g(P) ≤ B k, < 2 . (9 : 5)
Are these bounds sharp or, at least, "relatively" sharp? Note that if some of those bounds are (relatively) sharp, and remain so with growing, it would imply, in particular, that to relatively "small' pairs (k, ) correspond sometimes exponentially big values of n and/or d, whereas for some relatively "big" (k, ), the values of n and/or d are (absolutely or relatively) small. See § §10-11 for the study of these and related phenomena for, respectively, shift numbers d and member numbers n.

Shift Number Conjectures and Claims.

The shift number conjectures 17, 18, §5, or equivalently, 22(2), §6, 23, §8, assert that, for any d ∈ D the number (d) (5:1,2) (or equivalently, µ(d (6:7(2))) of primitive T d -cycles (respectively, memberships) is a positive integer (cf. the above generic notations (9:1)) :

∀d ∈ D                                1 ≤ (d) =          ≥2 1≤k< •log 3 2 (k) (d) = ≥2 (d) k≥1 >k•log 2 3 (k) (d) = k≥1 (k) (d)          < ∞ ; 1 ≤ µ(d =          ≥2 1≤k< •log 3 2 µ (k) (d = ≥2 µ (d k≥1 >k•log 2 3 µ (k) (d = k≥1 µ (k) (d          < ∞ .
(10 : 1)

We are concerned in this section with the finite-number-of-primitive-cycles conjecture (Conjectures 18, §5, 23, §8,), or, in other words, with the finiteness of the sums in (10:1). The double summations of (10:1) suggest two similar strategies : in each case, first prove that every summand is finite (which either have been already done above, for the -summunds, or will be done in this sections, for their k-counterparts), and then prove that the number of non-zero summands is finite (the most difficult, and still open parts of the problem).

In the first case, the summands are (d) or µ (d (i. e. the numbers of T d -cycles or memberships of the given length ), and the task to prove the finiteness of summands (which are themselves sums of a finite number of finite summands) is quite easy. In the first, and longest, part of this section, we study the dependence of the numbers of primitive cycles and memberships with a given shift number on their lengths and margins (Corollary 10.1,Lemmas 10.2,10.5,10.7,Conjectures 26,27).

In the second case, the summands are, by definition, sums of infinite number of finite summands (k) (d) or µ (k) (d , and their finiteness cannot be taken for granted. We conclude this section with an improved (both in substance and in methodology) version of the upper bound [START_REF] Belaga | Embedding the 3x+1 Conjecture in a 3x+d Context[END_REF]] to the numbers of primitive cycles and memberships with given shift number and of the given oddlength.

Corollary 10.1. According to (9:1-4),

∀(k, ) ∈ Λ                              M (k) = d∈D M (k) (d) =⇒          µ (k) (d ≤ χ k, < ∞ ; µ (d ≤ •log 3 2 k=1 χ k, < ∞ ; P k = d∈D P k (d) =⇒          (k) (d) ≤ χ k, k < ∞ ; (d) ≤ •log 3 2 k=1 χ k, k < ∞ .
(10 : 2)

In other words, the number of primitive memberships (cycles) with a given shift number and of a given length is finite.

This fact implies (Lemma 10.2 below) that the following conjecture is equivalent to the finite-number-of-primitive-T d -cycles conjecture (Conjectures 18,22(2) (2) Wild fluctuations of the functions (d) and (d) (Figure 5) are cancelled, and their occasional, but steady grows is preserved, by the following upper and lower length limit threshold functions :

∀d ∈ D , L(d) = max{ (d ) d ∈ I 1,d } ; L(d) = max{ (d ) d ∈ I 1,d } .
(10 : 6) (For the definition of the lower length limit (d) (10:5) to be sound, one needs Conjecture 17 : there exsists at least one primitive T d -membership. For the soundness of the defintion of the upper length limit (d), one needs both conjectures : cf. Conjecture 26, with L = L(d) = (d) chosen as the upper bound in (10:3).)

The below solution of Problem 10.3(1) gives a trivial but rather realistic universal lower bound to lengths of T d -memberships (Lemma 10.5(1)), and demonstrates that in an infinite number of cases this universal lower bound can be considerably strengthened (Lemma 10.5(2) [Lagarias 1990]).

Neither upper, nor nontrivial lower bounds to the upper length limit (d) are known (according to Conjecture 26 and Lemma 10.2, any universal upper bound would prove the finite-number-of-primitive-cycles conjecture, Conjecture 18). However, since, trivially, (d) ≥ (d), the below lower bounds (10:8) for an infinite series of shift numbers provide the only available now nontrivial lower bounds to the upper length limit for at least some shift numbers.

Lemma 10.5. (1) The following lower bound to the lower length limit is universal :

∀d ∈ D , (d) ≥ log 2 d .
(10 : 7)

(2) For an infinitely growing series of shift numbers, d 1 , d 2 , . . . , d j , . . ., the lower length limit has the following lower bound :

∃f : N -→ N , i < j ⇐⇒ f (i) < f (j) & ∀j ∈ N , d f (j) ≥ 5 4 • (d f (j) ) 1
3 . (10 : 8)

Proof :

(1) According to (8:9), : (10 : 9) which implies the bound (10:7). As our calculations show, in many cases, the bound (10:7) is very close to be sharp.

∀ ≥ 2 ∀(k, ) ∈ Λ ∀P ∈ Π (k) , d = B k, gcd a(P), B k, ≤ B k, < 2 ,
(2) See [Lagarias 1990].

End of the Proof.

Comments and Experimental Evidence 10.6. (1) The smaller is the cancellation factor gcd( a(P), B k, ) ≥ 1 in (10:9), the closer is the corresponding lower length limit (d) to the lower bound (10:7). Thus, for example, the primitive membership 1, 16381 has the length = 14 > log 2 16381 = 13.9997.

(2) However, as Lagarias has discovered, in some cases, this factor is necessary very huge : this is the phenomenon behind the lower bounds (10:8). Cf. (1:13) and Example 2.4.

(3) The problem of evaluating the precise (or sharp) rate of growth of the functions L(d), L(d) remains open. However, the experimental data (cf. (10:10) and Table 5) suggest that this rate is, most probably, much higher than that suggested by (10:8), and as high as d log d : cf. (10:10), Table 5, Conjecture 27, and Figure 5 below.

(4) Moreover, excluding probably an infinite, but "very scarce" subset of shift numbers, the functions L(d) and L(d) are identical : an overwhelming majority of experimentally studied here systems D d with at least one "very long" primitive cycle have only one cycle, (d) = 1; see (10:10), subsection (7), and Table 5

below.

(5) There are only 61 pairs (k, ) ∈ Λ, with the corresponding Collatz numbers B k, belonging to the range I 1,19999 . And there are only 106 values of d, out of the total number 16), ( 17) have the parameters , d as given in the corresponding columns of Table 6. of 6667 explored here, with the corresponding primitive T d -cycles of such (k, ) lengths and oddlengths.

(6) The last observation illustrates why the great majority of primitive cycles, experimentally recovered in this study, should come from Collatz configurations of much bigger values of lengths, oddlengths, and Collatz numbers. Among them there are 11 primitive cycles of lengths varying from 2004 to 2604, one cycle of the length 3918 and one of the length 4531, Table 5. In particular, we have found (cf. Figure 6) : 5, with at least one "long" primitive cycle have more than one primtive cycle, (d) > 1. (Curiously enough, one of those systems, D 14303 , has the maximal number of primitive cycles with a given shift number discovered in our experimental study, (14303) = 944 : cf. Figure 3.) The other 13 systems fit into the pattern of the lower bound (10:8) : cf. the above subsection (4).

                           (
(8) All primitive cycles of Table 5 have rather big margins (7:1,12). The general statistics belies this particular pattern, apparently, typical for cycles with "big" lengths and "small" shift numbers. The graph of the distribution w(λ) (9:10) of values of the margin λ = λ k, (Figure 6) shows that marginal Collatz numbers (Lemma 7.2(4) (7:12)) and, more generally, Collatz numbers with small margins, account for a disproportionally big number of primitive cycles with shift numbers d from a fixed interval, d ∈ D 1,D . This should not come as a surprise to us : for a given ≥ 2, to smaller margins correspond smaller Collatz numbers and, finally, primitive cycles with smaller shift and member number which are readily captured by our search procedure, §12.

(9) Figure 6 represents the graph of the function w, defined as follows (cf. (7:12)) :

∀λ ≥ 0              ∀d 1 , d 2 ∈ D        W (λ; d 1 , d 2 ) = C ∈ P(d) d 1 ≤ d ≤ d 2 & λ k, = λ , w(λ; d 1 , d 2 ) = #W (λ; d 1 , d 2 ) ;
w(λ) = w(λ; 1, 19999) .

(10 : 11) (10) Similar phenomena characterize the distribution of values of "big" shift numbers with cycles of a "small" length, as well (cf. Problem 9.5, (9:5)). Thus, the above Example 9.4 shows the attainability of the upper bound to d, with d equal to the corresponding Collatz number B 3,14 . This question is more amenable to a theoretical analysis. In particular, the 3x + 1 conjecture implies that if d = B k, is prime, then there exist 1 k χ k, primitive T d -cycles (Lemma 10.7 below). We have confirmed this implication for all 29 prime (out of the total number of 61) Collatz numbers B < 20000. This is another example of successful controlling checks of the thoroughness of our search procedure.

Lemma 10.7. (1) According to (7:6), a primitive T d -cycle, d = B k, , exists iff at least one member A of Collatz (k, )-corona is relatively prime to B k, :

∀(k, ) ∈ Λ , P(B k, = ∅ ⇐⇒ 1 ∈ gcd(A, B k, ) A ∈ A k, .
(10 : 12)

(2) The diophantine equivalent (Conjecture 5, §1, Corollary 8.4(2)) of the 3x + 1 conjecture implies that, if d = B k, is prime, then there exist 1 k χ k, (7:8), (9:2-4) primitive T d -cycles.

Proof : Selfevident.

End of the Proof.

The following conjectures formalize the above experimental insights (cf. Figure 5) :

Conjecture 27. (1) Define inductively the upper and lower length limit threshold sets (cf. Definition 10.4) D, D, as follows :

D = {d 1 < d 2 < . . .} ⊂ D, d 1 = 1, d k+1 = min d ∈ D L(d) > L(d k ) ; D = {d 1 < d 2 < . . .} ⊂ D, d 1 = 1, d k+1 = min d ∈ D L(d) > L(d k ) .
(10 : 13) (4) The upper and lower length limit threshod functions L and L satisfy the following inequalities, with some "relatively small" constants c 1 , c 2 , c 3 , c 4 : (10 : 14) From the length-related aspects of the 3x+d conjecture, we turn now to the oddlengthrelated ones. The finiteness of the number µ (k) (d of primitive T d -memberships of the oddlength k, with an effective (but, in practice, very huge) upper bound, has been proved in [START_REF] Belaga | Embedding the 3x+1 Conjecture in a 3x+d Context[END_REF]]. The proof used a general inequality of [Baker, Wüstholz 1993] on diophantine approximations of linear Z-combinations of logarithms of natural numbers.

∀d ∈ D , c 1 • d log d < L(d) < c 2 • d ; ∀d ∈ D , c 3 • d log d < L(d) < c 4 • d .
We improve here our finiteness result, both methodologically and quantitatively. More precisely, the finiteness of the number µ (k) (d is proved below in a quite elementary way, without any allusion to diophantine approximation theory or any other nontrivial fact outside our elementary diophantine formalism, § §7, 8.

On the other hand, we are able to improve our previous upper bound to µ (k) (d , thanks to a more ancient, less general, but much more effective result from [Rhin 1987], on diophantine approximation of linear combinations of the logarithms log 2 and log 3 (cf. the inequality (10:25) below).

Note, finally, that the crucial common step in the below proofs of the upper bounds (10:15,16) is based on the general diophantine cyclicity criterion (8:8) (or (10:17) below). Thus, the below bounds hold also for the numbers ς(d) of all T d -cycles, not necessary primitive ones : cf. (4:11,12).

Theorem 10.8. (1) For any d ∈ D and any k ≥ 1, an elementary proof yields the following exponential upper bound to the number of primitive T d -memberships of the oddlength k (or, equivalently, of Collatz configurations of the oddlength k yielding n as the member number of the corresponding primitive membership (8:16(10))) :

∀d ∈ D ∀k ≥ 1 , µ (k) (d < d • (4.5) k .
(10 : 15)

(2) A non-trivial and, as a matter of fact, the best known at present improvement of the above upper bound, based on a deep result [Rhin 1987] from diophantine approximation theory, still remains, quite disappontingly, exponential :

∀d ∈ D ∀k ≥ 1 , µ (k) (d < 3d • (1.5) k • k 13.3 .
(10 : 16)

Proof : (1) As in [START_REF] Belaga | Embedding the 3x+1 Conjecture in a 3x+d Context[END_REF]], we count the number of respective memberships, using our combined formula (8:8) for shift and member numbers of primtive memberships, with the shift number d and the oddlength k fixed :

n = d • A B k, . (10 : 17)
Define now the number (which, a priori, might be infinite, too) Together with (10:20,22), this inequality implies the bound (10:16).

N (d, k) = sup d • A B k, ∀ > k • log 2 3 & ∀A ∈ A k, . (
End of the Proof.

Member Number Conjectures and Claims.

We study here some theoretical implications of new experimental data concerning distributions of member numbers in primitive cycles. This distributions are the subject of Conjectures 19, 20, §5 [Lagarias 1990]. We remind the reader that Conjecture 19 claims that any odd positive integer n not divisible by 3, n ∈ D, is met by at least one primitive cycle, and Conjectures 20 strengthens this claim, asserting that n is met by an infinite number of such cycles: cf. Experimental Evidence 5.7, Table 4, and Figure 2,§5.

Here, our main technical tool will be the formula (7:6), (8:11) for the member number n of the primitive membership n, d corresponding to Collatz (k, )-configuration P :

∀(k, ) ∈ ∆ ∀P ∈ Π k, γ(P) = n, d , n = f (P) = A gcd(A, B k, ) = a(P) gcd a(P), B k, . (11 : 1)
As we have already observed above (Lemma 7.2 (7:10)), the function a(P) (7:6) does not actually depend on the rightmost component p k of a configuration P. This means that the expression (11:1) for n carries p k only as a summand of the exponent = p 1 + . . . + p k of the Collatz number B k, = 2 -3 k . Thus, one can vary p k in such a way that a value n once attained will be recapitulated infinitely many times. This is the idea behind the proof ( [Lagarias 1990], Lemma 11.1 below) that Conjectures 19, 20 are, in fact, equivalent : if n is met by at least one primitive cycle, then it is met by an infinite number of primitive cycles of the same oddlength and with an identical diophantine structure. This makes the rather audacious infinity claim of Conjecture 20 as plausible as that of Conjecture 19, dual to Conjecture 17 for shift numbers.

However, as our calculations show (cf. Experimental Evidence 5.7, In what follows, we assume that a positive odd integer not divisible by 3 is fixed, n ∈ D, together with the set Π n) (8:18) of Collatz configurations yielding n as the member number of the corresponding primitive membership (cf. (7:6), (8:1)) :

∀n ∈ D ∀P ∈ Π n) f (P) = n .
(11 : 2)

The below re-statements of the original claim from [Lagarias 1990] is adapted to our aims and notations.

Table 6. The first twenty values of the functions t(q), i(q), s(q), r(q) = t(q)i(q), i(q) s(q) . Cf the notations (11:15). 452, 354,359,414,396,410,423,399,324,409,426,265,407,415,418,422,395,440,300,406 r(q) 018,011,008,012,005,006,021,012,007,001,009,006,016,001,004,008,014,001,002,001 i(q) 434, 343,351,402,391,404,402,387,317,399,417,259,391,405,414,414,381,430,298,405 s(q) 223,203,194,217,231,221,227,206,192,225,210,177,218,227,232,221,220,241,201,220 i s (q) 1.9, 1.7, 1.8, 1.8, 1.7, 1.8, 1.9, 1.9, 1.6, 1.7, 2.0, 1.5, 1.8, 1.8, 1.8, 1.9, 1.7, 1.8, 1.5, 1.8 of primitive memberships found in this study (according to Note 4.8(2), the tilde-mark indicates that we deal with the experimental value of the corresponding theoretically defined parameter), for 20000 values n of their member number component, in the rectangle R 1,59999 1,19999 : (2) In a smaller rectangle, R 1,8249 1,19999 , for 2750 values of the member number n, we have calculated also the distribution of reducible memberships , i. e., memberships which are (11:c,d)-type replicas of other memberships (see for details Definition 11.3). The below sample (the third line of Table 6, which is an extension of the above Table 4, §5) of experimentally found values of the number r(q) of reducible memberships demonstrates that they account for only a tiny fraction of memberships. Thus, for example :

∀N, N , D, D ∈ D , R N,N D,D = (n, d) ∈ ∆ I N,
(i) out of 452 of experimentally discovered in the rectangle R 1,8249 1,19999 memberships of the form 1, d , only 18, or less than 4%, are reducible;

(ii) and out of the total number 823954 of calculated in this rectangle primitive memberships, there are only 9383 reducible memberships , or less than 1.2%.

(3) Moreover, according to Table 7, for 173 values of n ∈ I 1,8249 , all memberships are reducible (i. e., r = 0), in 428 cases there exists only one reducible membership, and only in 463 cases the number of reducible memberships is 6 or more. These experimental data are the motivation behind the below definitions of, and constructions associated with irreducible and strongly irreducible memberships. (Cf. Definition 11.3, (2) The choice of the alphabetical order in the above definition of strongly irreducible configuration is convinient and, probably, optimal for our goals, but not compulsory. What we need, in fact, is the characteristic function (11:10), and to define it effectively, any choice function choosing an element from every nonempty set Π (k) (n) of Collatz configurations of the oddlength k yielding n would do.. As we have already mentioned above (Experimental Evidence 5.7, Table 4, Figure 2), our calculations strongly confirm the existence conjecture for member numbers (Conjecture 19, §5). They present also a convincing circumstantial evidence in the favour of infinity Conjecture 20, §5, which, as our experimental data suggest (Experimental Evidence 11.2), cannot be explained away by the replicating mechanism of Lemma 11.1. Hence, two new infinity conjectures :

                   n = ξ(q) 6 • q 2 -(-1) a ∈ I 1,8249 , t(q) = #M n) n=ξ(q) d∈I 1,19999 = #Π n) n=ξ(q) d∈I 1,19999 , i(q) = #I n) n=ξ(q)
d∈I 1,19999 , s(q) = #S n) n=ξ(q) d∈I 1,19999 .

(11 : 15) Thus, t(q), q ∈ [1, 2750] is the number of primitive T d -cycles d ∈ I 1,19999 meeting n = ξ(q) ∈ I 1,19999 .

(3) Table 6 presents these functions, together with the difference r(q) = t(q)i(q) = and the ratio i(q) s(q) , in the interval 1 ≤ q ≤ 20. (4) As we have already mentioned above (Experimental Evidence 5.7(2)), we were able to calculate the function t(q) in a bigger interval (q ∈ [1, 20000], Figure 2) than other functions. Figures 789present, respectively, the graphs of the functions i(q), s(q), and a superposition of the graphs t(q), i(q), and s(q) on the interval q ∈ [1, 2750]. The graphic scenario of Figure 9 chosen here needs a short comment included in its caption.

(5) As Table 6 and Figure 9 show, the ratio i(q) s(q) stays around 2, and with growing q ∈ [1, 2750], actually slightly descents. Thus, for example, q = 2437, n = 7309 This means, that for any relevant n and k, there exists on the average 0 to 2 irreducible memberships n, d , d ∈ I 1,19999 , of the oddlength k. This observation suggest below Conjecture 30.

                     t(2437) = min
We start by refining the notations (11:10,12) for irreducible and strongly irreducible Collatz configurations and primitive memberships (Definition 11.4) :

Notations 11.7. For any k ≥ 1 and n ∈ D, define (cf. (8:16(4)) and (10:10)) : This classical cycle detection device, remarkable for its simplicity, has been invented by Robert W. Floyd. (Never published by the author. The standard reference is [Knuth 1969], pp. 4-7, Exercise 7. See also [Cohen 1993], §8.5.2, for an update on cycles detection methods.) :

∀k ≥ 1 ∀n ∈ D                      Π (k) = n∈D Π (k) n) , M (k) = n∈D M (k) n) , I k (n) = I(n) M (k) n) , i(n, k) = #I k (n) , S k (n) = S(n) M (k) n) , s(n, k) = #S k (n) , I k = n∈D I k (n) , S k = n∈D S k (n) .
Proposition 12. The graphic scenario of this superposition of the graphs of the functions t(q), i(q), s(q) calls for an explanation. Since on the interval q ∈ [1, 2750] the difference between the functions t(q) and i(q) is almost imperceptible, we have chosen to present t(q) as a white graph on the gray upper background.

(2) The comparison of the graphs i(q), s(q) makes almost palpable both the remarkable stability and a slow growth of the ratio i(q) s(q) . d ∈ I 1,19999 , n ∈ I 1,600•d-1 .

(12 : 4) and separately (when we were running a huge controlling check), in more than 24 • 10 9 cases within the intervals d ∈ I 1,4999 , n ∈ I 1,3000•d-1 .

(12 : 5)

To speed the search, trajectories have been traced in the increasing order of the starting number m ∈ D. Then, if the trajectory τ d (m) fell at some point behind the initial point m, n = T j d (m) < m, the search along τ d (m) was abandoned, since its continuation, the trajectory τ d (n) starting at n, has been already treated before. Every one of the thus traced trajectories either run ultimately into a primitive cycle, or descended under m, and thus, has been already traced to a cycle earlier.

We have carried out some additional controlling checks, too :

(1) In 82 cases, for all d ∈ I 2755,2999 , an independent search has been carried out, with the bigger initial interval 1 ≤ n ≤ 5000 • d. No new primitive cycles have been discovered.

(2) In one particularly interesting case, d = 343, mentioned below, the chosen initial controlling interval was 1 ≤ n ≤ 60, 000 • 343 > 2 • 10 7 . The calculations have confirmed the existence of only three primitive cycles discovered earlier.

(3) Cf. also the above examples of exhaustiveness of our experimental search : Note 5.2, Example 9.4, Comments and Experimental Evidence 10.6. (10).

Note also that the minimal members of all primitive cycles, discovered thus far, fall under the upper limit 600 • d in (12:4), with only two cases coming relatively close to this limit :

(1) d = 343; one of primitive T 343 -cycles (out of three discovered) has the minimal member (cf.

(

  IV) A Preliminary Sample of the Diophantine (3x + d) Extension. To give the reader a foretast of Diophantine version of the coming (3x + d) extension of Collatz conjecture (before its precise definition in §2), let us call a positive odd integer d not divisible by 3 a key to a Collatz number B, if B divides some members of the set d • A, with A being Collatz corona of B (since B and members of A are odd and not divisible by 3, the key can be restricted to numbers of the same type). Any Collatz number B = B k, has at least one key : for any A ∈ A k, , take d = A gcd(A,B) . Now, the other way around, is any positive odd integer d not divisible by 3 a key to some Collatz number ?

  Conjecture 7 : (NDTC) 3x+d For any d ∈ D, T d has no divergent trajectories. Or equivalently, but in the affirmative form : Conjecture 8 : (URCC) 3x+d For any d ∈ D, a T d -trajectory runs ultimately into a cycle. The existence of at least one T d -cycle being guaranteed (the cycle C o d (2:4)), the total number is conjecured to be finite : Conjecture 9 : (FCC) 3x+d For any d ∈ D, T d has only a finite number of cycles.

Conjecture 14 :

 14 Recurrence Threshold Conjecture. For any d ∈ D, there exists such a positive integer R that any T d -trajectory (2:2) enters the interval 1 ≤ m ≤ R infinitely many times. The minimal of such numbers R is denoted by R d and called the T d -recurrence threshold. Conjecture 15 : Collapse Threshold Conjecture. For any d ∈ D, there exists such a positive integer L that any T d -trajectory τ d (m) runs ultimately into the interval 1 ≤ m ≤ L, and there it remains. The minimal of such numbers L is denoted by L d and called the T d -collapse threshold. Conjecture 16 : Termination Set, or Attractor Conjecture. For any d ∈ D, there exists such a finite set U of positive integers, that any T d -trajectory τ d (m) runs ultimately into U , and there it remains. The intersection of all such sets is denoted by U d and called the T d -termination set, or T d -attractor.

  Any T d -trajectory passes by an odd number, and whatever might be m ∈ N, all other members T d (m), T 2 d (m) , . . . of a T d -trajectory τ d (m) (2:2) are not divisible by 3 :

  An odd member n of a primitive cycle belongs to D d (2:3). Conversely, a non-divergent trajectory τ d (m) starting at n ∈ D d either is a primitive cycle, or ultimately enters such a cycle.

  )] 371 , [371(2)] 371 , [721(29)] 371 . Note that 371 = 7 • 53 and that only the T 371 -cycle [25(222)] 371 is primitive. The other three cycles are 53-, 371-, and 7-multiples of, respectively, the primitive T 7 -, T 1 -, and T 53 -cycles [5(4)] 7 , [1(2)] 1 , [103(29)] 53 . Our calculations confirm Matthews assertion. We have found that each one of the systems D 7 , D 53 , and D 371 has only one primitive cycle, presented above. The following claims avout basic structural properties of the set C(d) of all T d -cycles (Definition 4.3) formalize intuitive insights gained with the above examples. These propositions do not depend on any of assumptions or conjectures concerning the dynamical systems D d . In particular, the below formulae are valid when the set C(d) is infinite. Lemma 4.6. For any d ∈ D, let C(d) and P(d be, respectively, the sets of all T d -cycles and all primitive T d -cycles, P(d ⊂ C(d) (Definition 4.3(

  1 ) (4 : 13) be the minimal, respectively, maximal member of a T d -cycle C of the length . Clearly, n o is odd and ∈ D, and m o is even. If, for a given d ∈ D, the combination (NDTC) 3x+d + (FCC) 3x+d of conjectures holds, §2, then the T d -recurrence and T d -collapse thresholds R d , L d , and the T d -attractor U d , §3, are given by the formulae :

  For all d ∈ D, 1 ≤ d ≤ 19999, denote by Pd , Cd , Ro d , Rd , Lo d , Ld , Ũd , ˜ (d), ς(d), (4 : 15)

  , respectively. On the other hand, the calculated T 1715 -recurrence and -collapse threshods are, respectively, R1715 = 886, 685 = 5 • 177337 , L1715 = 795268030 = 5 • 159053606 . Both these numbers are coming from a non-primitive T 1715 -cycle (remark that 1715 = 5 • 343), the 5-multiple of a primitive T 343 -cycle. The minimal and maximal members of this T 343 -cycle are also the T343 -recurrence and -collapse thresholds, R343 = Ro 343 = 177337 , L343 = Lo 343 = 159053606 . 5. Three Basic Primitive Cycles Conjectures. But do primitive cycles exist in all systems D d ? And what are the chances of an integer n ∈ D (cf. Lemma 4.2(1), Corollary 4.4(

Conjecture 17 :

 17 Existence of a Primitive T d -cycle. For any d ∈ D, there exists at least one primitive T d -cycle (cf. (4:8)) : ∀d ∈ D , (d) ≥ 1.

Conjecture 19 :

 19 Any Suitable Integer Is a Member of at Least One Primitive T d -cycle. For any n ∈ D, there exists at least one d ∈ D with a primitive T d -cycle meeting n. Or, in other words, the the set of odd members of all primitive T d -cycles covers the set D of odd positive integers not divisible by 3 (cf. the notations (4:4)) : d∈D C∈P(d Set(C) = D . (5 : 3) Conjecture 20 : Any Suitable Integer Is, in Fact, a Member of an Infinite Number of Primitive T d -cycles.

  below) show, the prolifiration of primitive cycles with the same values of length and oddlength does not account for the actual abundance of recurring memberships of a given number n ∈ D in primitive cycles, §11. Note 5.2 : Cogency of Experimental Confirmation. (1) The experimental search for primitive T d -cycles, for 6667 systems D d , within the range 1 ≤ d ≤ 19999, confirm Conjectures 17-20, albeit, inevitably, with different degrees of certainty.

  (d) : D -→ N is an onto mapping ⇐⇒ ∀r ∈ N ∃d ∈ D , (d) = r. (5 : 10) (2) For any D ∈ D and any sufficiently big E ∈ D, E D, the distribution function δ D,E (r) (5:9) attains its maximal values for r = 1 and/or 2, and exponentially descends with r ≥ 2 growing.

  Figure 1 displays two distributions δ of numbers ˜ (d) of primitive T d -cycles, as well as the logariphms υ = log(δ) of these distributions. The first distribution (cf. Figure 1(A) and, for its logarithm, Figure 1(C)) describes all 6667 systems experimentally studied in this paper, 1 ≤ d ≤ 19999. The second one deals with the portion of 1333 systems correponding to the (arbitrary chosen) interval 12001 ≤ d ≤ 15997 (Figure 1(B,D)).

  ∀r (1 ≤ r ≤ 120) , δ = δ 1,19999 (r), υ = ln(δ 1,19999 (r)) ; δ = δ 8003,11999 , υ = ln(δ 8003,11999 (r)) . (5 : 11) Experimental Evidence 5.7 : Conjecture 19. (1) The conjecture has been strongly confirmed for all n ∈ D, 1 ≤ n ≤ 59999 (altogether, 20000 values) in the band d ∈ I 1,19999 .

Figure 1 .

 1 Figure 1. The distributions of numbers of primitive cycles (see Experimental Evidence 5.6 for explanations). Note that systems with 1 to 2 cycles predominate.

  On the other hand, the set M(d of all memberships with a fixed second component (or, shift number) d can be identified with the set of members of all T d -cycles (cf. the notations (4:4)) : ∀d ∈ D , M(d = C∈P(d Set(C) .

  If < k • log 2 3, then the set M (k) is empty.(2) For any d ∈ D, the sets M(d , P(d are simultaneously either empty, finite, or infinite, with their cardinalities µ(d and (d) (4:8) related by the following formula (cf. the notations (4:4)) :                 ∀d ∈ D , M(d = ζ -1 (P(d ) = ≤ µ(d ≤ (d) • max C∈P(d oddlength(C) .

  See below Theorem 8.3(1). (2) Straightforward verification. End of the Proof.Assuming (d) and µ(d are finite, the second numerical characteristics of dynamical systems D d , as our calculations show, is less volatile and, on the average, steadily growing one : cf. Figures3,4. Now, the three basic conjectures of §5 can be summed up, as follows :Conjecture 22. (1) All sets M n) are infinite.(2) On the other hand, all sets M(d are non-empty and finite :

  If, for a given d ∈ D, the system D d has no divergent trajectories and if, according to the conjecture (6:7), µ(d = #M(d < ∞, then M(d is the T d -attractor of D d (cf. Conjecture 16, §3, and formula (4:14)) :U d = M(d .(6 : 8)Diophantine insights of the next chapter will shed new light on this disparate duality between the member-number-and shift-number-projections.Chapter III. Cyclic Diophantine Formalism.

Figure 3 .

 3 Figure 3. The graph of the function ξ(t) , (d) being the number of primitive cycles, with d = ξ(t) ranging from 1 to 19999 over D (2:3) when 1 ≤ t ≤ 6667.

Figure 4 .

 4 Figure 4. The graph of the function µ(d majorizing the function (d) (6:6).

  The numbers A ∈ A k, , σ(A), and B = B k, are related by the formulae :

  (8 : 15) Proof of Corollary 8.4 : Only the claim (4) needs a hint of a proof (by induction). According to the above claim (3), Conjectures 18, 23 are equivalent in the case of a prime shift number d = 5, 7, 11, . . .. Let now d ∈ D, d ≥ 5 be composite, and suppose there exists an infinite set of triples k, , A k, , with (k, ) ∈ Λ, A k, ∈ A k, , satisfying the congruence (8:10). Then, for any such triplet, the pairn k, = A k, gcd(A k, , B k, ) , d k, = B k, gcd(A k, , B k, ),definedaccording to (8:13), is a primitive membership, with d k, < d being a divisor of d. The number of divisors of d being finite, at least one of those divisors < d should be the shift number for an infinite number of primitive memberships (cf. also Corollary 4.7(10), (4:10-12)). Contradicts the inductive assumption clause. End of the Proof. Example 8.5. (1) The shift number d = 6487 = 13 • 499 has the representation 6487 = 2 16 -3 10 . Thus, any combination of parameters p 1 , . . . , p 10 , such that p 1 + . . . + p 10 = 16 > 10 • log 2 3 = 15.8496 , gcd a(p 1 , . . . , p 10 ), 6487 = 1 , is a solution of the equation d = g(p 1 , . . . , p 10 ) = B 10,16 gcd(a(p 1 , . . . , p 10 ), B 10,16 )

2

  82 -3 10 = 4 835 703 278 458 516 698 765 655 = 5 • 827 • 3 557 • 6 793 • 91 009 • 531 807 317.

  (6:7(2 right))) : Conjecture 26. For any d ∈ D, there exists an upper bound L(d) ≥ 2 to the lengths of primitive T d -memberships and cycles : ∀d ∈ D ∃L = L(d) ≥ 2 ∀ > L , µ (d = (d) = 0. (10 : 3) Lemma 10.2. Conjecture 26 is equivalent to Conjectures 18, 22(2) (6:7(2 right)), 24. Proof : (1) If (d) < µ(d < ∞ (Conjectures 18, 22(2) (6:7(2 right))), then only finite number of summands in the following sums can be positive, -which is equivalent to (10According to Corollary 10.1, all summands in two sums of (10:4) are finite. If, starting with some = L(d)+1 (Conjecture 26), they are equal to zero, then the parameters (d), µ(d are finite. End of the Proof. Problem 10.3. (1) How small can be the minimal length of a primitive T d -membership or cycle? (2) How big can be its maximal length ? Definition 10.4. (1) Assuming Conjectures 17 and 18, §5, i. e. (cf. (6:5,6(2))), 1 ≤ (d) < µ(d < ∞ , define, for any d ∈ D, its upper and lower length limits, (d) and (d), as follows : ∀d ∈ D , (d) = max{ ≥ 2 µ (d = 0} , (d) = min{ ≥ 2 µ (d = 0} . (10 : 5)

Figure 5 .

 5 Figure 5. The graphs of the functions (10:6) L(d) (black) and L(d) (gray) superimposed. Points (11), (16), (17) have the parameters , d as given in the corresponding columns of Table6.

  Only three out of 16 systems D d , presented in Table

Figure 6 .

 6 Figure 6. The graph of the functions w(λ) (10:11) and log(w). Thus, there are 3224 primitive (k, )-cycles with the zero margin λ =k • log 2 3 = 0 (7:1), out of the total number of 42765 primitive T d -cycles calculated here. The sets D, D ⊂ D (which, according to Lemma 10.5, are infinite) have density 0 (note that the set D is of the density 1 3 ). (2) The set D = D ∩ D is infinite and has relative density 1 in both sets D and D. (3) The set D ⊂ D of shift numbers d with a single primitive cycle, (d) = 1, is infinite and has relative density 1 in D.(4) The upper and lower length limit threshod functions L and L satisfy the following inequalities, with some "relatively small" constants c 1 , c 2 , c 3 , c 4 :

  10 : 18) It is clear that n ≤ N (d, k) and that the same upper bound holds for the number of different primitive T dmembership of the oddlength k :µ (k) (d ≤ N (d, k) .(10 : 19)

  N × I D,D . (11 : 7) (Cf. also Experimental Evidence 5.7 and Table 4, §5.) We remind the definition (2:3) of the function n = ξ(q) = 6 • q 2 -(-1) q and the definition (6:1) of the set ∆ : ∆ = {(n, d) ∈ D 2 | gcd(n, d) = 1}. See also the definition (5:4) of an interval I Q,R ⊂ D.

  below.) Definition 11.3. (1) To simplify and make uniform our notations, we define the empty 0-tuple of positive integers, N 0 = and extend to it the definition (7:4) of the norm . . .: n) = S(n) M (k) n) , s(n, k) = #S k (n) = 0 , if M (k) (n) = ∅ , 1, otherwise .(11 : 10) Note 11.5. (1) The above defintions (5, 6) of the ≺ -order and of strong irreducibility imply :∀k ≥ 1 ∀P ∈ N k ∀p ∈ N , p < P k , P = P k , p ≺ P .(11 : 11) Thus, a strongly irreducible Collatz configuration is irreducible, and the following inclusions hold :∀n ∈ D , Π(n) = ∅ =⇒ S(n) ⊆ I(n) ⊂ Π n) .(11 : 12)

Conjecture 28 .

 28 For any n ∈ D, there exists an infinite number of irreducible memberships n, d , or in other words (cf. the inclusion (11:12)),∀n ∈ D , #I(n) = #Π n) = ∞ .(11 : 13) Conjecture 29. For any n ∈ D, there exists an infinite number of strongly irreducible memberships n, d , or in other words (cf. the inclusion (11:12)),∀n ∈ D , #S(n) = #I(n) = #Π n) = ∞ .(11 : 14) Experimental Evidence 11.6. (1) We do not know the values of the parameters #S(n), #I(n), and #Π n) (this last one, according to Conjecture 20, is infinite), but we are able to calculate and compare the experimental lower bounds to these functions in the rectangle R 1,8249 1,19999 (11:7), for 2750 values of the member number n.(2) Namely, define, similarly to the notations (2:3), (5:14), ∀q ∈[1, 2750]

Figure 7 .

 7 Figure7. The graph of the function i(q), 1 ≤ q ≤ 2750, i(2437) = 133 ≤ i(q) ≤ 435 = i(196). Thus, for example, n = ξ(1) = 1 and n = ξ(196) = 1187 (2:3), Experimental Evidence 11.2(1), are the member numbers of, respectively, 434 and 435 irreducible primitive memberships. These two values are maximal ones for the numbers of irreducible memberships in the rectangle R 1,8249 1,19999 (11:7).

  Figure 9. (1)The graphic scenario of this superposition of the graphs of the functions t(q), i(q), s(q) calls for an explanation. Since on the interval q ∈ [1, 2750] the difference between the functions t(q) and i(q) is almost imperceptible, we have chosen to present t(q) as a white graph on the gray upper background.(2) The comparison of the graphs i(q), s(q) makes almost palpable both the remarkable stability and a slow growth of the ratio i(q) s(q) .

  (10:3)) n o = 177, 337; 517 • 343 < n o < 518 • 343 < 600 • 343 (and the maximal member m o = 159, 053, 606). (2) d = 551; one of primitive T 551 -cycles (out of ten) has the minimal member n o = 212, 665; 385 • 551 < n o < 386 • 551 < 600 • 551 (with m o = 8, 332, 648).

  Conjecture 12 : (DFCC) 3x+1 For any d ∈ D, the total number of Collatz numbers satisfying (2:7) is finite. Our computations show that even for relatively small values of the shift number d ∈ D, some T d -cycles are very long, with the corresponding Collatz number B and its counterpart A from Collatz corona of B rather big. The biggest found in this study Collatz number corresponds to a T 16819cycle of the length 4686 (see below Table 5, §10) :

	Example 2.4. B = B 2292,4686 = 2 4686 -3 2292 > 10 1409 and B divides 16819 • A	(2 : 8)

1 Table 2 .

 12 Eleven systems D d with the numbers of primitive cycles bigger than 160.

	d	7463 18359 7727 15655 10289 9823 17021 14197 13085 6487 14303
	˜ (d)	162	164	198	207	214	241	258	329	335	534	944
	These data strongly suggest the following new conjectures :
	Conjecture 21. (1) The number of primitive cycles attains all positive integer values :

Table 3 .

 3 The number δ1,19999 (P ) of systems D d with exactly P, 1 ≤ P ≤ 160, experimentally found primitive T d -cycles. On the intersection of i-th row (1 ≤ i ≤ 16) and j-th column (1 ≤ j ≤ 10) is the number of systems with P = j + 10 • (i -1) primitive cycles.

		j = 1	2	3	4	5	6	7	8	9	10
	i=1	1481	1507	1005	605	392	259	216	172	121	121
	2	87	72	45	53	48	42	35	19	30	24
	3	25	20	17	19	13	16	11	8	13	11
	4	5	7	7	8	3	3	8	6	2
	5	2	5	3	3	3	2	4	0	1

Table 5 .

 5 17 biggest values of lengths = (d) of primitive T d -cycles, d ∈ I 1,19999 (5:6), with shift numbers d, oddlengths k, margins λ k, (7:12), numbers (d) of primitive T d -cycles, decimal exponents log 10 B of their Collatz numbers ( e. g., B 982,1942 ≈ 10 448 ), and the minimal odd member n 0 .

		1	2	3	4	5	6	7
	(d)	1942	1954	1956	1966	2004	2014	2088
	k	982	978	972	947	1024	1010	1044
	λ k,	385	403	415	465	380	413	433
	d	14123	13187	13291	14627	16409	15683	15661
	(d)	3	1	1	1	1	1	1
	log 10 B 448	587	587	590	602	605	627
	n 0	37	17	5	19	119	11	103
		9	10	11	12	13	14	15	17
	(d)	2155	2242	2254	2270	2588	2604	3918	4686
	k	1092	1146	1136	1166	1304	1356	1954	2292
	λ k,	424	425	453	421	521	454	820	1053
	d	14303	10531	8431	13495	15563	16381	13829	16819
	(d)	944	1	1	1	1	2	1	1
	log 10 B 647	673	677	682	778	782	1178	1410
	n 0	101	25	23	143	83	23	13	7

  Table 4, and Figure 2, §5, above and Table 6, Figures 7-9 below), the replicating mechanism of Lemma 11.1 accounts only for a tiny fraction of primitive memberships with a given member number n.The below analysis (Definition 11.2, Lemma 11.3) of Lagarias' construction and of our experimental data leads to the notions of irreducible and strongly irreducible Collatz configurations, and, as the result, to two new infinity conjectures. Conjecture 28 strengthens Conjecture 20 by asserting the existence of infinitely many irreducible configurations yielding n. Conjecture 29 further strenghtens Conjecture 20, by claiming the same property for strongly irreducible configurations yielding n.

(2) To evaluate from above N (d, k), we slightly modify the definition (10:18), evaluating separately d • A B k, , first, for a marginal Collatz number B k, k•log 2 3 , and then for all other Collatz numbers B k, , > k • log 2 3 :

(10 : 20)

Note that, since "sup" of the second line of (10:20) is defined on the finit set A k, k•log 2 3 , it is replaced here by "max".

(3) According to (7:7,9),

The trivial lower bound B k, ≥ 1 (in other words, 2 = 3 k , for any (k, ) ∈ N) gives us : (10 : 22) On the other hand, for any > k

(10 : 23) Hence,

(10 : 24)

(4) The trivial lower bound B ≥ 1 for marginal Collatz numbers can be improved. According to [Rhin 1987], whose techniques lacks the generality of Baker's method (cf. [Baker, Wüstholz 1993] and the references there), but is more effective in the evaluation of linear forms of several specific logarithms, including the case p + q log 2 + log 3 (cf. (7:13) for the definition of k ) :

(10 : 25)

Lemma 11.1 (1) For any odd positive integer r > 1, there exists such a minimal integer exponent m = m(r) ≥ 2, a divisor of Euler function φ(r), that 2 r ≡ 1 (mod r) and, for any integer t ≥ 1, if 2 t ≡ 1 (mod r), then t ≡ 0 (mod r) :

(11 : 3)

We remind that Euler function φ(r) is defined as the number of different divisors of r.

(2) For any Collatz configuration P corresponding to the primitive membership γ(P) = n, d (8:6,16), (11 : 4) the below Collatz configuration P , corresponds to the primitive membership γ(P ) = n, d with the same member number, as follows :

(1) P = p 1 , . . . , p k-1 , p k + t , t = q • m(a(P)) , q ≥ 1 ;

(2) = + t ;

(3) a(P ) = a(P) , (cf. Lemma 7.2 (7 : 10)) ;

(4)

(5) gcd a(P ), B k, = gcd(a(P), B k, ) ;

(11 : 5)

(3) Moreover, for sufficiently large q, Collatz configurations (11:5) are lowermost, Definition 8.2, i. e., n is the minimal odd member of the corresponding primitive cycle.

Proof : (1) This is an elementary number theoretical fact : see, e. g., [Nathanson 2000].

(2) The statement (11:5) claims, rather implicitly, that if (11:5) is a Collatz configuration, then it yields n as the member number.

The last claim can be instantly verified, according to (11:5). Now, for a k-tuple of positive integers, P ∈ N (11:5), to be a Collatz configuration, two conditions need to be met : the inequality (7:4), P > k • log 2 3, and the aperiodicity. P being a Collatz configuration, P > k • log 2 3, we have :

As to the aperiodicity of P , it is obviously assured for all but, possibly, one value of q; for example, the 6-tuple 1, 1, 4, 1, 1, 2 is marginal Collatz (6, 10)-configuration, and all 6-tuples 1, 1, 4, 1, 1, 2 + t , t ≥ 1, but the periodic one, 1, 1, 4, 1, 1, 4 , are Collatz configurations, too.

In other words, there exists at most one q ≥ 1, such that the corresponding k-tuple P is periodic and equal to the exponent vector Even(C) (4:4) of a nonprimitive cycle C meeting n. This exceptional case has been, in fact, implicitly excluded from the claim (2), which concerns only Collatz configurations of the form (11:5).

(3) If k = 1, the claim is trivially true : the only odd member of a primitive cycle is always the lowermost (Lemma 4.2(2)). Consider now the following decomposition formulae for the functions a(P) = a k (P),

(2) a k σ j (P) = 3 j • a k-j (p j+1 , . . . , p k )+ 2 p j+1 +...+p k • a j (p 1 , . . . , p j ) .

(3

(11 : 6)

Applying now these formulae to Collatz configurations P = p 1 , . . . , p k + t , = + t, and σ j (P ), we find that, for all t ≥ 1, a k (P ) = a k (P) = A (the function a k does not depend on the coordinate p k (7:4)), but, according to (11:6(4)), for t sufficiently big,

End of the Proof. (As we argue in §12, this is the exhaustive list of primitive memberships in the above interval of shift number values.) Figure 2 renders the graph of the distribution, according to the value of the member number n, t(q) = ˜ (n n=ξ(q) ) 19999 1

Experimental

(11 : 8)

(2) The trivial decomposition

can be interpreted both as a breaking a given k-tuple into its (k -1)-component prequel and 1-component sequel, and as an assembling this k-tuple from given prequel and sequel. Hence, the two following dual notations :

(1)

(2) ∀j ≥ 0 ∀P = (p 1 , . . . , p k ) ∈ N j ∀p ∈ N ,

(11 : 9)

(3) For any k ∈ N and n ∈ D, let Π (k) n) be the set of all Collatz configurations P of the oddlength k yielding n = f (P). A Collatz configuration P ∈ Π (k) n) is called irreducible if, for any p ∈ N, p < p k = P k , the k-tuple P = P k , p is either not Collatz configuration, P ∈ Π, or it yields a member number n different from n, P ∈ Π (k) n).

(4) A membership n, d is called irreducible, if the corresponding Collatz configuration P = θ n, d (8:6) is irreducible. We denote by I(n) ⊂ M n) (8:16(1)) the set of all irreducible primitive memberships with the member number equal to n.

(5) Let ≺ denotes the alphabetical order on the set N k of k-tuples of positive integers (in this order, for example, 1, 1, 3, 1, 1, 3

(6) A membership n, d is called strongly irreducible, if the corresponding Collatz configuration P = θ n, d is strongly irreducible. For any n ∈ D, we denote by S(n) ⊂ M n) the set of all strongly irreducible primitive memberships with the member number equal to n. By definition, any two elements of S(n) have different oddlengths (cf. the notations (8:16(1,4)) :

Note that, according to Definition 11.4, (11 : 17) The following hypthesis is suggested by the above distribution of ratios i(q) s(q) (Table 6 and Figure 9) and is dual to the claim of Theorem 10.8 : as the sets M (k) (d are finite, for all k ≥ 1, d ∈ D, so should be the sets of irreducible memberships over n of the given oddlength, I k (n) (note that the sets of all memberships M (k) n) are infinite, due to the replicating mechanism of Lemma 11.1) :

Conjecture 30. For any k ≥ 1 and any n ∈ D, the set

Chapter V. Calculating Primitive Cycles.

12. Searching Algorithm.

The motor of our experimental enterprise is an algorithm searching for primitive cycles. It is powered by the iterative procedure implicit in the following "primitive" version of the ultimately-running-into-a-cycle conjecture, (URCC) 3x+d (Conjecture 8, §2), as implied by Corollary 5. Working Assumption 12.1. For any u, v ∈ D, such that gcd(u, v) = 1, the following algorithm halts :

(12 : 1)

The algorithm (12:1) computes at the j-th step the iterations T j d (n) and T 2j d (n), and then compares them. See Proposition 12.2 below for a proof that the non-primitive version A cyclic 3x+d , (2:6), of this algorithm detects all T d -cycles. f j (m) = f 2j (m) , (12 : 3)

Proof :

(1) The if (or sufficiency) condition (12:3) is obvious.

(2) The only if (or necessary) condition. Suppose τ (m) runs at the point s = f z (m), z ≥ 1, into a cycle of the length w, so that, for any x ≥ 0, f z+x (n) = f z+x+w (m).

Assuming t = z + x, the condition (12:2) will be satisfied if, for some positive integers x, y ≥ 1, the equality holds : 2t = 2(z + x) = z + x + y • w = t + y • w.

The choice y = z w and x = y • wz would do. End of Proof. The above Working Assumption has been verified in more than 75,000,000 cases within the intervals (cf. the notations (5:4-6))