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 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