A054238 -id:A054238 - cp's OEIS frontend

A163904 Array A(i,j): Cycle size of each A054238(i,j) in permutation A163355, listed antidiagonally as A(0,0), A(0,1), A(1,0), A(0,2), A(1,1), A(2,0), ...

1, 1, 2, 6, 2, 6, 3, 3, 6, 3, 1, 6, 6, 3, 4, 3, 3, 3, 6, 8, 8, 1, 3, 4, 3, 4, 4, 2, 1, 2, 2, 2, 2, 2, 2, 2, 6, 2, 4, 4, 4, 4, 8, 2, 6, 6, 6, 2, 4, 4, 8, 8, 4, 6, 6, 12, 6, 12, 2, 4, 8, 4, 4, 12, 6, 18, 6, 6, 12, 6, 2, 4, 8, 4, 6, 12, 18, 6, 3, 12, 18, 6, 9, 2, 2, 8, 6, 6, 12, 18, 3, 3, 6, 18, 18

Offset: 0

Antti Karttunen, Sep 19 2009

			The top left 8x8 corner of this array:
1 1 6 3 1 3 1 1
2 2 3 6 3 3 2 2
6 6 6 3 4 2 4 2
3 3 6 3 2 4 4 2
4 8 4 2 4 4 4 2
8 4 2 4 8 8 4 2
2 2 8 8 4 8 2 2
2 2 4 4 4 8 2 2

A. Karttunen, Table of n, a(n) for n = 0..32895

a(n) = A163890(A054238(n)) = A163890(A163357(n)). Positions of 1's: A165403. See also A163898, A163899.

A054239 Inverse of A054238.

Original entry on oeis.org

0, 1, 2, 4, 3, 6, 7, 11, 5, 8, 9, 13, 12, 17, 18, 24, 10, 15, 16, 22, 21, 28, 29, 37, 23, 30, 31, 39, 38, 47, 48, 58, 14, 19, 20, 26, 25, 32, 33, 41, 27, 34, 35, 43, 42, 51, 52, 62, 40, 49, 50, 60, 59, 70, 71, 83, 61, 72, 73, 85, 84, 97, 98, 112, 36, 45, 46, 56, 55, 66, 67, 79

Offset: 0

Marc LeBrun, Feb 07 2000

Transforms binary-interleaved pair numbers into diagonal pair numbers.

			a(3)=4 so A054238(4)=3.

Index entries for sequences that are permutations of the natural numbers

Inverse of A054238.

A072634 Permutation of natural numbers induced by reranking plane binary trees given in the standard lexicographic order (A014486) with an "arithmetic global ranking algorithm", using A054238 as the pairing function N X N -> N.

Original entry on oeis.org

0, 1, 3, 2, 11, 9, 4, 6, 5, 139, 131, 33, 41, 35, 12, 10, 8, 70, 66, 7, 17, 21, 18, 32907, 32779, 2051, 2179, 2059, 161, 137, 129, 8233, 8201, 43, 515, 547, 521, 140, 132, 34, 42, 36, 16, 14, 72, 16454, 16390, 68, 1026, 1090, 1030, 15, 13, 19, 81, 69, 23, 65

Offset: 0

Antti Karttunen, Jun 02 2002

nonn

Antti Karttunen, Alternative Catalan Orderings
Index entries for sequences that are permutations of the natural numbers

Inverse permutation: A072635.
Cf. A014486, A000695, A054238, A071651, A072636, A072646, A072656, A072658, A072644.
Cf. also A296689.

;; Functions below show the essential idea:
(define A072634 (lexrank->arithrank-bijection packA054238))
(define (lexrank->arithrank-bijection packfun) (lambda (n) (rank-bintree (binexp->parenthesization (A014486 n)) packfun)))
(define (rank-bintree bt packfun) (cond ((not (pair? bt)) 0) (else (1+ (packfun (rank-bintree (car bt) packfun) (rank-bintree (cdr bt) packfun))))))
(define (packA054238 x y) (+ (A000695 x) (* 2 (A000695 y))))

A163898 Array A(i,j) giving the square of distance from (i,j) to the location where A054238(i,j) is situated in array A163357(i,j), listed antidiagonally as A(0,0), A(0,1), A(1,0), A(0,2), A(1,1), A(2,0), ...

Original entry on oeis.org

