Re: Proof of Collatz Conjecture?

mensanator@xxxxxxxxxxx wrote:
Benjamin E. Cawaling Jr. wrote:
You wrote:
But this doesn't even begin to show that there
aren't any cycles of length bigger than 3, or
that there aren't any numbers that never wind
up in a cycle.

I believe that what I had established, by the arbitrariness
of n and a (or b) in my argument, is that every standard Collatz
sequence Cn has a length-3 cycle because there is always one
solution with b = 1

But you haven't proved a cycle can't exist with b>1.

to the expression
Cn = <n, m, l, ..., (i, h, ..., d, c, b)>
for any natural number n, i in { n, m, l, ..., d, c, b } and,
hence, every Cn is of the form
Cn = <n, m, l, ..., (4, 2, 1)>.
I stopped at length-3 cycle because a length-3 cycle could not
be included in a larger cycle with length greater than 3

Ok, (4,2,1) can't be included in a larger cycle. But you haven't
proved that a larger cycle must include (4,2,1).

-- although
two input terms to the standard Collatz function could give the same
output term, there is always only one succeeding term to any term in
any sequence or the cycle. Thus, all of your above concerns are answered

No.

-- all of them due to the arbitrariness of n and b in my argument.

If it is necessary to show that there are no cycles with length greater
than 3, then one could simply proceed as follows:
8. Suppose there exists a
Cn = <n, m, l, ..., (e, d, c, b)>
- that is, a length-4 standard Collatz cycle - for some
starting natural number n with
b = min(e,d,c,b).
Then, we simply rehash our earlier argument:
e = f(b) = 3b + 1
d = f(e) = (3b+1)/2 = 4b yields b = -1/5
c = f(d) = 3[(3b+1)/2] + 1 = 2b yields b = -1

Do you think it's a coincidence that the 4-cycle yields -1 just like
the 2-cycle does? You're making a big mistake here (the fallacy of
value-centric thinking). What is important here is that -1 is an
INTEGER (albeit negative). A cycle exists whenever you get an
integer. The sign simply tells you the cycle is in the negative domain.


-- therefore, there is no valid solution so that the cycle
(e,d,c,b) does not exist.

It exists in the negative domain.


Again, suppose there exists a
Cn = <n, m, l, ..., (f*,e,d,c,b)>
-- that is, a length-5 standard Collatz cycle -- for some
starting natural number n with
b = min(f*,e,d,c,b).
Then, we simply rehash our earlier argument:
f* = f(b) = 3b + 1
e = f(f*) = (3b+1)/2
d = f(e) = 3[(3b+1)/2] + 1 = (9b+5)/2 = 4b
yields b = -5

Again, we have an integer.

c = f(d) = 3[(9b+5)/2] + 1 = (27b+17)/2 = 2b
yields b = -17/23

Whoa! You made a big mistake here. Here's the correct analysis:

There are five ways to have a length 5 sequence (I've added
0=even 1=odd to the variable names) and named the paths
A, B, C, D, E. For example, path A is f0,e1,d0,c0,b1.


A B C D E
f0 f0 f1 f0 f1
| | / | /
e1 e0 e0
\ | |
d0 d1
\ /
c0
|
b1

If the sequence is a loop cycle, the predecessor of f is b
and since b is odd, f must be even, so we can rule out paths
C and E.

For path A, I get

3b+1 = (8b-2)/3
b = -5

For path B

3b+1 = 16b
b = 1/13

For path D

3b+1 = (8b-4)/3
b = -7


So not only is your -17/23 completely wrong, but you missed
the third path which yields b = -7.

Note that it, too is an integer. But it is part of the -5 cycle
meaning b is not minimum, so we generally don't count that as
a seperate loop cycle even though the above is mathematically
sound. And the 4-cycle? That's just two iterations of the 2-cycle.
We don't count multi-iterations seperately either.

Would you like to bet that were you to analyze the 6-cycle, you
would find BOTH a +1 result (twice around the 3-cycle) and a
-1 (three times around the 2-cycle)?

-- therefore, there is no valid solution so that the
cycle (f*,e,d,c,b) does not exist.

It exists in the negative domain.


