A243071 Permutation of nonnegative integers: a(1) = 0, a(2) = 1, a(2n) = 2*a(n), a(2n+1) = 1 + 2*a(A064989(2n+1)).

0, 1, 3, 2, 7, 6, 15, 4, 5, 14, 31, 12, 63, 30, 13, 8, 127, 10, 255, 28, 29, 62, 511, 24, 11, 126, 9, 60, 1023, 26, 2047, 16, 61, 254, 27, 20, 4095, 510, 125, 56, 8191, 58, 16383, 124, 25, 1022, 32767, 48, 23, 22, 253, 252, 65535, 18, 59, 120, 509, 2046, 131071

Offset

1,3

Comments

Note the indexing: the domain starts from 1, while the range includes also zero.

See also the comments at A163511, which is the inverse permutation to this one.

Links

Antti Karttunen, Table of n, a(n) for n = 1..1024

Index entries for sequences that are permutations of the natural numbers

Formula

a(1) = 0, a(2) = 1, a(2n) = 2*a(n), a(2n+1) = 1 + 2*a(A064989(2n+1)).

For n >= 1, a(A000040(n)) = A000225(n).

For n >= 1, a(2n+1) = 1 + 2*a(A064216(n+1)).

From Antti Karttunen, Jul 18 2020: (Start)

a(n) = A245611(A048673(n)).

a(n) = A253566(A122111(n)).

a(n) = A334859(A225546(n)).

For n >= 2, a(n) = A054429(A156552(n)).

a(n) = A292383(n) + A292385(n) = A292383(n) OR A292385(n).

For n > 1, A007814(a(n)) = A007814(n) - A209229(n). [This map preserves the 2-adic valuation of n, except when n is a power of two, in which cases it is decremented by one.]

(End)

Prog

(PARI)
A064989(n) = {my(f); f = factor(n); if((n>1 && f[1, 1]==2), f[1, 2] = 0); for (i=1, #f~, f[i, 1] = precprime(f[i, 1]-1)); factorback(f)};
A243071(n) = if(n<=2, n-1, if(!(n%2), 2*A243071(n/2), 1+(2*A243071(A064989(n))))); \\ Antti Karttunen, Jul 18 2020
(PARI) A243071(n) = if(n<=2, n-1, my(f=factor(n), p, p2=1, res=0); for(i=1, #f~, p = 1 << (primepi(f[i, 1]) - 1); res += (p*p2*(2^(f[i, 2]) - 1)); p2 <<= f[i, 2]); ((3<<#binary(res\2))-res-1)); \\ (Combining programs given in A156552 and A054429) - Antti Karttunen, Jul 28 2023
(Scheme, with memoizing definec-macro from Antti Karttunen's IntSeq-library)
(definec (A243071 n) (cond ((<= n 2) (- n 1)) ((even? n) (* 2 (A243071 (/ n 2)))) (else (+ 1 (* 2 (A243071 (A064989 n)))))))
(Python)
from functools import reduce
from sympy import factorint, prevprime
from operator import mul
def a064989(n):
    f = factorint(n)
    return 1 if n==1 else reduce(mul, (1 if i==2 else prevprime(i)**f[i] for i in f))
def a(n): return n - 1 if n<3 else 2*a(n//2) if n%2==0 else 1 + 2*a(a064989(n))
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Jun 15 2017

Crossrefs

Inverse: A163511.

Cf. A000040, A000225, A007814, A054429, A064989, A064216, A122111, A209229, A245611 (= (a(2n-1)-1)/2, for n > 1), A245612, A292383, A292385, A297171 (Möbius transform).

Cf. A007283 (known positions where a(n)=n), A364256 [= gcd(n,a(n))], A364288 [= n-a(n)], A364289 [where a(n)>=n], A364290 [where a(n)<n], A364291 [where a(n)<=n], A364497 [where n|a(n)].

Cf. A156552 (variant with inverted binary code), A253566, A332215, A332811, A334859 (other variants).

Sequence in context: A366276 A269386 A252756 * A332811 A377834 A286556

Adjacent sequences: A243068 A243069 A243070 * A243072 A243073 A243074

Keyword

nonn

Author

Antti Karttunen, Jun 20 2014

Status

approved