0, 0, 1, 8, 1, 4, 18, 5, 2, 9, 0, 5, 2, 5, 16, 2, 1, 2, 9, 10, 25, 0, 1, 4, 9, 16, 17, 36, 0, 1, 4, 9, 16, 25, 36, 49, 128, 1, 2, 1, 10, 9, 10, 25, 64, 162, 113, 4, 5, 18, 5, 4, 5, 50, 81, 128, 113, 100, 9, 10, 5, 10, 1, 64, 65, 100, 128, 113, 100, 89, 16, 17, 20, 25, 64, 81, 100

Offset: 0

Antti Karttunen, Sep 19 2009

			The top left 8 X 8 corner of this array:
   0  0  8 18  0  2  0  0
   1  1  5  5  1  1  1  1
   4  2  2  2  4  4  2  4
   9  5  9  9  9  1  5  9
  16 10 16 16 10 18 10 16
  25 17 25  9  5  5 17 25
  36 36 10  4 10 20 36 36
  49 25  5  1 25 29 25 49

A. Karttunen, Table of n, a(n) for n = 0..32895

a(n) = A163900(A054238(n)). Positions of zeros: A165403. See also A163899, A163904.

A163899 Array A(i,j) giving the square of distance from (i,j) to the location where A163357(i,j) is situated in array A054238(i,j), listed antidiagonally as A(0,0), A(0,1), A(1,0), A(0,2), A(1,1), A(2,0), ...

Original entry on oeis.org

0, 0, 1, 9, 1, 8, 9, 2, 5, 18, 0, 2, 4, 5, 25, 1, 2, 5, 2, 20, 29, 0, 1, 5, 9, 17, 10, 36, 0, 1, 4, 9, 16, 25, 36, 49, 225, 1, 4, 2, 16, 10, 5, 25, 128, 225, 170, 4, 1, 17, 10, 5, 18, 113, 162, 196, 170, 125, 9, 16, 25, 5, 10, 128, 113, 149, 225, 170, 125, 90, 16, 9, 4, 1, 128

Offset: 0

Antti Karttunen, Sep 19 2009

			The top left 8x8 corner of this array:
+0 +0 +9 +9 +0 +1 +0 +0
+1 +1 +2 +2 +2 +1 +1 +1
+8 +5 +4 +5 +5 +4 +4 +4
18 +5 +2 +9 +9 +2 +1 +9
25 20 17 16 16 17 16 16
29 10 25 10 10 25 +9 25
36 36 +5 +5 +5 +4 36 36
49 25 18 10 +1 10 25 49

A. Karttunen, Table of n, a(n) for n = 0..32895

a(n) = A163900(A163357(n)). Positions of zeros: A165403. See also A163898, A163904.

A163900 Squared distance between n's location in A054238 array and A163357 array.

Original entry on oeis.org

0, 0, 1, 1, 8, 18, 5, 5, 4, 2, 9, 5, 2, 2, 9, 9, 0, 2, 1, 1, 0, 0, 1, 1, 4, 4, 9, 1, 2, 4, 5, 9, 16, 10, 25, 17, 16, 16, 25, 9, 36, 36, 49, 25, 10, 4, 5, 1, 10, 18, 5, 5, 10, 16, 17, 25, 10, 20, 25, 29, 36, 36, 25, 49, 128, 162, 113, 113, 128, 128, 113, 145, 100, 100, 89, 113, 162

Offset: 0

Antti Karttunen, Sep 19 2009

nonn

A. Karttunen, Table of n, a(n) for n = 0..65535

Positions of zeros: A163901. See also A163898, A163899.

a(n) = A000290(abs(A059906(n)-A059252(n))) + A000290(abs(A059905(n)-A059253(n))).

A072793 Simple tabular N X N -> N bijection: first interleave the bits as with A054238, then apply the bijection A048680.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 8, 12, 11, 17, 13, 14, 15, 19, 20, 22, 23, 16, 25, 18, 33, 24, 38, 26, 27, 28, 30, 31, 40, 41, 43, 44, 21, 46, 32, 51, 29, 67, 45, 72, 34, 35, 36, 53, 54, 48, 49, 74, 75, 56, 57, 37, 59, 39, 88, 50, 80, 52, 122, 58, 93, 60, 61, 62, 64, 65, 82, 83

Offset: 0

Antti Karttunen, Jun 12 2002

Index entries for sequences that are permutations of the natural numbers