I think that there is a pattern here (I did not explore this
further

And that was a mistake. You should have explored all the way out to
length 18 cycles where you'll find a lot of integer results, a bunch of
new negative ones and the result of 9 times around the 2-cycle (-1)
and 6 times around the 3-cycle (+1).

because I didn't think it is necessary since I believe
that the arbitrariness of n in my earlier argument already
covers these concerns) that we could easily generalize by
mathematical induction to prove that there are no cycles with
length greater than 3 (hence, there is also no divergent sequence).

Conclusion based on false premise.

Have you completed the homework assignment I gave you?

Taking your little analysis out to the 18-cycle?

No? I don't see why not, there's only 2584 18-cycles and you
only have to check 1597 of them.

And don't complain, I would never ask anyone to do something
I couldn't do:

sequence18.py
# how many 18-sequences are there?
import gmpy
sequence = 18
print
print 'PART I: Constructing sequence tree from odd root'
b = [[1]] # root of sequence tree must be odd
count = 1
while count<sequence:
temp = []
for i in b[-1]:
if i==0: # an even can have both an ...
temp.append(0) # ...even predecessor and an
temp.append(1) # ... odd predecessor
else:
temp.append(0) # but an odd can only have an even
predecessor
b.append(temp)
count += 1
print
print 'First 5 levels of tree:'
print
for k in xrange(5):
print b[k]
print
print 'Sequences (all): %d Sequences (even): %d ' %
(len(b[-1]),len(b[-1])-sum(b[-1]))
print
print
print
print 'PART II: Count legal sequences using partition generator:'
print
svs = []
#
#
# Sequence Vectors are a list of positive integers that cannot have
# a 0 as an element. For example [1,2] represents a length 5 sequence
# since the count of elements is the number of odds and the sum of
# elements is the number of evens. So all sequences of length 18
# are the set of all possible Sequence Vectors whose count and sum
# equal 18.
#
# All lists of integers for a given count and sum where 0 cannot
# be an element is equivalent to the number of ways DEPTH items can be
# partitioned into WIDTH containers such that each container contains
# at least one item (so DEPTH must be >= WIDTH). The count will be
# Combinations(WIDTH-1,DEPTH-1)
# For a given sequence length such as 18, the WIDTH cannot be greater
# than 18/2 and WIDTH+DEPTH must equal 18.
#
# So the only valid (WIDTH,DEPTH) tuples are:
# (1,17) (2,16) (3,15) (4,14) (5,13) (6,12) (7,11) (8,10) and (9,9)
#
for width in xrange(1,sequence/2 + 1):
depth = sequence - width
svs.append(gmpy.comb(depth-1,width-1))
print 'For width: %3d depth: %3d svs: %4d' %
(width,depth,svs[-1])
print
print 'Total svs: %5d' % (sum(svs))
##
## L:\user_home\partitions>sequence18.py
##
## PART I: Constructing sequence tree from odd root
##
## First 5 levels of tree:
##
## [1]
## [0]
## [0, 1]
## [0, 1, 0]
## [0, 1, 0, 0, 1]
##
## Sequences (all): 2584 Sequences (even): 1597
##
##
##
## PART II: Count legal sequences using partition generator:'
##
## For width: 1 depth: 17 svs: 1
## For width: 2 depth: 16 svs: 15
## For width: 3 depth: 15 svs: 91
## For width: 4 depth: 14 svs: 286
## For width: 5 depth: 13 svs: 495
## For width: 6 depth: 12 svs: 462
## For width: 7 depth: 11 svs: 210
## For width: 8 depth: 10 svs: 36
## For width: 9 depth: 9 svs: 1
##
## Total svs: 1597
##
## Note how the partition counter directly returned only the svs
## where the starting sequence element is even. That's because the
## partion generator can only create legal sequences, so the false
## sequences (those with two consecutive odd numbers) we saw in
## Part I are not counted here.
##
## Part III, where the actual partitions are generated and the
## sequences checked for integer values of b are a seperate
## program: partition_generator_sequence18.py


