Collatz ("3n+1") Problem: discoveries and questions
Geoffrey E. Caveney
Not long ago while browsing the Web I came across this fascinating
unsolved problem. For those who don't know it, consider the function where
f(n) for even integers = n/2, and for odd integers = 3n+1. The problem is
what happens when the function is applied repeatedly starting from a given
positive integer. For example, f(1) = 4, f(4) = 2, f(2) = 1, a cycle.
Every positive integer tested has eventually reached this cycle, but no
one has been able to prove that all positive integers do. A counterexample
could be another cycle or a number whose "Collatz sequence" increases
indefinitely.
If you don't see how difficult the problem can be, try the sequence for 27
on a pocket calculator. It takes quite a while to reduce to 1,4,2,1....
You can reason that if it can be shown that every number reduces to a
smaller number, induction will solve the problem, and indeed it can be
shown for even numbers of course, and for n=1 mod 4 (4x+1 -> 12x+4 -->
6x+2 --> 3x+1), n=3 mod 16, 11 mod 32, 23 mod 32, etc. But good luck
finding enough such forms to complete the proof--the smallest such modulo
covering 27 is n=27 mod 2^59 !
I gave up trying to solve the 3n+1 Collatz problem and thought of how to
generalize it from 3n+1 and n/2 to an+1 and n/b for coprime a,b. The "+1"
part has to be modified; instead think of 3n+1 as "3n and round up to the
next integer that 2 divides." Define the Collatz function for a/b as f(n)
for integers that b divides = n/b, and for other integers = an rounded up
to the next integer b divides.
I experimented with Collatz sequences for these values of a/b: 4/3, 5/3,
5/4, 6/5, 7/5, 8/5, and 7/6. Here's what I found:
The only other Collatz function that seems to reduce all integers to the
same cycle is 6/5. That cycle is 1,10,2,15,3,20,4,25,5,1.... I tested it
for small positive integers up to 30, and since 3^3 (27) was a messy one
for the 3/2 function, I checked 6^3 (216) for this one and it reduced to
the same cycle too.
The 4/3, 5/3, and 5/4 functions all appear to reduce all positive integers
to two cycles. For 4/3, one cycle is 1,6,2,9,3,1 and the other is the
longer 7,30,10,42,14,57,19,78,26,105,35,141,47,189,63,21,7. More integers
seem to reduce to the latter cycle than the former: of numbers 3 does not
divide less than 24, only 1,2,4,13,20 go to the first cycle, the rest go
to the 7 cycle.
But for 5/3 and 5/4, more integers seem to reduce to the smaller of
their two cycles. For 5/3 the cycles are 4,21,7,36,12,4 and
8,42,14,72,24,8. Aside from 8 and 14, the only number not divisible by 3 I
found reaching this cycle was 25. For 5/4 the first cycle is
1,8,2,12,3,16,4,1 but the other is much more complicated. I'll just give
the "roots" (integers that aren't divisible by 3, or generally for a/b
that aren't divisible by b) of the cycle:
23...29...37...47...59...74...93...117...147...46...58...73...23.
Aside from these roots, I only found n=11,14,18 going to this cycle.
Perhaps though this is an illusion created by checking mostly numbers
smaller than those in the cycle. When I checked 5^3 (125), however, it
reduced to the 1,8,2... cycle.
Things seem to get messier as b increases. For 7/5, small numbers reduce
to two cycles: 1,10,2,15,3,25,5,1 only for n=roots in the cycle and n=7;
and 6...9...13...19...27...38...54...76...107...6 for all other n<25 and
not divisible by 5, and for n=49. BUT my routine check of 7^3 (343)
created a problem: it escalates beyond the reach of my 8-digit calculator
without going into any cycle.
So my first question/request is this: can anybody who does number theory
computer programming check and see if large numbers of iterations of
f(n)=n/5 if 5|n, =7n rounded up to the next multiple of 5 if n is not a
multiple of 5, starting from f(343), reduce to a cycle. It's probably
simpler to program f(n) for n not divisible by 5 as 7n/5 rounded up to the
next greater integer, which amounts to the same thing.
8/5 is even more problematic. There's a small cycle: 4,35,7,60,12,100,20,4
but as small an integer as n=8 escalates beyond the 8-digit range without
cycling! Again I ask if anyone can check the iteration of f(n)=n/5 if 5|n,
=8n/5 rounded up to the next greater integer if not, for f(8).
Finally, 7/6 is the first Collatz function I found that produces 3 cycles:
(A) 1,12,2,18,3,24,4,30,5,36,6,1 for most integers < 28,
(B) 23...27...32...38...45...53...62...73...86...101...118...23 for
n=9,11,13,16,19, the roots in the cycle, and also for n=343 and 401,
and most surprisingly:
(C)
88...103...121...142...166...194...227...265...310...362...423...494...577...
674...787...919...1073...1252...1461...1705...1990...387...452...88 !
for n=49 as well as these roots in the cycle.
Perhaps someone could use a computer program to test more values of the
7/6 Collatz function for more cycles or non-cycling integers. (I don't
know how one would prove a given integer will never cycle!)
Comments greatly appreciated, as always.
Jeff
QSCGZ
>Define the Collatz function for a/b as f(n)
>for integers that b divides = n/b, and for other integers = an rounded up
>to the next integer b divides.
>Perhaps someone could use a computer program to test more values of the
>7/6 Collatz function for more cycles or non-cycling integers. (I don't
>know how one would prove a given integer will never cycle!)
try this small program :
10 input "a,b,n";A,B,N
20 if N@B then N=(A*N+B-1)\B else N=N\B
30 print N;:goto 20
written in ubasic.
7,5,343 reduces to a 6,... cycle
8,5,8 mounts up to 10^2500 , when you get an overflow
you can download ubasic from :
<A HREF="ftp://ftp.simtel.net/pub/simtelnet/msdos/ubasic/ub32i88a.zip">
ftp://ftp.simtel.net/pub/simtelnet/msdos/ubasic/ub32i88a.zip</A>
you might want to have a look at the other files in that directory too !
The most actual version (88b,10/20/97) is at :
<A HREF="ftp://rkmath.rikkyo.ac.jp/ubibm/ub32i88b.zip">
ftp://rkmath.rikkyo.ac.jp/ubibm/ub32i88b.zip</A>
qscgz
Dave Rusin
Geoffrey E. Caveney <cav...@wwa.com> wrote:
>I gave up trying to solve the 3n+1 Collatz problem and thought of how to
>generalize it from 3n+1 and n/2 to an+1 and n/b for coprime a,b.
I might generalize it a little more. This dresses up the problem so that
it looks primed for an easy victory. Of course it's not, but I can talk
fast -- to make it look convincing -- and then duck and run.
For p prime you can analyze the problem like this: recall that the
p-adic norm |x| of a rational number x = y/z is p^(s-r), where p^r and
p^s are respectively the greatest powers of p dividing y and z.
Then the rational number x*|x| has no powers of p in numerator or
denominator. It's also integral if x is, and positive if x is.
Observe that the standard Collatz conjecture simply asks about the
behaviour of the function
f(x) = (3x+1) * |3x+1| (where p=2)
on the positive integers: do the iterates of each x eventually become 1 ?
So you could easily generalize to this: given some linear map L(x) = mx+b
(with m and b integral) and a prime p, do the iterates of
f(x) = L(x) * |L(x)|
stabilize, whenever starting with a positive integer x? If there is more
than one limit point, which initial x lead to which limit?
The real reason this formulation is suggestive, I think, is that it allows us
to change the domain of x's while keeping the question; we can see how
the answers might differ. These functions f can be extended to any ring
containing the integers as long as the norm functions are defined; in
particular, they may be extended to the rationals, or to the p-adics or
p-adic integers. Here f is a continous function defined on one of these
rings and mapping into that ring's intersection with the p-adic unit ball.
So the iterates form a sequence inside this compact set, which if infinite
has a convergent subsequence; whatever x the subsequence converges to
is then a point for which some f^k(x) = x. But it's very easy to itemize such
points x for k = 1, 2, 3, ... It follows that every initial x eventually
falls into the same cycle as one of these x's. To solve the Collatz-like
conjectures, we have only to identify the x's to which such a sequence
can converge _when starting with a natural number_.
Consider the ordinary Collatz conjecture, L(x)=3x+1 and p=2. Of course x=1
is a fixed point of f. Are there other fixed points? The answer is ... YES!
If |3x+1| = 2^(-r), then x is a fixed point iff x = 1/(2^r-3); this
does indeed give the right norm to 3x+1 iff r > 0. So you see, the
ordinary Collatz conjecture has already overlooked the obvious other cycles
containing x =
-1, (1,) 1/5, 1/13, ...
But 1 is the only positive integer among these.
We next consider the possibility that the sequence of iterates of f
has a subsequence converging to an x with f(f(x))=x. Well, if
|3x+1| = 2^(-r) and |3 f(x) + 1 | = 2^(-s) then
x = (3 (3x+1)*2^(-r) + 1 ) * 2^(-s) means
x = (2^r + 3)/(2^(r+s) - 9), with r, s > 0;
this adds a host of new periodic points for f:
-5, -7, 5/7, 1/29, 11/7, ...
Of course, none can be another positive integer as 2^(r+s) - 9 > 2^r + 3
unless r+s < 4; those cases are easily checked.
We can go on in this way, finding many more interesting cycles (of increasing
length) than with the standard Collatz conjecture, yet never another cycle
involving positive integers. So if we start with a positive integer to form
the sequence of iterates, the x we converge to cannot be a positive integer
except x=1.
So is the Collatz conjecture solved? Well, no: not only have I lied about
four times, but something peculiar happens when we pass to the p-adics.
Recall that all sequences of iterates contain a convergent subsequence. What
if by luck we found a sequence of iterates which equalled
X+1, X+5, X+21, X+85, ..., X+(1+4+4^2+...4^N), ...
for some X. Where's the convergent subsequence? The answer is: the _whole
sequence_ converges, to X - 1/3 ! So unfortunately, the observations that
none of our periodic points are positive integers are irrelevant;
even though f(x) is a positive integer if x is, convergent sequences of
positive integers need not converge to positive integers.
dave
(He ducks...)
PS: To make this analysis rigorous, begin by noting that f isn't actually
continuous!
(...and runs)
Onno Garms
On 7 Feb 1998 08:44:35 GMT, ru...@vesuvius.math.niu.edu (Dave Rusin)
wrote:
>I might generalize it a little more. This dresses up the problem so that
>it looks primed for an easy victory. Of course it's not, but I can talk
>fast -- to make it look convincing -- and then duck and run.
>
>For p prime you can analyze the problem like this: recall that the
>p-adic norm |x| of a rational number x = y/z is p^(s-r), where p^r and
>p^s are respectively the greatest powers of p dividing y and z.
>Then the rational number x*|x| has no powers of p in numerator or
>denominator. It's also integral if x is, and positive if x is.
>
>Observe that the standard Collatz conjecture simply asks about the
>behaviour of the function
> f(x) = (3x+1) * |3x+1| (where p=2)
>on the positive integers: do the iterates of each x eventually become 1 ?
>
>four times but something peculiar happens when we pass to the p-adics.
>Recall that all sequences of iterates contain a convergent subsequence. What
>if by luck we found a sequence of iterates which equalled
> X+1, X+5, X+21, X+85, ..., X+(1+4+4^2+...4^N), ...
>for some X. Where's the convergent subsequence? The answer is: the _whole
>sequence_ converges, to X - 1/3 ! So unfortunately, the observations that
>none of our periodic points are positive integers are irrelevant;
>even though f(x) is a positive integer if x is, convergent sequences of
>positive integers need not converge to positive integers.
>
>PS: To make this analysis rigorous, begin by noting that f isn't actually
>continuous!
Great "proof"! But as long as you do not define |0| and hence f(-1/3)
(you did not do so) the function |.| is even locally constant and
hence f continious, am I right?
How did you find your ideas? Is this piece of mathematical rhetorics
some garbage you got when attempting to find a real proof? Or did you
even at the beginning intend to find a "theory" for the Collatz
conjecture which is good to fool the readers?
Onno Garms
ga...@iname.com
Dave Rusin
Onno Garms <ga...@iname.com> wrote:
>On 7 Feb 1998 08:44:35 GMT, ru...@vesuvius.math.niu.edu (Dave Rusin)
>wrote:
...
>>Observe that the standard Collatz conjecture simply asks about the
>>behaviour of the function
>> f(x) = (3x+1) * |3x+1| (where p=2)
>>on the positive integers: do the iterates of each x eventually become 1 ?
...
>Great "proof"! But as long as you do not define |0| and hence f(-1/3)
>(you did not do so) the function |.| is even locally constant and
>hence f continious, am I right?
Right; the usual definition is |0|=0, but while |x| is continuous on the set
of nonzero p-adics, it admits no continuous extension to 0.
>How did you find your ideas? Is this piece of mathematical rhetorics
>some garbage you got when attempting to find a real proof? Or did you
>even at the beginning intend to find a "theory" for the Collatz
>conjecture which is good to fool the readers?
Fool the readers? Me? I'm just here to help :-)
Actually it's more accurate to say that I was trying to put the Collatz
conjecture into some context which makes it seem less arbitrary. Certainly
the idea of looking for cycles in dynamical systems of nearly-linear
maps is quite common; indeed, at first blush, the map f(x) = L(x)*|L(x)|
looks quadratic, just like the common choices for f on the complex
plane. But having placed the problem into the "right" context does not
mean we are any closer to a solution (compare e.g. the Langlands conjectures).
dave