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

%I #46 Aug 02 2023 10:02:10

%S 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,

%T 126,9,60,1023,26,2047,16,61,254,27,20,4095,510,125,56,8191,58,16383,

%U 124,25,1022,32767,48,23,22,253,252,65535,18,59,120,509,2046,131071

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

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

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

%H Antti Karttunen, <a href="/A243071/b243071.txt">Table of n, a(n) for n = 1..1024</a>

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

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

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

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

%F From _Antti Karttunen_, Jul 18 2020: (Start)

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

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

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

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

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

%F 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.]

%F (End)

%o (PARI)

%o 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)};

%o A243071(n) = if(n<=2, n-1, if(!(n%2), 2*A243071(n/2), 1+(2*A243071(A064989(n))))); \\ _Antti Karttunen_, Jul 18 2020

%o (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

%o (Scheme, with memoizing definec-macro from _Antti Karttunen_'s IntSeq-library)

%o (definec (A243071 n) (cond ((<= n 2) (- n 1)) ((even? n) (* 2 (A243071 (/ n 2)))) (else (+ 1 (* 2 (A243071 (A064989 n)))))))

%o (Python)

%o from functools import reduce

%o from sympy import factorint, prevprime

%o from operator import mul

%o def a064989(n):

%o f = factorint(n)

%o return 1 if n==1 else reduce(mul, (1 if i==2 else prevprime(i)**f[i] for i in f))

%o def a(n): return n - 1 if n<3 else 2*a(n//2) if n%2==0 else 1 + 2*a(a064989(n))

%o print([a(n) for n in range(1, 101)]) # _Indranil Ghosh_, Jun 15 2017

%Y Inverse: A163511.

%Y 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).

%Y 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)].

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

%K nonn

%O 1,3

%A _Antti Karttunen_, Jun 20 2014