Analogues to the 3x+1, x/2 problem

As detailed here, if you consider “the behavior of the iterates of the function which takes odd integers n to 3n+1 and even integers n to n/2, the ‘3x+1 Conjecture’ asserts that, starting from any positive integer n, repeated iteration of this function eventually produces the value 1.” There are actually lots of sites which address this function (e.g. here).

I don’t have a clue about 99% of the contents of these sites, but I do have a simple question:

Are there are other, similar, functions on the integers that ultimately produce the value 1?

yes, the 0x + 1 iteration :slight_smile:

Certainly. There are an infinite number of functions which converge to 1. If x[sub]n[/sub] is a series such that x[sub]n[/sub] > x[sub]n+1[/sub] and x[sub]n[/sub] > 1 but x[sub]n+1[/sub] is not bounded below by any greater constant, then any function that (in general) takes x[sub]n[/sub] to x[sub]n+1[/sub] converges to 1.

More on this tomorrow–I’ll have time to look up theorems then.

Thanks ultrafilter, but I think you’re giving me too much credit. I’m just looking for another “rule” such as if you take odd integers to k[sub]1[/sub]n+k[sub]2[/sub] and even integers to n/2, then you’ll always arrive at 1.

That’s true, ultrafilter, but KarlGauss asked about similar functions. For one thing, the one mentioned in the OP does not converge to 1, but winds up cycling through 4, 2, 1, 4, 2, 1, etc.

I’m thinking that if we replace the 3 in the problem with a 1, ie, f(n) = n/2 for n even, and n+1 for n odd, would hit 1 pretty rapidly. I don’t know about any others, though.

IIRC, that’s called the Syracuse Algorithm.

And, as KarlGauss’s link shows, the Collatz problem, the Syracuse problem, Kakutani’s problem, Hasse’s algorithm, Ulam’s problem, and the 3x+1 problem.

Hey, KarlGauss, this one should be right up your alley.

Oops, missed that. I just want to point out that it cycles 2, 1, 2, 1, etc., not 4, 2, 1, 4 etc.

Yeah, I realized this morning that what I said probably wasn’t exactly right. Well, there’s always x[sub]n+1[/sub] = (-1)*x[sub]n[/sub], with x[sub]1[/sub] = 1.

?? I musta been talking about Achernar’s other function

Wow, took you a while to catch that one.

God bless MathWorld. There’s some discussion of the generalized Collatz Problem near the bottom.

What’s interesting about this function (which I know of as the hailstone problem for what are obvious reasons if you actually watch its behavior) is that no one knows if it always hits the 4,2,1 cycle, although lots of people have worked on it. In that sense I know of no similar functions.

x/x always yields 1 :smiley:


Except when x=0 :doh: