A140263 -id:A140263 - cp's OEIS frontend

A140264 Inverse permutation to A140263.

0, 1, 2, 5, 7, 3, 6, 4, 8, 17, 19, 15, 23, 25, 21, 11, 13, 9, 18, 16, 20, 12, 10, 14, 24, 22, 26, 53, 55, 51, 59, 61, 57, 47, 49, 45, 71, 73, 69, 77, 79, 75, 65, 67, 63, 35, 37, 33, 41, 43, 39, 29, 31, 27, 54, 52, 56, 48, 46, 50, 60, 58, 62, 36, 34, 38, 30, 28, 32, 42, 40, 44

Offset: 0

Antti Karttunen, May 19 2008

nonn

Index entries for sequences that are permutations of the natural numbers

Inverse: A140263.

def a117966(n):
    if n==0: return 0
    if n%3==0: return 3*a117966(n/3)
    elif n%3==1: return 3*a117966((n - 1)/3) + 1
    else: return 3*a117966((n - 2)/3) - 1
def Z(z): return 2*z if z>0 else 2*abs(z) + 1
def a140266(n): return Z(a117966(n - 1))
def a(n): return a140266(n + 1) - 1 # Indranil Ghosh, Jun 07 2017

(define (A140264 n) (- (A140266 (+ 1 n)) 1))

a(n) = A140266(n+1)-1.

A140265 Permutation of natural numbers: a(n) = A140263(n-1)+1.

Original entry on oeis.org

1, 2, 3, 6, 8, 4, 7, 5, 9, 18, 23, 16, 22, 17, 24, 12, 20, 10, 19, 11, 21, 15, 26, 13, 25, 14, 27, 54, 68, 52, 67, 53, 69, 48, 65, 46, 64, 47, 66, 51, 71, 49, 70, 50, 72, 36, 59, 34, 58, 35, 60, 30, 56, 28, 55, 29, 57, 33, 62, 31, 61, 32, 63, 45, 77, 43, 76, 44, 78, 39, 74, 37

Offset: 1

Antti Karttunen, May 19 2008

Inverse: A140266.

from sympy import ceiling
from sympy.ntheory.factor_ import digits
def a004488(n): return int("".join([str((3 - i)%3) for i in digits(n, 3)[1:]]), 3)
def a117968(n):
    if n==1: return 2
    if n%3==0: return 3*a117968(n/3)
    elif n%3==1: return 3*a117968((n - 1)/3) + 2
    else: return 3*a117968((n + 1)/3) + 1
def a117967(n): return 0 if n==0 else a117968(-n) if n<0 else a004488(a117968(n))
def a001057(n): return -(-1)**n*ceiling(n/2)
def a(n): return a117967(a001057(n - 1)) + 1 # Indranil Ghosh, Jun 07 2017

(define (A140265 n) (+ 1 (A140263 (- n 1))))

A263273 Bijective base-3 reverse: a(0) = 0; for n >= 1, a(n) = A030102(A038502(n)) * A038500(n).

Original entry on oeis.org

0, 1, 2, 3, 4, 7, 6, 5, 8, 9, 10, 19, 12, 13, 22, 21, 16, 25, 18, 11, 20, 15, 14, 23, 24, 17, 26, 27, 28, 55, 30, 37, 64, 57, 46, 73, 36, 31, 58, 39, 40, 67, 66, 49, 76, 63, 34, 61, 48, 43, 70, 75, 52, 79, 54, 29, 56, 33, 38, 65, 60, 47, 74, 45, 32, 59, 42, 41, 68, 69, 50, 77, 72, 35, 62, 51, 44, 71, 78, 53, 80, 81

Offset: 0

Antti Karttunen, Dec 05 2015

Here the base-3 reverse has been adjusted so that the maximal suffix of trailing zeros (in base-3 representation A007089) stays where it is at the right side, and only the section from the most significant digit to the least significant nonzero digit is reversed, thus making this sequence a self-inverse permutation of nonnegative integers.
Because successive powers of 3 and 9 modulo 2, 4 and 8 are always either constant 1, 1, 1, ... or alternating 1, -1, 1, -1, ... it implies similar simple divisibility rules for 2, 4 and 8 in base 3 as e.g. 3, 9 and 11 have in decimal base (see the Wikipedia-link). As these rules do not depend on which direction they are applied from, it means that this bijection preserves the fact whether a number is divisible by 2, 4 or 8, or whether it is not. Thus natural numbers are divided to several subsets, each of which is closed with respect to this bijection. See the Crossrefs section for permutations obtained from these sections.
When polynomials over GF(3) are encoded as natural numbers (coefficients presented with the digits of the base-3 expansion of n), this bijection works as a multiplicative automorphism of the ring GF(3)[X]. This follows from the fact that as there are no carries involved, the multiplication (and thus also the division) of such polynomials could be as well performed by temporarily reversing all factors (like they were seen through mirror). This implies also that the sequences A207669 and A207670 are closed with respect to this bijection.

			For n = 15, A007089(15) = 120. Reversing this so that the trailing zero stays at the right yields 210 = A007089(21), thus a(15) = 21 and vice versa, a(21) = 15.

