u/jonseymourau

In a previous post I described a regex that could match Steiner circuits. That notation was:

(7*3)?(1|5)

With any odd Collatz path being a repetition of that basic pattern.

Here is a notation that captures the same thing, using an exponential notation that captures the precise identity of the Steiner circuit in its exponents.

7^{α-2}3^{α-1}1^{2-β}5^{β-1} 

where:

α = o
β = e-o

{ n^k } means k repeats of n, k >0
{ n^k } means {} when k <= 0

The cool thing about this is that it encodes the mod 8 character of each element of the Steiner circuit.

So:

OEE -> 1
OEOEE-> 31
OEEE -> 5
OEEEE -> 5^2
OEOEOEE -> 731

My claim is that you can describe a Collatz graph entirely where the (interesting*) nodes of in-degree 2 are 5 mod 8 and edges are strings of Steiner circuits expressed with this notation. This is the overlay graph described previously. The leaves of this graph are all 0 mod 3. If you delete the (1,1) edge and the Collatz conjecture is true, then the graph is a tree. If the Collatz conjecture is false the graph has multple disconnected components.

By interesting*, I mean fully recursive. Other nodes have branches, but one of them leads immediately to an 5 mod 8 node and the other leaves straight to a 0 mod 3 - extended recursion of the (reverse) walk in the Collatz graph only happens via 5 mod 8 nodes.

I am preparing a paper that describes this more fully, but that's the basic idea.

I have referenced this paper from a previous post, but since the paper now folds in insights from two of my recent posts, I think it is worthy of its own post.

The key result is the recognition that n mod 5 nodes allow the construction of an overlay tree over the reverse Collatz tree where there interior nodes consists only of n mod 5 nodes that the "left" branches contain a forward path from a mutliple of 3 to the n mod 5 node that is OEEE+-free (e.g. does not contain n mod 5 node except at the end).

This structure allows one to make this strong (but presently unproven) claim about any pair. of nodes along the left branch:

e >= o. log_2(3) <=> a >= b

This is possible PRECISELY because such branches do not have 5 mod 8 nodes.

What remains unproven (though almost certainly is true) is that each 5 mod 8 reaches a 0 mod 3 node via its left branch.

update: I have had to withdraw most (but not all) of the theorems in the paper because I realised the proofs didn't stack up. I have replaced the theorems with conjectures and left some implication theorems that trace out the logical implication framework should the conjectures eventually be shown to be true. I would welcome any counter examples for conjectures/postulates as currently posed.

I think this is true:

This regex:

(((7*3)?(1|5)))*

Matches the n mod 8 representation of all "complete" odd Collatz orbits. (An orbit is "complete" if the last term is the last odd term of a Steiner circuit - that is, it ends with either a 1 or a 5)

For example, if you consider all the odd numbers in the sequence from 27 to 1 and calculate n mod 8 for each value, then you get this sequence:

317773113173177315731317777357735115573551

That sequence is matched by the regex above.

Some notes:

- each repetition of the outer group is a complete Steiner circuit
- a string of 7's is always followed by a 3 (these correspond to the leading OE terms of a Steiner circuit)
- a 7 is always followed by a 7 or 3
- a 3 is always followed by a 1 or 5
- a 1 corresponds to an OEE term
- 1 or 5 can be followed by any other term
- a 5 corresponds to an OEEE+ term where EEE+ is at least 3 even terms
- 7 and 5 have symmetrical roles - 7's permit arbitrary number of leading OE terms in each Steiner circuit, 5's permit arbitrary number of trailing E terms in each Steiner circuit.
- 3 identifies the last OEO term in a Steiner circuit.

All of this, of course, is a consequence of action of the Collatz map on the mod 8 arithmetic of sequence elements.

Another property of this representation that relates to the recent discussions in this place about the frequency of paths that pass through 5.

All odd terms between 2 5's have the same 3.k leaf - that is, if you take closest reverse branch for each of these terms, then it is guaranteed that each 3,k leaf will be the same - the 3k leaf changes at each 5 term.

What this means is that the reverse path between a node and 0 mod 3 leaf node can be represented as an unbalanced tree where the left branch is a 3k-leaf node and the right branch is another tree of the same structure.

1
|
5
/ \
3 53
/ \
15 61
/ \
81 325
/ \
303 3077
/ \
159 2429
/ \
111 445
/
27

I've written this up in a paper

update: corrected * -> ? per comments below paper will be corrected in due course.

In a previous post I described an algorithm that would generate the Twin Primes without an explicit primality test.

In this post, I present an even simpler algorithm which does use a primality test but fundamentally relies on another unproved conjecture about Twin Primes - a so-called bridging conjecture.

The bridging conjecture (BC) discussed here is:

For every positive integer V, there exist u, v, w in A002822 with u <= v <= V < w and u + v = w.

So, the algorithm here will not stop iff the bridging conjecture (and hence, TPC) is true.

It could be that the bridging conjecture if false, and the Twin Primes Conjecture (TPC) is true. In this case the algorithm will stop, even though the TPC is true.

This algorithm could also stop and the TPC is false for other reasons.

However, if the algorithm never stops, then TPC must be true.

Empirically, it appears the algorithm never stops. This is not proof of TPC - far from it - but it does indicate that there are good, empirical, reasons for believing the bridging conjecture is true.

