Re: "Collatz 3n+1 conjecture is unprovable" paper; one last comment


Craig Feinstein wrote:
mensanator@xxxxxxxxxxx wrote:
Craig Feinstein wrote:
Proginoskes wrote:
A while back (Mon, May 15 2006 8:50 am), Craig Feinstein wrote in
sci.math:

if the Theorem 2 [in his paper] is wrong, then you should be able to
pick a number like 7 or 32 and rigorously prove that when applied to
the Collatz algorithm, the algorithm will halt at one *without talking
about what the algorithm does at each iteration*. If you can do this,
then and only then have you shown that Theorem 2 is wrong. If not, then
you are simply fooling yourself.

Searching through MathSciNet for a paper on Collatz and the 2-adics, I
found the following paper:

Stefan Andrei, Cristian Masalagiu, "About the Collatz conjecture."
Acta Informatica 35 (1998), no. 2, 167--179.

In the abstract, it states: "[The authors] show that the value of $k$
such that $f^{(k)}(n) =1$ can be found by an algorithm faster than the
one deriving from a direct application of the definition. They argue,
but don't give a definite proof, that their algorithm is three times
faster than the trivial one (the one obtained by applying the
definitions)."

So not only can it be proved that f^(k)(n) = 1 without using the
definition, there's actually a quicker way without the definition.

OK, I'll believe you if you can use the results given in this paper to
rigorously prove that when the number 7 is applied to the Collatz
algorithm, the algorithm will halt at one *without talking about what
the algorithm does at each iteration*.

I'll use my own paper instead. Not that it matters, once you're
proved wrong it doesn't matter if other prrofs exist.


But I'm not holding my breath for such a proof.

## Feinstein:
##
## Theorem 2: If k, n ∈ N and T(k)(n) = 1, then in order to prove
## that T(k)(n) = 1, it is necessary to specify the values
## of (n, T(n), ..., T(k−1)(n)) mod 2 in the proof.
##
## Proof: The formula for T(k)(n) is determined by the values of
## (n, T(n), ..., T(k−1)(n)) mod 2, and there is a
## one-to-one correspondence between all of the possible
## formulas for T(k)(n) and all of the possible values of
## (n, T(n), ..., T(k−1)(n)) mod 2 (Lagarias, 1985);
## therefore, in order to prove that T(k)(n) = 1, it is
## necessary to specify the values of (n, T(n), ...,
## T(k−1)(n)) mod 2 in the proof, since in order to prove
## that T(k)(n) = 1, it is necessary to specify the formula
## for T(k)(n) in the proof.

import gmpy

#
# Sequence Vector utilities
#
def seed(a,xyz):
"""calculate Seed from Hailstone

seed(a,xyz)
a: hailstone
xyz: HailstoneFunctionParameters
x * a - z
g = ---------
y
returns (0) if invalid
returns Seed (g)
"""
g = divmod(xyz[0]*a-xyz[2],xyz[1])
if g[1]==0:
return g[0]
else:
return 0

def gen0(k,xyz):
"""Find first member of generation k of Hailstone Function.

gen0(k,xyz)
k: generation
xyz: HailstoneFunctionParameters

<Non-recursive version>

a: the first solution to the Hailstone Function
g: seed that genertes _a_
d: difference between _a_ and _g_
j: index of _a_ where d == 0 (mod y**k)
c: a[j] the
returns [0,0,0,0] if k invalid
returns GenerationParameters [a,g,d,c]
"""
ONE = gmpy.mpz(1)
yx = gmpy.mpz(xyz[1]-xyz[0])
gen = gmpy.mpz(0)
while gen<k:
if gen==0:
a = gmpy.divm(xyz[2],xyz[0],xyz[1])
g = seed(a,xyz)
d = a - g
c = a
gen += 1
ap = a
gp = g
dp = d
cp = c
else:
j =
gmpy.divm(xyz[1]**(gen)-dp,yx,xyz[1]**(gen))/xyz[1]**(gen-ONE)
a = j*xyz[1]**(gen) + cp
g = seed(a,xyz)
c = a
d = a - g
gen += 1
ap = a
gp = g
dp = d
cp = c
return [a,g,d,c]

def geni(k,i,xyz):
"""Find ith kth generation hailstone

geni(k,i,xyz)
i: member of generation
k: generation
xyz: HailstoneFunctionParameters
a(k,i) = i*y**k + a(k,0) k,i: { 1, 2, 3, ...}
returns Hailstone (a)
"""
K = gmpy.mpz(k)
I = gmpy.mpz(i-1)
if (k<1) or (i<1):
return 0
else:
a = gen0(k,xyz)
return I*xyz[1]**K + a[0]