Antti Karttunen, Table of n, a(n) for n = 0..6561
Wikipedia, Divisibility rule
Index entries for sequences that are permutations of the natural numbers

Bisections: A264983, A264984.
Cf. A000035, A007089, A010873, A030102, A038500, A038502, A207669, A207670.
Cf. also A057889, A264965, A264966, A264980.
Permutations induced by various sections: A263272 (a(2n)/2), A264974 (a(4n)/4), A264978 (a(8n)/8), A264985, A264989.
Cf. also A004488, A140263, A140264, A246207, A246208 (other base-3 related permutations).

r[n_] := FromDigits[Reverse[IntegerDigits[n, 3]], 3]; b[n_] := n/ 3^IntegerExponent[n, 3]; c[n_] := n/b[n]; a[0]=0; a[n_] := r[b[n]]*c[n]; Table[a[n], {n, 0, 80}] (* Jean-François Alcover, Dec 29 2015 *)

from sympy import factorint
from sympy.ntheory.factor_ import digits
from operator import mul
def a030102(n): return 0 if n==0 else int(''.join(map(str, digits(n, 3)[1:][::-1])), 3)
def a038502(n):
    f=factorint(n)
    return 1 if n==1 else reduce(mul, [1 if i==3 else i**f[i] for i in f])
def a038500(n): return n/a038502(n)
def a(n): return 0 if n==0 else a030102(a038502(n))*a038500(n) # Indranil Ghosh, May 22 2017

(define (A263273 n) (if (zero? n) n (* (A030102 (A038502 n)) (A038500 n))))

a(0) = 0; for n >= 1, a(n) = A030102(A038502(n)) * A038500(n).
Other identities. For all n >= 0:
a(3*n) = 3*a(n).
A000035(a(n)) = A000035(n). [This permutation preserves the parity of n.]
A010873(a(n)) = 0 if and only if A010873(n) = 0. [See the comments section.]

A117967 Positive part of inverse of A117966; write n in balanced ternary and then replace (-1)'s with 2's.

Original entry on oeis.org

0, 1, 5, 3, 4, 17, 15, 16, 11, 9, 10, 14, 12, 13, 53, 51, 52, 47, 45, 46, 50, 48, 49, 35, 33, 34, 29, 27, 28, 32, 30, 31, 44, 42, 43, 38, 36, 37, 41, 39, 40, 161, 159, 160, 155, 153, 154, 158, 156, 157, 143, 141, 142, 137, 135, 136, 140, 138, 139, 152, 150, 151, 146

Offset: 0

Franklin T. Adams-Watters, Apr 05 2006

			7 in balanced ternary is 1(-1)1, changing to 121 ternary is 16, so a(7)=16.

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 2, pp. 173-175

Alois P. Heinz, Table of n, a(n) for n = 0..9841
Ken Levasseur, The Balanced Ternary Number System

Cf. A117966. a(n) = A004488(A117968(n)). Bisection of A140263. A140267 gives the same sequence in ternary.

a:= proc(n) local d, i, m, r; m:=n; r:=0;
      for i from 0 while m>0 do
         d:= irem(m, 3, 'm');
         if d=2 then m:=m+1 fi;
         r:= r+d*3^i
      od; r
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, May 11 2015

a[n_] := Module[{d, i, m = n, r = 0}, For[i = 0, m > 0, i++, {m, d} = QuotientRemainder[m, 3]; If[d == 2, m++]; r = r + d*3^i]; r];
a /@ Range[0, 100] (* Jean-François Alcover, Jan 05 2021, after Alois P. Heinz *)

