A359194 Binary complement of 3*n.

1, 0, 1, 6, 3, 0, 13, 10, 7, 4, 1, 30, 27, 24, 21, 18, 15, 12, 9, 6, 3, 0, 61, 58, 55, 52, 49, 46, 43, 40, 37, 34, 31, 28, 25, 22, 19, 16, 13, 10, 7, 4, 1, 126, 123, 120, 117, 114, 111, 108, 105, 102, 99, 96, 93, 90, 87, 84, 81, 78, 75, 72, 69, 66, 63, 60, 57

Offset: 0

Author

Joshua Searle, Dec 19 2022

Keywords

• nonn
• base
• easy

Comments

The binary complement takes the binary value of a number and turns any 1s to 0s and vice versa. This is equivalent to subtracting from the next larger Mersenne number.

It is currently unknown whether every starting positive integer, upon iteration, reaches 0.

From M. F. Hasler, Dec 26 2022: (Start)

This map enjoys the following properties:

(P1) a(2*n) = a(n)*2 + 1 (since 3*(2*n) is 3*n shifted one binary digit to the left, and the one's complement yields that of 3*n with a '1' appended).

(P2) As an immediate consequence of (P1), all even-indexed values are odd.

(P3) Also from (P1), by immediate induction we have a(2^n) = 2^n-1 for all n >= 0.

(P4) Also from (P1), a(4*n) = a(n)*4 + 3.

(P5) Similarly, a(4*n+1) = a(n)*4 (because the 1's complement of 3 is 0).

(P6) From (P5), a(n) = 0 for all n in A002450 (= (4^k-1)/3). [For the initial value at n = 0 the discrepancy is explained by the fact that the number 0 should be considered to have zero digits, but here the result is computed with 0 considered to have one binary digit.] (End)

Examples

			a(7) = 10 because 3*7 = 21 = 10101_2, whose binary complement is 01010_2 = 10.
a(42) = 1 because 3*42 = 126 = 1111110_2, whose binary complement is 0000001_2 = 1.
a(52) = 99 by
  3*n        = binary 10011100
  complement = binary 01100011 = 99.
		

Links

• Michael S. Branicky, Table of n, a(n) for n = 0..10000
• Joshua Searle, Collatz-inspired sequences.

Crossrefs

Trisection of A035327.

Cf. A002450, A020988 (indices of 1's).

Cf. A256078.

Programs

PARI

a(n)=if(n, bitneg(3*n, exponent(3*n)+1), 1) \\ Rémy Sigrist, Dec 22 2022

Python

def a(n): return 1 if n == 0 else (m:=3*n)^((1 << m.bit_length()) - 1)
print([a(n) for n in range(67)]) # Michael S. Branicky, Dec 20 2022

Formula

a(n) = A035327(3*n).

a(n) = 0 iff n belongs to A002450 \ {0}. - Rémy Sigrist, Dec 22 2022