open problems: existence of counterexamples for the Collatz conjecture and the value of $ limsup_ {n to infty} dfrac { mathcal {C} (n)} { mathcal {N} (n)} $

I asked a related question before. Here I will ask the question as research and add details. In the first place, I am not sure that the problem I asked is the same / equivalent as Natural Density. If so, remember Terras' theorem.

Riho Terras (1979), On the existence of a density, Acta Arithmetica 35 (1979), 101-102. (MR 80h: 10066).

This document provides additional details about the evidence in Terras (1976) that
The set of integers that have an infinite detention time has a zero asymptotic density. The test in Terras (1976) had been criticized by Möller (1978). On an added note
As proof, the author states that the evidence of Terras (1976) is defective.

If the question I ask is really the same as Terras' theorem, then the answer is obvious: $$ lim_ {n to infty} dfrac { mathcal {C} (n)} { mathcal {N} (n)} = 1 $$

Now I want to ask my question.

Leave, $ mathcal {C} (n) $ Be a Collatz counting function. This function works like this:

Consider the exponential expansion interval: $ left (1, 2 ^ {2 ^ n}} – 1 right), n in mathbb {N}. $

The function $ mathcal {C} (n) $ count everything Collatz numbers in the interval $ left (1,2 ^ 2 2 n) – 1 right) $. Here, Collatz numbers they are odd positive integers when the function $$ mathrm {Coll (n)} = begin {cases} n / 2 & text {if} n equiv 0 pmod {2} \ 3n + 1 & text {if} n equiv 1 pmod {2}. end {cases} $$ applies to him, we definitely get the result $ 1 $. In other words, for big enough $ N $, we have $ mathrm {Coll ^ N (n)} = 1. $

It is obvious that if there is a counterexample to the Collatz Conjecture, then we have countless counterexamples. Suppose we have Finely many independent counterexamples. Or at least $ 1 $ verifiable counterexample. I define "independent verifiable counterexample" as follows:

Leave, $ X $ Y $ Y $ Be verifiable counterexamples. Verifiable counterexamples are counterexamples that we can prove, There is no such $ N $, what gives $ mathrm {Coll ^ N (X)} = 1 $ or $ mathrm {Coll ^ N (Y)} = 1. $ We work, yes and only if with odd positive integers. Independent verifiable counterexamples are counterexamples, for any $ N_1, N_2 in mathbb {N} $ we have $ mathrm {Coll ^ {N_1} (X)} neq mathrm {Coll ^ {N_2} (Y)} $. In other words, for $ X $ Y $ Y $we always have $ 2 $ Different trees / sequences.

Leave, $$ displaystyle theta_1 = liminf_ {n to infty} dfrac { mathcal {C} (n)} { mathcal {N} (n)}, qquad theta_2 = limsup_ {n to infty} dfrac { mathcal {C} (n)} { mathcal {N} (n)} $$ where $ mathcal {N} (n) $ is the number of all odd positive integers in the interval $ left (1, 2 ^ 2 2 n) – 1 right) $ Y $ theta_1 leq theta_2 $. In this case, we have $ mathcal {N} (n) = 2 ^ 2 ^ n} -1} $

It is possible to show that, $ theta_1 $ strictly greater than $ 0. $

Suppose we have finitely many verifiable independent counterexamples (at least $ 1 $ verifiable counterexample), we can say $ theta_2 $ is strictly smaller than $ 1 $ ?

Of course, this is obvious if $ X $ verifiable counterexample, there are such $ n in mathbb {N} $ we have:

$$ liminf_ {n to N} dfrac { mathcal {C} (n)} { mathcal {N} (n)} = limsup_ {n to N} dfrac { mathcal {C} ( n)} { mathcal {N} (n)} <1 $$

Does this imply, if we have finely many independent verifiable counterexamples, or at least $ 1 $ verifiable counterexample then,

$$ theta_2 = limsup_ {n to infty} dfrac { mathcal {C} (n)} { mathcal {N} (n)} <1 $$

If, as I said before, the question is exactly the same as Terras 'theorem, then is Terras' theorem completely validated?

Note: I'm sorry for English grammars.

Thank you.

vhdl – collatz conjecture in verilog

