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

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.

Links

Table of n, a(n) for n=4..53.

Example

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.

Prog

(C) #include <stdio.h> #include <stdlib.h> #include <math.h> 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; }

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.

Sequence in context: A329778 A355391 A053163 * A141031 A061011 A359777

Adjacent sequences: A125623 A125624 A125625 * A125627 A125628 A125629

Keyword

easy,nonn

Author

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

Status

approved