from sympy.ntheory.factor_ import digits
def a004488(n): return int("".join([str((3 - i)%3) for i in digits(n, 3)[1:]]), 3)
def a117968(n):
    if n==1: return 2
    if n%3==0: return 3*a117968(n/3)
    elif n%3==1: return 3*a117968((n - 1)/3) + 2
    else: return 3*a117968((n + 1)/3) + 1
def a(n): return 0 if n==0 else a004488(a117968(n)) # Indranil Ghosh, Jun 06 2017

;; Two alternative definitions in MIT/GNU Scheme, defined for whole Z:
(define (A117967 z) (cond ((zero? z) 0) ((negative? z) (A004488 (A117967 (- z)))) (else (let* ((lp3 (expt 3 (A062153 z))) (np3 (* 3 lp3))) (if (< (* 2 z) np3) (+ lp3 (A117967 (- z lp3))) (+ np3 (A117967 (- z np3))))))))
(define (A117967v2 z) (cond ((zero? z) 0) ((negative? z) (A004488 (A117967v2 (- z)))) ((zero? (modulo z 3)) (* 3 (A117967v2 (/ z 3)))) ((= 1 (modulo z 3)) (+ (* 3 (A117967v2 (/ (- z 1) 3))) 1)) (else (+ (* 3 (A117967v2 (/ (+ z 1) 3))) 2))))
;; Antti Karttunen, May 19 2008

a(0) = 0, a(3n) = 3a(n), a(3n+1) = 3a(n)+1, a(3n-1) = 3a(n)+2.

If one adds this clause, then the function is defined on the whole Z: If n<0, then a(n) = A004488(a(-n)) (or equivalently: a(n) = A117968(-n)) and then it holds that a(A117966(n)) = n. - Antti Karttunen, May 19 2008

A254103 Permutation of natural numbers: a(0) = 0, a(2n) = (3a(n))-1, a(2n+1) = floor((3(1+a(n)))/2).

Original entry on oeis.org

0, 1, 2, 3, 5, 4, 8, 6, 14, 9, 11, 7, 23, 13, 17, 10, 41, 22, 26, 15, 32, 18, 20, 12, 68, 36, 38, 21, 50, 27, 29, 16, 122, 63, 65, 34, 77, 40, 44, 24, 95, 49, 53, 28, 59, 31, 35, 19, 203, 103, 107, 55, 113, 58, 62, 33, 149, 76, 80, 42, 86, 45, 47, 25, 365, 184, 188, 96, 194, 99, 101, 52, 230, 117, 119, 61, 131, 67, 71, 37, 284, 144, 146, 75, 158, 81, 83, 43

Offset: 0

Antti Karttunen, Jan 25 2015

nonn

This sequence can be represented as a binary tree. Each child to the left is obtained by multiplying the parent by three and subtracting one, and each child to the right is obtained by adding one to parent, multiplying by three, and then halving the result (discarding a possible remainder):
                                     0
                                     |
                  ...................1...................
                 2                                       3
       5......../ \........4                   8......../ \........6
      / \                 / \                 / \                 / \
     /   \               /   \               /   \               /   \
    /     \             /     \             /     \             /     \
  14       9          11       7          23       13         17       10
41  22   26 15      32  18   20 12      68  36   38  21     50  27   29  16
etc.

Antti Karttunen, Table of n, a(n) for n = 0..8191
Index entries for sequences that are permutations of the natural numbers

Inverse: A254104.
Cf. A007051, A016789, A032766, A140263, A191450, A246207.
Similar permutations: A048673, A183209.