Inverse: A072794. Composition of A048680 & A054238. The X-projection: A072661, The Y-projection: A072662. Used in global arithmetic ranking scheme presented in A072656.

A346453 The array in A054238 read by upward antidiagonals.

Original entry on oeis.org

0, 2, 1, 8, 3, 4, 10, 9, 6, 5, 32, 11, 12, 7, 16, 34, 33, 14, 13, 18, 17, 40, 35, 36, 15, 24, 19, 20, 42, 41, 38, 37, 26, 25, 22, 21, 128, 43, 44, 39, 48, 27, 28, 23, 64, 130, 129, 46, 45, 50, 49, 30, 29, 66, 65, 136, 131, 132, 47, 56, 51, 52, 31, 72, 67, 68

Offset: 0

Jasper Brown, Jul 19 2021

See A054238 for further information.

			The top left corner of the array is:
   0  1  4  5 16 17 20 21
   2  3  6  7 18 19 22 23
   8  9 12 13 24 25 28 29
  10 11 14 15 26 27 30 31
  32 33 36 37 48 49 52 53
  34 35 38 39 50 51 54 55
  40 41 44 45 56 57 60 61
  42 43 46 47 58 59 62 63

Cf. A054238 (by downward antidiagonals).

A073200 Number of simple Catalan bijections of type B.

Original entry on oeis.org

0, 1, 0, 3, 1, 0, 2, 2, 1, 0, 7, 3, 3, 1, 0, 8, 4, 2, 3, 1, 0, 6, 6, 8, 2, 3, 1, 0, 4, 5, 7, 7, 2, 3, 1, 0, 5, 7, 6, 6, 8, 2, 3, 1, 0, 17, 8, 5, 8, 7, 7, 2, 2, 1, 0, 18, 9, 4, 4, 6, 8, 7, 3, 3, 1, 0, 20, 10, 22, 5, 5, 5, 8, 4, 2, 2, 1, 0, 21, 14, 21, 17, 4, 4, 6, 5, 8, 3, 3, 1, 0

Offset: 0

Antti Karttunen, Jun 25 2002

Each row is a permutation of nonnegative integers induced by a Catalan bijection (constructed as explained below) acting on the parenthesizations/plane binary trees as encoded and ordered by A014486/A063171.
The construction process is akin to the constructive mapping of primitive recursive functions to N: we have two basic primitives, A069770 (row 0) and A072796 (row 1), of which the former swaps the left and the right subtree of a binary tree and the latter exchanges the positions of the two leftmost subtrees of plane general trees, unless the tree's degree is less than 2, in which case it just fixes it. From then on, the even rows are constructed recursively from any other Catalan bijection in this table, using one of the five allowed recursion types:
0 - Apply the given Catalan bijection and then recurse down to both subtrees of the new binary tree obtained. (last decimal digit of row number = 2)
1 - First recurse down to both subtrees of the old binary tree and only after that apply the given Catalan bijection. (last digit = 4)
2 - Apply the given Catalan bijection and then recurse down to the right subtree of the new binary tree obtained. (last digit = 6)
3 - First recurse down to the right subtree of old binary tree and only after that apply the given Catalan bijection. (last digit = 8)
4 - First recurse down to the left subtree of old binary tree, after that apply the given Catalan bijection and then recurse down to the right subtree of the new binary tree. (last digit = 0)
The odd rows > 2 are compositions of the rows 0, 1, 2, 4, 6, 8, ... (i.e. either one of the primitives A069770 or A072796, or one of the recursive compositions) at the left hand side and any Catalan bijection from the same array at the right hand side. See the scheme-functions index-for-recursive-sgtb and index-for-composed-sgtb how to compute the positions of the recursive and ordinary compositions in this table.

A. Karttunen, Gatomorphisms (With the complete source and explanation)

