A125626 Numbers n whose reverse binary representation has the following property: let a 0 mean "halving" and a 1 mean "k -> 3k+1". The number describes an operation k -> f_n(k). If the equation f_n(k) = k has a positive solution, n is a term in the sequence.

4, 8, 16, 32, 33, 34, 36, 40, 48, 64, 65, 66, 68, 72, 80, 96, 128, 129, 130, 131, 132, 133, 134, 136, 137, 138, 140, 144, 145, 146, 148, 152, 160, 161, 162, 164, 168, 176, 192, 193, 194, 196, 200, 208, 224, 256, 257, 258, 259, 260

Offset: 4

Author

Nicholas Sanders (gummybean(AT)gmail.com), Jan 27 2007

Keywords

• easy
• nonn

Comments

The terms in this sequence have the following characterization. Suppose the binary expansion of n contains i 1's and j 0's. Then it is easy to see that n is in the sequence if and only if 3^i < 2^j, or i/j < log 2 / log 3 = 0.630929753... - David Applegate and N. J. A. Sloane, Feb 01 2007

Note that f_n(x) is always a linear function of x.

The reverse binary expansions of the first few terms are:

001

0001

00001

000001

100001

010001

001001

000101

000011

0000001

1000001

0100001

0010001

0001001

0000101

0000011

00000001

10000001

01000001

11000001

00100001

...

Could be used in conjunction with the Collatz (or 3x+1) conjecture. If the positive solution k is an integer (most are not) then a cycle exists. If this cycle does not contain a 1 and the sequence of steps agrees with what Collatz's rule tells you to do when you start with k, then the Collatz conjecture would be false.

Examples

			Consider the term 200: its binary representation is 11001000. Reversing this gives 00010011. We solve (3*(3*(((3*(((k/2)/2)/2)+1)/2)/2)+1)+1) = k and find k = 40. Since k is positive, 200 is a member of the sequence.
		

Crossrefs

For the values of n for which the fixed point k is a positive (or any) integer, see A125754-A125757.

Cf. A112695, A125710, A125711.

Programs

C

#include  #include  #include  void multiply(float *coef, float *cons) { (*coef) *= 3; (*cons) = 3*(*cons)+1; } void divide(float *coef, float *cons) { (*coef) /= 2; (*cons) /= 2; } int main() { int a, b, c, n; float coef, cons, final; char data[30], sequence[30]; for (a = 1; a < 500; a++) { coef = 1; cons = 0; c = a; sequence[0] = ''; for (b = 1; b < 12; b++) //12 is arbitrary; it allows for "a" up to 2^12 { if (c != 0) { if (c % 2) { sprintf(sequence, "%s1", sequence); multiply(&coef, &cons); } else { sprintf(sequence, "%s0", sequence); divide(&coef, &cons); } c = trunc(c/2); } else break; } if (coef >= 1.0) { coef -= 1.0; cons *= -1.0; } else coef = 1.0-coef; final = cons/coef; if (final > 0) { sprintf(data, "%10.3f %s %d ", final, sequence, a); printf(data); } } return 0; }