A distinct proof and extension of the Collatz conjecture

A distinct proof and extension of the Collatz conjecture Mikhail Bokiy 25.09.2025, 31.10.2025 Abstract. A proof by contradiction of the Collatz conjecture is presented based on the constructive-topological approach using the geometric mean properties of the network structures generated by the 3n+1 algorithm. The key contradiction was revealed by the method of “constructive induction” and is related to restrictions on the divisibility of the rootless subnet. The logic of the proof is transferable to other cases, which made it possible to formulate and detail the extension of the Collatz conjecture to the entire class of similar algorithms. Contents 1. Introduction 2. Geometric mean properties 3. Proof technique 4. Logic of the proof 5. Extension of the Collatz conjecture 6. Conclusion 1. Introduction This article continues the approach to the Collatz conjecture proposed previously [1]. It's time to explore the last problematic question: why does this algorithm never diverge? The third article in the series will be devoted to the systematics of Collatz-type algorithms. Summary of the first article. It was shown that the original Collatz 3n+1 algorithm (as well as analogues of the form an±b) implicitly defines a certain network. This is a holistic object, more comprehended than the set of all numerical sequences or even the Collatz graph. The network is most naturally visualized as a Table of expansions of natural numbers in powers of 2 with labeling by keys and pointers. As a consequence, the network is initially complete and only its structure determines the behavior of the corresponding algorithm. The convergence of any Collatz-type algorithm is guaranteed in the case of a simply connected network with a single root. Threats to single-connectivity include extra roots and cycles, as well as network decay with the appearance of rootless fragments. An effective toolkit has been proposed for detecting all roots and cycles of various types. Except for trivial 1-cycles, the remaining cycles are random and are searched for as integer solutions to a limited set of simple systems of linear equations. The question of excluding potential network decay, externally manifested by divergent sequences, remains open. As one of the AI agent noted, the article reconceptualized the 3n+1 problem. For the sake of consistency between articles, we will adhere to the definitions and designations already used earlier [1]. The definition of the Collatz algorithm for positive integers is standard: 3n+1 if n is odd and n/2 if n is even. The original algorithm is considered descending reverse, its mnemonic notation is “3n+1/2” (a 1 reminder of the order of operations) or shorter “3n+1”. The ascending direct algorithm is denoted “2n−1/3” (the same operations in reverse). For other Collatztype algorithms, for example, “5n−1”, respectively. The Table with keys and pointers (see Fig. 1) refers to a table of expansions of natural numbers in powers of 2 with “keys” (the column of all odd numbers n) and “pointers” (even numbers of the form 3n+1 in rows). The Table helps to topologically represent and explore the network defined by the algorithm. In the case 3n+1, the network topology is a rooted tree. The root is the key (one odd number) to which the descending algorithm converges. A cycle is a set of several keys, a cyclic variant of the root. For rootless fragments, we will further use the term “rootless subnet.” For equations linking any two keys or pointers to each other, we introduce the term “network connectivity equations.” The reason we insist on our own terminology (network, keys, pointers) is that it is more adequate for the object under study. Fig. 1 If the reader needs to get to the heart of the article more quickly, it may be worth starting with Section 4. It reveals the logic of the proof, stripped of technical details, and on this ground proposes a basic criterion for extending the Collatz conjecture to the entire class of similar algorithms. 2. Geometric mean properties To approach the proof, we will need new tools. Let's look at Collatz descending algorithm as a competition between progression (action 3n+1) and regression (division by 2 while divisible). Let us take as a step of the algorithm the transition from the previous odd key n1 to the next n2. Each step will correspond to the exact values of progression a1 = (3n1+1)/n1 and regression c1 = (3n1+1)/n2 = 2p, where the power p is the actual number of divisions by 2. From separate steps, we will move on to a chain of z steps and determine the average accumulated rates of progression and regression as the geometric means of step-by-step values: Az = (n1/1 × a1a2… az)1/z and Cz = (c1c2… cz)1/z, respectively. The progression additionally takes into account the “zero step” — the ratio of the start and finish numbers of the sequence. This definition of Az is correct with respect to the single root, so for now we will confine ourselves to the case 3n+1 (another suitable algorithm is 5n−1). At the first step, A1 > C1 always, except for the trivial case of convergence in one step, when n2 = 1 and A1 = C1 = 2p. The rate of progression Az for any finite starting key n1 monotonically decreases with an 2 increase in the number of steps, in the limit tending from above to the value of the parameter a = 3. The average accumulated rate of regression Cz fluctuates following the next cz (the number of divisions is sometimes greater, sometimes less) in a certain range above 2 (this is the minimum rate). When, after z steps, the sequence 3n+1 converges from n1 to 1, the rates of progression and regression are compared and Az = Cz at some value above 3 (see Fig. 2). If the sequence diverges (which occurs in the case 5n−1 for the part n1), then the rates are never compared and Az > Cz at any step (see Fig. 3). Fig. 2 Fig. 3 Let us define a third property, comparable in meaning and magnitude to the average accumulated regression rate of the sequence defined above. This will be the “network divisibility” that turned out to be an invariant, which is the subject of the article [2]. The definition of network divisibility for Collatz-type algorithms given there is: network divisibility Δ(с) = cc/(c−1) is the limit value of the geometric mean over a series of divisors сp extracted from the pointer scheme of any algorithm of the form an+b/c after sorting the pointers in ascending order. A well-known analogue is the average divisibility by 2p over the entire series of even natural numbers 2, 4, 6, 8…, which is simply calculated through the sum of the series 2(1+1/2+1/4+1/8+…) = 22 = 4. We prefer to calculate it using the geometric mean over a series of divisors 21, 22, 21, 23…, which gives the same result in the limit. Each specific algorithm has its own pointer scheme and its own order of divisors. But, as numerical verification on different algorithms has shown, in all cases, in the limit, the divisibility of the entire network tends to the correct value Δ(c), which depends only on the base of the algorithm — the parameter c. A typical change in Δ 3 with an increase in the number of pointers taken into account is shown in Fig. 4 for the 3n+1 algorithm. This invariant has an important property — a consequence of its definition in terms of geometric means: the divisibility of the entire network Δ(c) is decomposed into the product of the divisibility of the network's constituent parts raised to powers equal to the natural densities of the constituent parts. The constituent parts can be any real or hypothetical network structures, for example, a rooted tree and a rootless subnet, then: Δ(с) = (Δroot)ωroot × (Δunroot)ωunroot = cc/(c−1), where ωroot + ωunroot = 1. Fig. 4 Two more methods of a constructive nature will be described later in the process of proving Collatz conjecture (see Section 3, Part 1 and Part 2). 3. Proof technique Let us recall the statement of the problem from the first article [1]. The Collatz algorithm has a single root 1, generated by a trivial cycle. There are no other roots or cycles. To complete the proof of convergence of the algorithm, it is necessary to confirm that the entire network 3n+1 is simply connected. In other equivalent formulations, this means: the existence and solvability of the network connectivity equations for any natural number, reachability from the root via an ascending algorithm of any natural number, the completeness of Collatz tree with respect to all natural numbers. Let's proceed by contradiction. Suppose the Collatz conjecture is false. Then the 3n+1 network is not simply connected, and in addition to the main rooted tree, there must be a separate rootless subnet. From any number belonging to it, one can move infinitely along both the ascending 2n−1/3 and descending 3n+1/2 algorithms, since there are no roots or cycles blocking further descent. Infinite descending sequences will be called rootless. The topology of a rootless subnet can be clearly imagined as an infinite “tree crown” with an unreachable root at infinity. In a rooted tree, all descending sequences end at the root. In Section 2, we determined the moment of reaching the root at some step z by the equality of the average accumulated rates of progression and regression Az = Cz. Turning to the “progression curve” (actually discrete, Figs. 2 and 3), we note that to explain the behavior of rootless sequences, due to their infinity, a part of the graph in the limit of large numbers is sufficient. Therefore, without loss of essence, we can accept that the divisibility of the network is 4, and the rate of progression is 3+. Since the rootless sequence does not converge, its marginal regression rate 4 must not exceed 3. Moreover, this requirement applies not to a single “loser,” but to the entire “collective” of sequences in the rootless subnet. To confirm the sense of obvious contradiction, we will approach this from two sides. Part 1 Let us take an arbitrary key n1 (not a multiple of 3, see Note 1) in the rootless subnet and start a primary rootless sequence from it using the 3n+1/2 algorithm. Technically, we will need sufficiently long but finite initial sections of descending sequences — let's call them chains. Since no infinite sequence converges in a rootless subnet, finite chains certainly do not. We define a sufficient chain length (n1, n2… nz+1) as follows: enough steps z so that the “progression curve” Az, constructed for the starting key n1 of a given chain, has managed to fall definitely below 4, let's say to 3.5 (see Fig. 5). Approximately (accuracy is not required in this case): Az ≈ 3.5, n11/z ≈ 1.17, z ≈ lg n1/lg 1.17 ≈ 15 lg n1, which is just about 15s steps from the start key 10s. A chain of z steps passes through the same number of pointers, so the regression rate of this chain Cz = (c1c2… cz)1/z < Az ≈ 3.5. Note 1. Keys 3, 9, 15, 21… are not part of the 3n+1 network skeleton, i.e., they do not connect other keys and do not affect convergence or divergence in any way, so during the proof, all keys of the form 6k+3 and their corresponding pointers of the form 18k+10 can be ignored. Recalculating the divisibility of the entire network Δ without these pointers does not change anything significantly; in the limit of large numbers Δ still comes out to 4+. Fig. 5 Let's begin increasing the primary chain. From the last key nz+1, using the same descending algorithm, we will construct a chain continuation of the descent. We will determine its sufficient length in the same way: y ≈ 15 lg nz+1. The regression rate of the continuation Cy = (cz+1cz+2… cy)1/y < 3.5. The branching ascending algorithm 2n−1/3 provides even more opportunities for structure growth: many new chains can be started from each of the keys (see Fig. 6 and Note 2). To begin, we select one key ň in the primary chain, which will be the terminal (at the descent) key of the first ascending chain. In this case, we cannot have a formula for calculating a sufficient number of steps x, since the starting (when descending) key ň1 of the ascending chain is not known in advance. This is a fundamental unknown due to the multiplying variety of branching options in the ascending algorithm. But for our approach, the length of the chain is not essential; its existence is sufficient. Since ascending and descending finite chains are the same entities of a reversible algorithm, ascending chains exist simply 5 because any descending ones we need can be constructed. The rate of regression (at the descent) of our first ascending chain Cx = (č1č2… čx)1/x < 3.5. Note 2. Fig. 6 depicts the schematic diagram of the primary chain growth knowingly without numbers, since the existence of a rootless subnet in the 3n+1 network is purely hypothetical, which is necessary for proof by contradiction. For the same reason, studying the behavior of rootless sequences by numerical methods is only partially possible on suitable analogues, for example, 5n−1. Fig. 6 Now we consolidate the regression rate for the entire resulting network segment according to the rules for handling geometric means: D = (Czz × Cyy × Cxx)1/(z+y+x) < 3.5. In addition to the general limitation of the regression rate, it is important that there are no repetitions in the final formula: D = (c1c2… cz × cz+1cz+2… cy × č1č2… čx)1/(z+y+x). All step-by-step regressions c1, c2… etc. are divisors of the corresponding pointers through which chains pass once from key to key. Nothing prevents us from continuing the process of structure growth using both a descending and a branching ascending algorithm, connecting all new keys achieved to the process and approaching the coverage of the entire hypothetical rootless subnet without limitation. Adding a single new chain is very similar to one step of mathematical induction (see Note 3). At the same time, decomposition into finite chains followed by consolidation preserves both decisive properties: the bound on the regression rate and the absence of repetition. Due to the non-repeating accounting of pointers, the property D constructed above is the average divisibility over the rootless subnet — an analogue of the divisibility of the entire network Δ ≈ 4 defined and calculated in Section 2. And from the remaining inequality, we conclude that the rootless subnet that violates Collatz conjecture must have an average divisibility D < 3.5, and this estimate can be tightened down to 3+ by increasing the length of the chains. Note 3. The method proposed here is somewhat similar to traditional induction, which proved to be not very applicable to the 3n+1 problem. Perhaps this is a long-known approach, and we lack mathematical erudition. But to emphasize the 6 crucial role of this type of reasoning in overcoming the fundamental nonlinearity of the object, let us refer to this method as “constructive induction.” Part 2 Next, we need to designate three types of rows in our Table for the 3n+1 algorithm (see Fig. 1): type α — the row begins with a pointer in the first position (key of the form 6k+5, example — row 5), type β — the row contains a pointer in the second position (key of the form 6k+1, example — row 1), type γ — a row without pointers, a useless type for us (key of the form 6k+3, example — row 3). Each type is obviously associated with its own series of divisors through pointers in the row: α — 21, 23, 25…; β — 22, 24, 26… and γ — empty. With that, the type α has subtypes that differ in the cyclic sequence in which child rows of the main types are generated through pointers. The proof is routine, easier with examples: row 5 — descendants γ-β-α and further in rotation, row 11 — β-α-γ…, row 17 — α-γ-β… For type β, the generation of child rows is arranged in exactly the same way: row 7 — descendants γ-β-α…, row 13 — α-γ-β…, row 19 — β-α-γ… The most obvious explanation for D < 3+ is a redistribution of “bad” pointers with the lowest divisibility 21 in favor of the rootless subnet. Such a redistribution means an increase in the share of α-rows. We will evaluate whether there are initial prerequisites for this by calculating the divisibility separately for rows α and β. Direct calculation using the pointer scheme of the 3n+1 algorithm yields values of Δα greater than 3 and Δβ less than 7. Let us justify the numerical result more analytically. The series of divisors of 2p, extracted from sorted in ascending order pointers of all α-rows, is structured as follows: each quadrupling (×4) of the number of terms in the series adds 1 divisor of the next order, which in contracted form can be described by the conditional formula (((21×4)23×4)25×4)27… The limit value of the geometric mean for such a series is amenable to calculation and gives Δα→25/3 ≈ 3.17. If we note that among all the pointers sorted in ascending order, 2/3 come from α-rows, and the remaining 1/3 come from β-rows, then the invariant property can be used to calculate Δβ: Δ(2) = (Δα)2/3 × (Δβ)1/3 = 4, hence Δβ→28/3 ≈ 6.35. Note 4. Along the way, we will present conditional formulas for the series of divisors for calculating the limit values of geometric means: for the divisibility of all β-rows Δβ — (((22×4)24×4)26×4)28…, for the divisibility of the entire network 3n+1 — (((21×2)22×2)23×2)24… Similar formulas for other Collatz-type algorithms are constructed in the same way based on patterns in the divisor series. Thus, even a “subnet” consisting of the worst-divisible α-rows (in fact, pointers to β-rows are still taken into account, only the contribution of β-rows to divisibility is excluded) cannot ensure the divisibility D < 3+, which is necessary for the existence of a rootless subnet. This argumentation will only strengthen if we move on to assessing the divisibility of a more realistic subnet. Considering that 22 > 3+, the insertion of large divisors into the series, simply by the properties of geometric means, will increase the divisibility of the subnet D above the critical value. It is impossible to avoid involving β-rows in a subnet based on any subset of α-rows for the above-mentioned reason of pointers rotation through which the child rows α and β are generated. This means that any real subnet in the case of the 3n+1 algorithm will have an average divisibility D > Δα ≈ 3.17. Finale We have come to a contradiction. On the one hand, the requirement for average divisibility over a hypothetical rootless subnet D < 3+. On the other hand, 7 divisibility over any real subnet (including rootless) D > 3.17. This means that a rootless subnet cannot exist. Consequently, the 3n+1 network is simply connected — it is one complete rooted tree with divisibility equal to the divisibility of the entire network Δ(2) = (Δroot)1 = 4. Accordingly, any number converges to the root 1, the Collatz conjecture is true. At the same time, all alternative formulations of the conjecture are proven (see Section 3). For other Collatz-type algorithms, the proof changes in Part 1, deriving to the value of the limit of the “progression curve” a+. For example, for a = 5, the requirement on average divisibility over a rootless subnet D < 5.5 up to 5+. In Part 2, the divisibility estimate depends on the specific pointer placement scheme, i.e., on the combination of both parameters a and c. But such an assessment is not always necessary. For example, for the 5n−1/2 algorithm, a contradiction with the requirement on average divisibility over the rootless subnet is excluded, since Δunroot < 4 < Δroot. 4. Logic of the proof The Collatz conjecture states that all natural numbers can be reduced to 1 by a descending algorithm 3n+1/2, which has only one root 1 and no cycles. Proof by contradiction. Suppose that Collatz conjecture is false, i.e., there exists a sequence that does not converge to 1. The ascending algorithm 2n−1/3 connects this and other non-converging sequences into an infinite rootless subnet, separate from the rooted tree to which all converging sequences belong. Let us define for any sequence the average accumulated rates of progression and regression as the geometric means of the stepwise values. In the rooted tree, all sequences converge when the rates of progression and regression at some step are compared. Since in a rootless subnet all sequences are infinite, the rate of progression, taking into account the starting point, monotonically decreases to 3+, then a bound on the rate of regression in all rootless sequences arises — in the limit no more than 3. However, the bound in individual sequences does not yield much — perhaps all this is a consequence of “mass fluctuation.” Therefore, it is worth using the bound on the rate of regression to obtain an estimate of a certain “collective” property that characterizes the rootless subnet as a whole. A suitable property turned out to be the “average divisibility of the subnet,” defined as the geometric mean of the divisors 2p over all even pointers of the rootless subnet. The nontrivial problem of transitioning to the estimation of this property is solved in Section 3 (Part 1) by a new (presumably) method, designated as “constructive induction.” Result: a hypothetical rootless subnet that violates Collatz conjecture must have divisibility D < 3+. For comparison, it is now logical to estimate the actual average divisibility over a rootless subnet in another way. This problem is solved in Section 3 (Part 2) by a method that utilizes the properties of the Table of keys and pointers. Result: the average divisibility over any real subnet (including rootless) is D > 3.17. A contradiction — two incompatible estimates of the same property — leads to the conclusion that a rootless subnet cannot exist in the case of the 3n+1 algorithm. Consequently, the network is simply connected — it is a single complete rooted tree, and therefore any natural number converges to 1, and the Collatz conjecture is true. 8 The fact that the key contradiction prohibiting a rootless subnet is possible for a < Δ(2) and excluded for a > Δ(2) allows us to accept this inequality as a convergence criterion for all algorithms of the family an+b/2. The logic of the presented proof is transferable to Collatz-type algorithms with an arbitrary base c > 2, so the heuristic convergence criterion can be generalized to the relation a < Δ(с) = cc/(c−1). The criterion found becomes even more meaningful if we supplement it with the invariant property Δ(с) = (Δroot)ωroot × (Δunroot)ωunroot. This basis is quite sufficient to formulate and detail the extension of the Collatz conjecture to the entire class of similar algorithms. 5. Extension of the Collatz conjecture First of all, it is necessary to clarify which algorithms will be classified as similar to Collatz. The algorithm can be defined on the set of all integers, but for now we will focus only on natural numbers. Naturally, the algorithm must be two-part. One of the operations must be serial division by some base c = 2, 3, 4… This allows us to select keys from the entire set of numbers, i.e., numbers that are not divisible by this base, and apply the algorithm to the Table of expansion of all natural numbers by this base: keys in the first column, the remaining numbers (products of keys and bases raised to powers) in the corresponding rows. The second operation should map the entire set of keys to pointers — a certain subset of numbers in the rows. This mapping should be one-to-one (so that both the direct and reverse algorithms exist) and monotonic. The original 3n+1/2 algorithm is just that. The possibility of extending it to ambiguous and non-monotonic mappings requires separate analysis. If we restrict ourselves to linear mappings, then algorithms of the form an+b/c (mnemonic notation for a descending algorithm) fall into the Collatz-type class, where a and c are positive integers, and b is an integer (constant, but not necessarily). Non-integer combinations of parameters a and b are possible, but let's not complicate the task. Some combinations of parameters a, b, c can give reducible and degenerate algorithms that generate uninteresting network variants. For this reason, parameters a and c must be relatively prime, but combinations with a < c−1 are excluded due to the impossibility of creating a correct algorithm. Now let's define the interrelated concepts of “root,” “cycle,” and “convergence” of an algorithm. From the point of view of a descending algorithm, roots and cycles play the same role, blocking further descent due to entering a cycle or the absence of a pointer. A trivial root and a trivial cycle are almost the same thing. Therefore, we will consider any cycles to be “cyclic roots.” This is preferable, since there is a type of root that is not related to cycles. It does not matter to us that a network with a cyclic root ceases to be flat; for us, it is just a rooted tree with an exotic root. Any root entails convergence. In this interpretation, convergence is equivalent to a number belonging to a rooted tree, and divergence is a consequence of belonging to a rootless network (subnet). Only in the case of a single root can we ask about “complete convergence” from any number to a single root, as in Collatz conjecture. But it is more correct not to mix the problems of root uniqueness and algorithm convergence. These are different phenomena: convergence is related to network divisibility, while cycles are related to rare “incidents” in the network connectivity equations. Returning to the criterion. 9