From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Subject: Re: simple question
Date: 15 Oct 1999 22:52:08 GMT
Newsgroups: sci.math.num-analysis
Keywords: Iterate x-> 3x+1; get a power of 2? (No)
In article ,
Virgil wrote:
>In article , phiferd@alleg.edu (Dan) wrote:
>
>>ok, I put this up last year and I didn't get any replied, hopefully I
>>will get one this time.
>>
>>For x in N
>>If you iterate the function f(x) = x + 1, eventually you will get a
>>power of 2, obviously.
>>
>>For f(x) = 2x + 1 you will never get a power of two becasue it's
>>always odd.
>>
>>Now, f(x) = 3x+1. Can anyone tell figure this out. Will you always
>>get a power of two for any x in N?
>>Dan
>
>No one knows. This is a disguised version of the 3*n+1 puzzle:
Is it? I don't really think so.
You've got an initial x = x0. You define a sequence of x's by
x_n = f( x_{n-1} ). You want to know whether or not x_n is a power
of 2 for some n. Well, in this problem (_unlike_ the "3x+1 problem")
you can obtain a simple form for the terms of the sequence:
x_n = 3^n x_0 + (3^n - 1)/2
which is easily checked by induction. So now your question is whether,
for a given x0, there are integers n and m with
(*) 2^m + 1 = 3^n T
where I have set T = 2 x0 + 1.
We may solve for m :
m = log_2( 3^n T - 1 ) = n log_2(3) + log_2(T) + log_2(1 - 1/3^n/T)
the last term being O( 1 / 3^n ), which is to say quite small!
Ignoring that last term, we see the question is only to decide whether
or not there is an integer n for which
alpha n + beta
is (extremely near to) an integer (=m), where in this case alpha=log_2(3)
and beta = log_2(T). This is then a question of Diophantine approximations,
or I guess Transcendental Number Theory. I can't recall a nice specific
reference in this case, but the short answer is: it ain't gonna happen.
There's a related way to view equation (*). With T fixed, you are
looking for an equation of the form X + Y = Z where the prime divisors
of X, Y, and Z are fixed in advance and X,Y, and Z are coprime.
In general there are only finitely many solutions to this equation.
For example, when the prime divisors are 2, 3, and 5 then there are
I think only 17 solutions ranging in complexity from 1 + 1 = 2 to
80 + 1 = 81 and 125 + 3 = 128. In particular, if we start with, say, x0 = 7
(so T = 15 ) then (*) would have to be an equation on this finite list,
with a right-hand side divisible by 15. There are no such equations,
so your iterations will never end in a power of 2.
dave
Transcendental number theory: try
http://www.math-atlas.org/index/11JXX.html
==============================================================================
From: Gareth McCaughan
Subject: Re: simple question
Date: 15 Oct 1999 23:46:53 +0100
Newsgroups: sci.math.num-analysis
"Dan" wrote:
[iterating functions ...]
> Now, f(x) = 3x+1. Can anyone tell figure this out. Will you always
> get a power of two for any x in N?
No. Try starting with x=7, and look at what happens mod 4. We get
3, 2, 3, ... and it repeats. We never get anything that's 0 mod 4,
so in particular we never get a power of 2. (You need to check that
that first 2 isn't actually the number 2, but it isn't!)
--
Gareth McCaughan Gareth.McCaughan@pobox.com
sig under construction