Integers and positives in 8 bits.
The Collatz conjecture says that, for any positive integer n greater than zero, if applicable
The function repeatedly:
• If n = 1, stop.
• If n is greater than one and even, divide n by 2 (n div 2).
• If n is greater than one and odd, multiply n by 3 and add 1 (3n + 1).
the process will make the number n converge to 1.
For example, if we start with n = 22, the generated sequence will be 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8,
4, 2, 1. 15 steps are required, that is, the function is applied 15 times until the stop point is reached. Yes
We start with n = 6, the sequence will be 6, 3, 10, 5, 16, 8, 4, 2, 1, and the stop point is reached in 8 steps.
The system must receive a positive 8-bit integer as input through an input called date and calculate how many steps the stop point is reached, reporting this through an output
called steps. By definition, if the number is zero, the number of steps must also be zero.
The system has a bit input, called start. The system is on hold until it starts = 1.
In this case, the system must load the value of the data entry into an internal system register and perform the
transactions on the value of that registrar. After completing the operations, the amount
of steps in step output. You should not update this output until the process is complete. Once the calculation is finished, the system stops and displays the result. The system, however, also has an entry
called reset, which resets (at any time) the entire process when reset = 1.
Present, as output, the current value of n, to verify if the Conjecture is being applied
correct The current value of n must be available through an output called tempN.

performance – Why is this "more efficient" version of a Scala Collatz solution slower than the recursion of the queue?

I implemented two versions of the collatz problem and felt an icy terror in the pit of my stomach, since an optimized solution was slower than the tail. Queue recursion is simple:

// calculate the next term in a Collatz sequence
def nextTerm(term: Long): Long = 
  if (term % 2 == 0) term / 2 else (3 * term) + 1