Four other tables giving the corresponding cycle-counts: A073201, counts of the fixed elements: A073202, the lengths of the largest cycles: A073203, the LCM's of all the cycles: A073204. The ordinary compositions are encoded using the N X N -> N bijection A054238 (which in turn uses the bit-interleaving function A000695).
The first 21 rows of this table:.
Row 0: A069770. Row 1: A072796. Row 2: A057163. Row 3: A073269, Row 4: A057163 (duplicate), Row 5: A073270, Row 6: A069767, Row 7: A001477 (identity perm.), Row 8: A069768, Row 9: A073280.
Row 10: A069770 (dupl.), Row 11: A072796 (dupl.), Row 12: A057511, Row 13: A073282, Row 14: A057512, Row 15: A073281, Row 16: A057509, Row 17: A073280 (dupl.), Row 18: A057510, Row 19: A073283, Row 20: A073284.
Other Catalan bijection-induced EIS-permutations which occur in this table. Only the first known occurrence is given. Involutions are marked with *, others paired with their inverse:.
Row 164: A057164*, Row 168: A057508*, Row 179: A072797*.
Row 41: A073286 - Row 69: A073287. Row 105: A073290 - Row 197: A073291. Row 416: A073288 - Row 696: A073289.
Row 261: A057501 - Row 521: A057502. Row 2618: A057503 - Row 5216: A057504. Row 2614: A057505 - Row 5212: A057506.
Row 10435: A073292 - Row ...: A073293. Row 17517: A057161 - Row ...: A057162.
For a more practical enumeration system of (some) Catalan automorphisms see table A089840 and its various "recursive derivations".

A001196 Double-bitters: only even length runs in binary expansion.

Original entry on oeis.org

0, 3, 12, 15, 48, 51, 60, 63, 192, 195, 204, 207, 240, 243, 252, 255, 768, 771, 780, 783, 816, 819, 828, 831, 960, 963, 972, 975, 1008, 1011, 1020, 1023, 3072, 3075, 3084, 3087, 3120, 3123, 3132, 3135, 3264, 3267, 3276, 3279, 3312, 3315, 3324, 3327, 3840, 3843

Offset: 0

N. J. A. Sloane, based on an email from Bart la Bastide (bart(AT)xs4all.nl)

Numbers whose set of base 4 digits is {0,3}. - Ray Chandler, Aug 03 2004
n such that there exists a permutation p_1, ..., p_n of 1, ..., n such that i + p_i is a power of 4 for every i. - Ray Chandler, Aug 03 2004
The first 2^n terms of the sequence could be obtained using the Cantor-like process for the segment [0, 4^n-1]. E.g., for n=1 we have [0, {1, 2}, 3] such that numbers outside of braces are the first 2 terms of the sequence; for n=2 we have [0, {1, 2}, 3, {4, 5, 6, 7, 8, 9, 10, 11}, 12, {13, 14}, 15] such that the numbers outside of braces are the first 4 terms of the sequence, etc. - Vladimir Shevelev, Dec 17 2012
From Emeric Deutsch, Jan 26 2018: (Start)
Also, the indices of the compositions having only even parts. For the definition of the index of a composition, see A298644. For example, 195 is in the sequence since its binary form is 11000011 and the composition [2,4,2] has only even parts. 132 is not in the sequence since its binary form is 10000100 and the composition [1,4,1,2] also has odd parts.
The command c(n) from the Maple program yields the composition having index n. (End)
After the k-th step of generating the Koch snowflake curve, label the edges of the curve consecutively 0..3*4^k-1 starting from a vertex of the originating triangle. a(0), a(1), ... a(2^k-1) are the labels of the edges contained in one edge of the originating triangle. Add 4^k to each label to get the labels for the next edge of the triangle. Compare with A191108 in respect of the Sierpinski arrowhead curve. - Peter Munn, Aug 18 2019

Sean A. Irvine, Table of n, a(n) for n = 0..10000
Robert Baillie and Thomas Schmelzer, Summing Kempner's Curious (Slowly-Convergent) Series, Mathematica Notebook kempnerSums.nb, Wolfram Library Archive, 2008.
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
Ralf Stephan, Table of generating functions. [ps file]
Ralf Stephan, Table of generating functions. [pdf file]
Eric Weisstein's World of Mathematics, Koch Snowflake.
Wikipedia, Koch snowflake.
Index entries for sequences related to binary expansion of n

3 times the Moser-de Bruijn sequence A000695.
Two digits in other bases: A005823, A097252-A097262.
Digit duplication in other bases: A338086, A338754.
Main diagonal of A054238.
Cf. A191108.

int a_next(int a_n) { int t = a_n << 1; return a_n ^ t ^ (t + 3); } /* Falk Hüffner, Jan 24 2022 */