partition_generator_sequence18.py
# how many 18-sequences?
import sys
from collatz_functions import *
def move_col(c):
sv[c-1] += 1
sv[c] -= 1
def find_c():
i = -1
while i<0:
if sv[i]>1:
return i
i -= 1
def rollover(c):
move_col(c)
sv[-1] = sv[c]
sv[c] = long('1')
def print_sv(cp):
print 'Crossover Point: %8d Sequence Vector:' % (cp),
svs = ""
for s in sv:
svs = svs + str(s) + ","
print svs[:-1]
print
print 'Part III: Test all partitions for integers'
print
sequences = 18 # find all sequences of 18 numbers by using
# partition generator to create all (DEPTH,WIDTH)
# tuples from (1,17) to (9,9)
sequence_count = 0
print
for width in xrange(1,10):
depth = sequences - width
if depth<width:
print 'depth',depth,'must be greater than width',width
sys.exit()
max_element = depth - width + 1
sv = []
for i in range(width):
sv.append(long('1'))
sv[-1] = max_element
xyz = calc_xyz(sv)
cp = crossover(xyz,1)
if cp[1]==0:
print_sv(cp[0])
sequence_count += 1
while sv[0]<max_element:
c = find_c()
if c < -1:
rollover(c)
xyz = calc_xyz(sv)
cp = crossover(xyz,1)
if cp[1]==0:
print_sv(cp[0])
sequence_count += 1
else:
move_col(c)
xyz = calc_xyz(sv)
cp = crossover(xyz,1)
if cp[1]==0:
print_sv(cp[0])
sequence_count += 1
print
print 'Sequences checked: %d' % (sequence_count)
##
## L:\user_home\partitions>partition_generator_sequence18.py
##
## Part III: Test all partitions for integers
##
##
## Crossover Point: 1 Sequence Vector: 2,2,2,2,2,2
## Crossover Point: -17 Sequence Vector: 1,1,1,2,1,1,4
## Crossover Point: -25 Sequence Vector: 1,1,2,1,1,4,1
## Crossover Point: -41 Sequence Vector: 1,1,4,1,1,1,2
## Crossover Point: -37 Sequence Vector: 1,2,1,1,4,1,1
## Crossover Point: -61 Sequence Vector: 1,4,1,1,1,2,1
## Crossover Point: -55 Sequence Vector: 2,1,1,4,1,1,1
## Crossover Point: -91 Sequence Vector: 4,1,1,1,2,1,1
## Crossover Point: -1 Sequence Vector: 1,1,1,1,1,1,1,1,1
##
## Sequences checked: 1597
##
## Note actual partitions generated matches the
## Combination(WIDTH-1,DEPTH-1)
## calculation we saw in Part II which matches the legal sequence
## count found by creating the sequence tree in Part I.
##
## As I predicted, we see b=1 for the sequence vector representing
## 6 iterations of the 3-sequence [2] and b=-1 representing
## 9 iterations of the 2-sequence [1].
##
## The other 7 negative numbers are all cyclic permutations of the
## sequence vector [1,1,1,2,1,1,4] and are thus, all part of the
## loop cycle at -17.

Now that wasn't so hard, was it? And look what I found, another
integer solution at -17. So can you now explain how you know there
are no others?

.

Relevant Pages

  • Re: An Argument for the Subroot Node
    ... each edge in the sequence is the initial vertex of the next edge ... If a graph has two distinct nodes with more than one path between ... it will contain a cycle. ...
    (sci.math)
  • Re: file editing
    ... > sequence, house, street, cycle, walk, read, filler, period, time); ...
    (comp.unix.questions)
  • Re: file editing
    ... > sequence, house, street, cycle, walk, read, filler, period, time); ...
    (comp.unix.shell)
  • Re: Array Programming Questions
    ... Given an array of length N containing integers between 1 and N, ... we have a successor function that defines a sequence that ends in a ... The object is to find the beginning of the cycle in the ... beyond the entry point. ...
    (comp.programming)
  • I got it now (was: M.Brushis paper on Collatz generalizations)
    ... incorporate his extentions into my Sequence Vector theory. ... Now, in 3n+C, C must be an odd number or you get parity ... By dynamically changing C during the sequence, Bruschi ...
    (sci.math)