Of course, proving that the algorithm never stops is not a trivial problem!

The surprising thing about the algorithm is that it is entirely based on the sumset of A002822. It is trivial to generate all twin primes if you iterate over N and apply a prime sieve . But this algorithm IS NOT iterating over N. Rather, it is iterating only over the already discovered subset of A002822 (e.g. W) and generating the sumset of that subset. Yet, it apparently manages to discover all the twin prime witnesses.

This algorithm and the related bridging conjecture are completely inspired by Harvey Dubner's middle number conjecture which states that "every middle number (of a twin prime pair) is the sum of two other middle numbers". I was clued into this conjecture by this reddit post, so h/t to u/Heavy-Sympathy5330 for drawing my attention to that.

The bridging conjecture (BC) riffs on Dubner's conjecture. If it is true, then it is trivially true that TPC is also true. However, TPC => BC iff Dubner's middle number conjecture (MNC) is true.

Suffice to say, all of BC, TPC and MNC remain conjectures.

I have some papers which explore these ideas further, but since my karma in this place is relatively low it is almost certainly true that this post will be blocked if I attempt to directly link to them [ based on hard-core, absolutely empirical experience ] so I am not going to do that (other than to the extent that I have!). (I can post links in a comment or amend the post body if/when it achieves sufficient upvotes).

import heap
from sympy import isprime

class TwinPrimesGenerator:
    def __init__(self, seed_witnesses):
        self.q = list(seed_witnesses)
        heapq.heapify(self.q)
        self.W = set()

    def twin_primes(self):
        yield 3
        while self.q:
            v = heapq.heappop(self.q)

            # emission gate: skip if already processed
            if v in self.W:
                continue

            # emit twin prime components separately
            yield 6 * v - 1
            yield 6 * v + 1

            self.W.add(v)

            # expand using current v
            for u in self.W:
                w = u + v
                if isprime(6 * w - 1) and isprime(6 * w + 1):
                    heapq.heappush(self.q, w)


[ 
    tp for i, tp in zip(
        range(0,100),
        TwinPrimesGenerator({1}).twin_primes()
    ) 
]

This algorithm enumerates the twin-primes without performing explicit primality tests.

A twin-prime witness is an integer w such that both 6w−1 and 6w+1 are both prime.

A characterization discussed in OEIS A002822 and in work of Francesca Balestrieri is that w is a twin-prime witness if and only if it cannot be expressed in any of the forms

• 6ab+a+b
• 6ab+a−b
• 6ab−a+b
• 6ab−a−b

The algorithm systematically enumerates all values of the form 6ab±a±b. It maintains a priority queue of such values and emits the integers that are not covered. These uncovered integers are precisely the twin-prime witnesses, from which the corresponding twin-prime pairs 6w−1,6w+1 are produced.

import heapq                                                                                                                                                                              
   
class TwinPrimeWalk:
    def __init__(self):
        pass

    def encode_sigma(self, c, d, sigma_c, sigma_d):
        n = c * d
        f = 6*n+sigma_c*c+sigma_d*d
        t = (sigma_c+1)//2+sigma_d+1
        return (f, -n, c, d, t)
        
    def encode(self, c,d, t):
        return self.encode_sigma(c,d, (t%2)*2-1, (t//2)*2-1)

    def twin_primes(self):
        yield 3

        q = []
        w = 0
        last_sqn=1
        heapq.heappush(q, self.encode(1,1,0))
        while len(q) > 0:
            r = heapq.heappop(q)
            f, _n, c, d, t = r
            n=-_n

            for ww in range(w+1, f):
                yield(6*ww-1)
                yield(6*ww+1)
            w = f    

            if t == 0:
                heapq.heappush(q, self.encode(c, d, 1))
                heapq.heappush(q, self.encode(c, d, 2))
                heapq.heappush(q, self.encode(c, d, 3))
                heapq.heappush(q, self.encode(c, d+1, 0))
            
            while n > last_sqn**2:
                sqn = last_sqn+1
                heapq.heappush(q, self.encode(sqn, sqn, 0))
                last_sqn = sqn

[ w for i, w in zip(range(0, 100), TwinPrimeWalk().twin_primes()) ]

[1] OEIS A002822 - the OEIS sequence that is the set of witnesses of twin primes
[2] F. Balestrieri, An Equivalent Problem To The Twin Prime Conjecture, arXiv:1106.6050v1 [math.GM], 2011.
[3] J. Seymour, "The Sieve of Balestrieri", a visualisation
[4] Suzuki, M. (2000). Alternative formulations of the twin prime problem. The American Mathematical Monthly, 107(1), 55-56. (h/t u/davidjohnpaul for finding this)

Does anyone know of a gx+1, x/h system where g=h^c-1 for c>1 that admits something other than a trivial cycle?

For example with g=3, h=2 we have x={1,4,2}.

For g=7,h=2 we have {1,8,4,2}

For g=8,h=3 we have {1.9,3}

For g=15,h=4 we have {1,16,4}

Does anyone know if any of these systems has a non-trivial cycle?

—-

Of course the motivation for this question is that if there are no counter examples for g=h^c-1, then explaining why this is so would be sufficient to show why 3x+1 has no counter examples and would at least address the no-cycles arm of the conjecture.

If there are counter examples, then so be it.