a001196 n = if n == 0 then 0 else 4 * a001196 n' + 3 * b
            where (n',b) = divMod n 2
-- Reinhard Zumkeller, Feb 21 2014

Runs := proc (L) local j, r, i, k: j := 1: r[j] := L[1]: for i from 2 to nops(L) do if L[i] = L[i-1] then r[j] := r[j], L[i] else j := j+1: r[j] := L[i] end if end do: [seq([r[k]], k = 1 .. j)] end proc: RunLengths := proc (L) map(nops, Runs(L)) end proc: c := proc (n) ListTools:-Reverse(convert(n, base, 2)): RunLengths(%) end proc: A := {}: for n to 3350 do if type(product(1+c(n)[j], j = 1 .. nops(c(n))), odd) = true then A := `union`(A, {n}) else  end if end do: A; # most of the Maple  program is due to W. Edwin Clark. - Emeric Deutsch, Jan 26 2018
# second Maple program:
a:= proc(n) option remember;
     `if`(n<2, 3*n, 4*a(iquo(n, 2, 'r'))+3*r)
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Jan 24 2022

fQ[n_] := Union@ Mod[Length@# & /@ Split@ IntegerDigits[n, 2], 2] == {0}; Select[ Range@ 10000, fQ] (* Or *)
fQ[n_] := Union@ Join[IntegerDigits[n, 4], {0, 3}] == {0, 3}; Select[ Range@ 10000, fQ] (* Robert G. Wilson v, Dec 24 2012 *)

a(n) = 3*fromdigits(binary(n),4); \\ Kevin Ryde, Nov 07 2020

def inA001196(n):
    while n != 0:
        if n%4 == 1 or n%4 == 2:
            return 0
        n = n//4
    return 1
n, a = 0, 0
while n < 20:
    if inA001196(a):
        print(n,a)
        n = n+1
    a = a+1 # A.H.M. Smeets, Aug 19 2019

from itertools import groupby
def ok2lb(n):
  if n == 0: return True  # by convention
  return all(len(list(g))%2 == 0 for k, g in groupby(bin(n)[2:]))
print([i for i in range(3313) if ok2lb(i)]) # Michael S. Branicky, Jan 04 2021

def A001196(n): return 3*int(bin(n)[2:],4) # Chai Wah Wu, Aug 21 2023

a(2n) = 4*a(n), a(2n+1) = 4*a(n) + 3.
a(n) = 3 * A000695(n).
Sum_{n>=1} 1/a(n) = 0.628725478158702414849086504025451177643560169366348272891020450593453403709... (calculated using Baillie and Schmelzer's kempnerSums.nb, see Links). - Amiram Eldar, Feb 12 2022

cp's OEIS Frontend

A163904 Array A(i,j): Cycle size of each A054238(i,j) in permutation A163355, listed antidiagonally as A(0,0), A(0,1), A(1,0), A(0,2), A(1,1), A(2,0), ...

Views

Author

Keywords

Examples

Links

Crossrefs

A054239 Inverse of A054238.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A072634 Permutation of natural numbers induced by reranking plane binary trees given in the standard lexicographic order (A014486) with an "arithmetic global ranking algorithm", using A054238 as the pairing function N X N -> N.

Views

Author

Keywords

Links

Crossrefs

Programs

Scheme

A163898 Array A(i,j) giving the square of distance from (i,j) to the location where A054238(i,j) is situated in array A163357(i,j), listed antidiagonally as A(0,0), A(0,1), A(1,0), A(0,2), A(1,1), A(2,0), ...

Views

Author

Keywords

Examples

Links

Crossrefs

A163899 Array A(i,j) giving the square of distance from (i,j) to the location where A163357(i,j) is situated in array A054238(i,j), listed antidiagonally as A(0,0), A(0,1), A(1,0), A(0,2), A(1,1), A(2,0), ...

Views

Author

Keywords

Examples

Links

Crossrefs

A163900 Squared distance between n's location in A054238 array and A163357 array.

Views

Author

Keywords

Links

Crossrefs

Formula

A072793 Simple tabular N X N -> N bijection: first interleave the bits as with A054238, then apply the bijection A048680.

Views

Author

Keywords

Links

Crossrefs

A346453 The array in A054238 read by upward antidiagonals.

Views

Author

Keywords

Comments

Examples

Crossrefs

A073200 Number of simple Catalan bijections of type B.

Views

Author

Keywords

Comments

Links

Crossrefs

A001196 Double-bitters: only even length runs in binary expansion.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

C

Haskell

Maple

Mathematica

PARI

Python

Python