def calc_xyz(sv):
"""calculate Hailstone Function Parameters

calc_xyz(sv)
sv: sequence vector
returns HailstoneFunctionParameters (x,y,z)
"""
TWO = gmpy.mpz(2)
TWE = gmpy.mpz(3)
twee = gmpy.mpz(len(sv))
twoo = gmpy.mpz(sum(sv))
x = TWO**twoo
y = TWE**twee
z = gmpy.mpz(0)
for i in xrange(len(sv)):
z = z + (TWE**i * TWO**sum(sv[:-(i+1)]))
return (x,y,z)


#
# Partition Generator
#

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] = 1


#
# Test if partition generated is an actual Collatz Sequence
# without actually running it through the Collatz
# process (no intermediate values calculated)

def print_sv(sv):
# All Sequence Vectors that are Collatz Sequences must end
# in an even number >=4
#
# This last number is appended to the vector created by the
# partition generator, so actual vector checked will always
# be width+1.
#
sv.append(4)
xyz = calc_xyz(sv)
a0 = geni(1,1,xyz)
if a0==1:
# If true, Sequence Vector is an actual Collatz Sequence
# that ends at 1, so find the seed that generates it.
g0 = seed(a0,xyz)
print sv, g0
return 1
return 0

#
# Main: prove the Collatz Sequence 7 ... 1 without ever calculating
# any intermediate values
#

width = 4

for depth in xrange(width,width+9):
#
# Partition generator creates all partitions of depth items into
# width containers such that each container has at least 1 item.
# This is equivalent to all Collatz Sequences starting with an odd
# number having width 3n+1 iterations and depth n/2 iterations.
#
m = depth - 1
n = width - 1
print
print 'Checking %d Sequence Vectors with Width=%d Depth=%d' %
(gmpy.comb(m,n),width,depth)
max_element = depth - width + 1
sv = []
for i in range(width):
sv.append(1)
sv[-1] = max_element
found = print_sv(sv[:])
count = 1
while sv[0]<max_element:
c = find_c()
if c < -1:
rollover(c)
found += print_sv(sv[:])
else:
move_col(c)
found += print_sv(sv[:])
count += 1
print 'Solutions found: %d' % (found)

## Checking 1 Sequence Vectors with Width=4 Depth=4
## Solutions found: 0
##
## Checking 4 Sequence Vectors with Width=4 Depth=5
## Solutions found: 0
##
## Checking 10 Sequence Vectors with Width=4 Depth=6
## Solutions found: 0
##
## Checking 20 Sequence Vectors with Width=4 Depth=7
## [1, 1, 2, 3, 4] 7
## Solutions found: 1

## QED

##
## Checking 35 Sequence Vectors with Width=4 Depth=8
## [1, 1, 1, 5, 4] 15
## Solutions found: 1
##
## Checking 56 Sequence Vectors with Width=4 Depth=9
## [3, 1, 2, 3, 4] 29
## Solutions found: 1
##
## Checking 84 Sequence Vectors with Width=4 Depth=10
## [3, 1, 1, 5, 4] 61
## Solutions found: 1
##
## Checking 120 Sequence Vectors with Width=4 Depth=11
## [5, 1, 2, 3, 4] 117
## Solutions found: 1
##
## Checking 165 Sequence Vectors with Width=4 Depth=12
## [2, 5, 2, 3, 4] 241
## [5, 1, 1, 5, 4] 245
## Solutions found: 2

You can breathe now.

You have not presented a rigorous proof.

Haven't you read my paper?

Blueprint for Failure
How to Construct a Counterexample to the Collatz Conjecture
Full paper at S.A.T.O. Volume 5.3. (2006)
<http://home.zonnet.nl/galien8>

It's the least you can do. After all, I read yours.

You just gave a lot of computer code.

Which resolves the question of whether I can prove a
sequence starting with 7 ends at 1 without calculating
intermediate values which suffices to show that your
Theorem 2 is false.

It's no surprise, because a rigorous proof is impossible.

But I don't have to give a rigorous proof for all integers,
I just have to show that your Theorem 2 is false.
That's what you asked for and that's what I gave you.

It's too bad that the state-of-the-art in Collatz research
has passed you by. You would be better off trying to
catch up than moaning about your worthless proof.




Craig

.

Relevant Pages
Loading