def a(n):
    if n==0: return 0
    if n%2==0: return 3*a(n//2) - 1
    else: return int((3*(1 + a((n - 1)//2)))/2)
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 06 2017

a(0) = 0, a(2n) = A016789(a(n)-1), a(2n+1) = A032766(1+a(n)).
a(0) = 0, a(2n) = (3*a(n))-1, a(2n+1) = floor((3*(1+a(n)))/2).
Other identities:
a(2^n) = A007051(n) for all n >= 0. [A property shared with A048673 and A183209.]

A117968 Negative part of inverse of A117966; write -n in balanced ternary and then replace (-1)'s with 2's.

Original entry on oeis.org

2, 7, 6, 8, 22, 21, 23, 19, 18, 20, 25, 24, 26, 67, 66, 68, 64, 63, 65, 70, 69, 71, 58, 57, 59, 55, 54, 56, 61, 60, 62, 76, 75, 77, 73, 72, 74, 79, 78, 80, 202, 201, 203, 199, 198, 200, 205, 204, 206, 193, 192, 194, 190, 189, 191, 196, 195, 197, 211, 210, 212, 208, 207

Offset: 1

Franklin T. Adams-Watters, Apr 05 2006

			-7 in balanced ternary is (-1)1(-1), changing to 212 ternary is 23, so a(7)=23.

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 2, pp. 173-175

Indranil Ghosh, Table of n, a(n) for n = 1..6561
Ken Levasseur, The Balanced Ternary Number System

Cf. A117966. a(n) = A004488(A117967(n)). Bisection of A140263. A140268 gives the same sequence in ternary.

def a(n):
    if n==1: return 2
    if n%3==0: return 3*a(n//3)
    elif n%3==1: return 3*a((n - 1)//3) + 2
    else: return 3*a((n + 1)//3) + 1
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Jun 06 2017

a(1) = 2, a(3n) = 3a(n), a(3n+1) = 3a(n)+2, a(3n-1) = 3a(n)+1.

A246207 Permutation of nonnegative integers: a(0) = 0, a(1) = 1, a(2n) = A117968(a(n)), a(2n+1) = A117967(1+a(n)).

Original entry on oeis.org

0, 1, 2, 5, 7, 3, 22, 15, 23, 11, 6, 4, 71, 35, 66, 52, 58, 33, 25, 12, 21, 16, 8, 17, 172, 99, 73, 36, 213, 148, 194, 137, 197, 152, 75, 43, 59, 29, 24, 13, 69, 49, 68, 47, 19, 9, 64, 45, 587, 419, 225, 127, 173, 104, 72, 37, 516, 304, 620, 431, 643, 447, 601, 462, 640, 441, 577, 423, 177, 103, 203, 155, 211, 150, 61, 30, 57, 34, 26, 53

Offset: 0

Antti Karttunen, Aug 19 2014

This is an instance of entanglement permutation, where complementary pair A005843/A005408 (even and odd numbers respectively) is entangled with complementary pair A117968/A117967 (negative and positive part of inverse of balanced ternary enumeration of integers, respectively), with a(0) set to 0 and a(1) set to 1.

Thus this shares with A140263 the property that after a(0)=0, the even positions contain only terms of A117968 and the odd positions contain only terms of A117967.

Antti Karttunen, Table of n, a(n) for n = 0..8191
Antti Karttunen, Pin & logarithmic scatter plots computed for range 0..2047 only (computed with OEIS "graph" command)
Index entries for sequences that are permutations of the natural numbers

Inverse: A246208.
Related permutations: A140263, A054429, A246209, A246211.
Cf. A117967, A117968.

from sympy.ntheory.factor_ import digits
def a004488(n): return int("".join([str((3 - i)%3) for i in digits(n, 3)[1:]]), 3)
def a117968(n):
    if n==1: return 2
    if n%3==0: return 3*a117968(n/3)
    elif n%3==1: return 3*a117968((n - 1)/3) + 2
    else: return 3*a117968((n + 1)/3) + 1
def a117967(n): return 0 if n==0 else a117968(-n) if n<0 else a004488(a117968(n))
def a(n): return n if n<2 else a117968(a(n/2)) if n%2==0 else a117967(1 + a((n - 1)/2)) # Indranil Ghosh, Jun 07 2017

As a composition of related permutations:
a(n) = A246209(A054429(n)).
a(n) = A246211(A246209(n)).

cp's OEIS Frontend

A140264 Inverse permutation to A140263.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Scheme

Formula

A140265 Permutation of natural numbers: a(n) = A140263(n-1)+1.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Scheme

A263273 Bijective base-3 reverse: a(0) = 0; for n >= 1, a(n) = A030102(A038502(n)) * A038500(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Scheme

Formula

A117967 Positive part of inverse of A117966; write n in balanced ternary and then replace (-1)'s with 2's.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

Scheme

Formula

A254103 Permutation of natural numbers: a(0) = 0, a(2n) = (3*a(n))-1, a(2n+1) = floor((3*(1+a(n)))/2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Formula

A117968 Negative part of inverse of A117966; write -n in balanced ternary and then replace (-1)'s with 2's.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Python

Formula

A246207 Permutation of nonnegative integers: a(0) = 0, a(1) = 1, a(2n) = A117968(a(n)), a(2n+1) = A117967(1+a(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Formula

A254103 Permutation of natural numbers: a(0) = 0, a(2n) = (3a(n))-1, a(2n+1) = floor((3(1+a(n)))/2).