def byTailRecursion(upperbound: Long) = {
    .map(x => (x, tailRec(x)))

def tailRec(term: Long, length: Int = 0): Int =
  term match {
    case x if x == 1l => length + 1
    case x => tailRec( nextTerm(x), length+1)

I thought the nextTerm function would be the most expensive computationally due to the module and division involved. The attempt to optimize it was to save the sequence lengths on a map identified by the current number. If during a calculation a sequence of collatz was already calculated, we would obtain the length and avoid unnecessary calculations:

def savePaths(upperbound: Long) = {
  var cLengths = scala.collection.mutable.Map(1l -> 1)
  for(i <- 2l to upperbound) {
    var queue = new mutable.Queue(Long)
    var j = nextTerm(i)
    while(!cLengths.contains(j)) {
      j = nextTerm(j)
    queue.dequeueWhile((term) => {
    cLengths(term) = queue.size + cLengths(j)
    queue.size > 0

However, in practice, as the numbers increased, the "optimized" savePaths solution became significantly slower. When the upper limit was 1,000,000, tail recursion was executed in a quarter of the time on average since savePaths version. However, the nextTerm function was called approximately 1 million times less than with tail recursion.

I guess the main offender is the searches on the cLengths map. The other possibility is that Scala is paralleling the tail recursion call, but I'm not sure.

Java: new in Python, the longest collatz sequence

I am new to Python and I am struggling with a task.
"Consider the following operation applied to positive integer values: if the number is even, then divide it in half, but if the number is odd, multiply it by three and add one.
Write full Python functions as described below. All functions must be named and behave exactly as specified.
syracuse fn (n) Returns the result of the operation described in the first sentence of the preceding paragraph to the integer value n.
syracuse seq (n) For the Syracuse sequence with starting point n, it returns both its length and its largest element. For example, for n = 12, the result should be the pair 10 (length) and 16 (the largest). 1 2 3
longest seq (n) For starting points up to and including n, find which gives the longest sequence. Returns both the starting point and the length of the sequence. For example, with n = 10, the longest sequence has the starting point 9 and has a length of 20 "

So far I have:

def syracuse_fn(n):
#Return  the  result  of  the  operation to the integer value n
while n > 1:
    #If n is even, divide n by 2
    if (n%2) == 0:          
        n= n//2
    #if n is odd, multiply n by 3 and add 1
        n = 3*n+1
        return n

Any idea how to solve Syracuse_seq (n) or longest_seq (n).
Any help appreciated.

number theory: solve two variables for each n related to the Collatz conjecture

For this code, for each x I would like to solve all ranges of values ​​for c1 and c2 in a bounded range, that is, c1 and c2 in the range of real numbers + -100 for c1 and c2 for each x, which combined give "Length (stepsForEachN) == nRangeToCheck – 1". Here is the code so far, I'm not sure how to solve the two variables c1 and c2 for each x:

(*stepsForEachN output is A006577={1,7,2,5,8,16,3,19} if c1=c2=1*)
c1 = 1; 
c2 = 1;
nRangeToCheck = 10;
stepsForEachNwithIndex = {};
stepsForEachN = {};
stepsForEachNIndex = {};
maxStepsToCheck = 10000;

c1ValuesForEachN = {};

For(x = 2, x <= nRangeToCheck, x++,

 n = x;

 For(i = 1, i <= maxStepsToCheck, i++,
  If(EvenQ(n), n = Floor((n/2)*c1),
   If(OddQ(n), n = Floor((3*n + 1)*c2))

  If(n < 1.9,
   AppendTo(stepsForEachN, i);
   AppendTo(stepsForEachNIndex, x);
   AppendTo(stepsForEachNwithIndex, {x, i});
   i = maxStepsToCheck + 1
Length(stepsForEachN) == nRangeToCheck - 1

conditional: how do I modify my code to detect cycles in this recursion type Collatz?

A popular variant of Collatz's recursion is as follows. Given a positive integer $ n_i $,

  • Yes $ n_i $ even, $ n_ {i + 1} = 2n $,
  • Yes $ n_i $ it's odd $ n_ {n + 1} = 3n-1 $.

The Mathematica code that I am using to display the list of $ n_i $ For a given initial number it is:

collatz[x_] :=  NestWhileList[If[Mod[#, 2] == 0, #/2, #*3 - 1] &, x, # != 1 &]

However, this variant of the Collatz has cycles other than the trivial one. $ {4,2,1 } $, for example for initial values $ 5 $ Y $ 17 $. The above code only stops once $ 1 $ it is reached, which obviously creates an infinite loop for these inputs.

How do I modify the previous code so that other "loops" are also taken into account? I tried to modify the detention condition to include something like # != x But that condition is obviously met at the beginning of the cycle, and the introduction of variables that verify if it is the "first" iteration makes the code very messy.

Is there any "nice" way to do this?

Number number theory: what kind of graph is exactly the Collatz tree?

If the Collatz conjecture is true, then it is an infinite graph, equivalent to N. I think we can say that it is labeled, directed, weakly connected and a disjoint union of subgraph. We usually call it a tree, but is it exactly a tree? Is it an arborescence? A rooted tree? A polyforest?

programming challenge – Euler Project Problem # 14 largest Collatz sequence written in Python

Problem Statement:
The following iterative sequence is defined for the set of positive integers:

n → n / 2 (n is even)
n → 3n + 1 (n is odd)

Using the previous rule and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
You can see that this sequence (starting at 13 and ending at 1) contains 10 terms. Although it does not have
still tested (Collatz problem), it is thought that all the initial numbers end in 1.

What initial number, less than one million, produces the longest chain?

NOTE: Once the string starts, the terms can go over a million.
Here is my implementation written in Python, waiting for your comments.

from the time of import
from the operator import itemgetter

def collatz_count (n, count = {1: 1}):
"" "use cache (account) to speed up the search, return the sequence
length for the given number "" "
return count[n]
    except KeyError:
if n% 2 == 0:
tell[n] = collatz_count (n / 2) + 1
tell[n] = collatz_count (n * 3 + 1) + 1
return count[n]

def run_test ():
"" "uses the previous function, returns the number generated by the
Major sequence "" "
time1 = time ()
articles = ordered ([(x, collatz_count(x)) for x in range(1, 1000000)],
key = itemgetter (1), reverse = True)
maximum = articles[0]
    print (f & # 39; Initial number: {maximum[0]}  n sequence length:
{maximum[1]}  n & # 39;
f & # 39; Calculated in: {time () - time1} seconds. & # 39;)

yes __name__ == & # 39; __ main __ & # 39;
run_test ()

Sequences and series: for the Collatz conjecture, can you prove that you can not solve a loop to infinity? But the non-trivial $ n- $ cycle can be proven to not exist.

I'm not a mathematician, I'm not a researcher. My field is not even mathematical. My question is only out of curiosity. Can I say something mathematically possible?

Let's take a known function.

$$ C (n) = begin {cases} n / 2 & text {if} n equiv 0 pmod {2} \ 3n + 1 & text {if} n equiv 1 pmod {2} . end {cases} $$

Definition: A $ n- $ cycle is a cycle that can be divided into $ 2n $ contiguous subsequences: $ k $ increasing sequences of odd numbers alternating with $ n $ Decreasing sequences of even numbers. For example, if the cycle consists of a single, increasing sequence of odd numbers followed by a decreasing sequence of even numbers, it is called $ 1- $ cycle.

Let's suppose that, the non-trivial $ n $ The cycle proved to be non-existent.

Question: For the Collatz conjecture, can you prove that you can not solve a loop to infinity? But the non-trivial. $ n- $ It can be proved that the cycle does not exist.

I mean, I want to know if this contradicts the fundamental laws of mathematics. (Axiom systems and etc.)

Thank you.