A162910 -id:A162910 - cp's OEIS frontend

A233280 Permutation of nonnegative integers: a(n) = A003188(A054429(n)).

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

Offset: 0

Antti Karttunen, Dec 18 2013

nonn

This permutation transforms the enumeration system of positive irreducible fractions A071766/A229742 (HCS) into the enumeration system A007305/A047679 (Stern-Brocot), and the enumeration system A245325/A245326 into A162909/A162910 (Bird). - Yosu Yurramendi, Jun 09 2015

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

Inverse permutation: A233279.
Cf. A000069, A001969, A003188, A054429, A063946, A154436.
Similarly constructed permutation pairs: A003188/A006068, A135141/A227413, A232751/A232752, A233275/A233276, A233277/A233278, A193231 (self-inverse).

from sympy import floor
def a003188(n): return n^(n>>1)
def a054429(n): return 1 if n==1 else 2*a054429(floor(n/2)) + 1 - n%2
def a(n): return 0 if n==0 else a003188(a054429(n)) # Indranil Ghosh, Jun 11 2017

maxrow <- 8 # by choice
a <- 1
for(m in 0:maxrow) for(k in 0:(2^m-1)){
a[2^(m+1)+    k] <- a[2^m+      k] + 2^m
a[2^(m+1)+2^m+k] <- a[2^(m+1)-1-k] + 2^(m+1)
}
a
# Yosu Yurramendi, Apr 05 2017

(define (A233280 n) (A003188 (A054429 n)))
;; Alternative version, based on entangling even & odd numbers with odious and evil numbers:
(definec (A233280 n) (cond ((< n 2) n) ((even? n) (A000069 (+ 1 (A233280 (/ n 2))))) (else (A001969 (+ 1 (A233280 (/ (- n 1) 2)))))))

a(n) = A003188(A054429(n)).
a(n) = A063946(A003188(n)).
a(n) = A054429(A154436(n)).
a(0)=0, a(1)=1, and otherwise, a(2n) = A000069(1+a(n)), a(2n+1) = A001969(1+a(n)). [A recurrence based on entangling even & odd numbers with odious and evil numbers]
a(n) = A258746(A180201(n)) = A180201(A117120(n)), n > 0. - Yosu Yurramendi, Apr 10 2017

A052913 a(n+2) = 5a(n+1) - 2a(n), with a(0) = 1, a(1) = 4.

Original entry on oeis.org

1, 4, 18, 82, 374, 1706, 7782, 35498, 161926, 738634, 3369318, 15369322, 70107974, 319801226, 1458790182, 6654348458, 30354161926, 138462112714, 631602239718, 2881086973162, 13142230386374, 59948977985546, 273460429154982, 1247404189803818, 5690100090709126

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Main diagonal of the array: m(1,j)=3^(j-1), m(i,1)=1; m(i,j) = m(i-1,j) + m(i,j-1): 1 3 9 27 81 ... / 1 4 13 40 ... / 1 5 18 58 ... / 1 6 24 82 ... - Benoit Cloitre, Aug 05 2002
a(n) is also the number of 3 X n matrices of integers for which the upper-left hand corner is a 1, the rows and columns are weakly increasing, and two adjacent entries differ by at most 1. - Richard Stanley, Jun 06 2010
a(n) is the number of compositions of n when there are 4 types of 1 and 2 types of other natural numbers. - Milan Janjic, Aug 13 2010
If a Stern's sequence based enumeration system of positive irreducible fractions is considered (for example, A007305/A047679, or A162909/A162910, or A071766/A229742, or A245325/A245326, ...), and if it is organized by blocks or levels (n) with 2^n terms (n>=0), and the products numerator*denominator, term by term, are summed at each level n, then the resulting sequence of integers is a(n). - Yosu Yurramendi, May 23 2015
Number of 1’s in the substitution system {0 -> 110, 1 -> 11110} at step n from initial string "1" (1 -> 11110 -> 11110111101111011110110 -> ...) . - Ilya Gutkovskiy, Apr 10 2017

G. C. Greubel, Table of n, a(n) for n = 0..1000
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 894
J.-C. Novelli, J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962 [math.CO], 2014.
Index entries for linear recurrences with constant coefficients, signature (5,-2).

Cf. A007482 (inverse binomial transform).

a:=[1,4];; for n in [3..30] do a[n]:=5*a[n-1]-2*a[n-2]; od; a; # G. C. Greubel, Oct 16 2019

I:=[1,4]; [n le 2 select I[n] else 5*Self(n-1)-2*Self(n-2): n in [1..35]]; // Vincenzo Librandi, May 24 2015

R:=PowerSeriesRing(Integers(), 25); Coefficients(R!((1-x)/(1-5*x+2*x^2))); // Marius A. Burtea, Oct 16 2019

spec := [S,{S=Sequence(Union(Prod(Sequence(Z),Union(Z,Z)),Z,Z))},unlabeled]: seq(combstruct[count](spec,size=n), n=0..20);
seq(coeff(series((1-x)/(1-5*x+2*x^2), x, n+1), x, n), n = 0..30); # G. C. Greubel, Oct 16 2019

Transpose[NestList[{Last[#],5Last[#]-2First[#]}&, {1,4},20]][[1]] (* Harvey P. Dale, Mar 12 2011 *)
LinearRecurrence[{5, -2}, {1, 4}, 25] (* Jean-François Alcover, Jan 08 2019 *)

Vec((1-x)/(1-5*x+2*x^2) + O(x^30)) \\ Michel Marcus, Mar 05 2015

def A052913_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P((1-x)/(1-5*x+2*x^2)).list()
A052913_list(30) # G. C. Greubel, Oct 16 2019

G.f.: (1-x)/(1-5*x+2*x^2).
a(n) = Sum_{alpha=RootOf(1 - 5*z + 2*z^2)} (1/17)*(3+alpha)*alpha^(-1-n).
a(n) = ((17+3*sqrt(17))/34)*((5+sqrt(17))/2)^n + ((17-3*sqrt(17))/34)*((5-sqrt(17))/2)^n. - N. J. A. Sloane, Jun 03 2002
a(n) = A107839(n) - A107839(n-1). - R. J. Mathar, May 21 2015
a(n) = 2*A020698(n-1), n>1. - R. J. Mathar, Nov 23 2015
E.g.f.: (1/17)*exp(5*x/2)*(17*cosh(sqrt(17)*x/2) + 3*sqrt(17)*sinh(sqrt(17)*x/2)). - Stefano Spezia, Oct 16 2019
a(n) = 3*A107839(n-1) + (-1)^n*A152594(n) with A107839(-1) = 0. - Klaus Purath, Jul 29 2020

Typo in definition corrected by Bruno Berselli, Jun 07 2010

A180201 Inverse permutation to A180200.

Original entry on oeis.org

0, 1, 2, 3, 5, 4, 6, 7, 11, 10, 8, 9, 13, 12, 14, 15, 23, 22, 20, 21, 17, 16, 18, 19, 27, 26, 24, 25, 29, 28, 30, 31, 47, 46, 44, 45, 41, 40, 42, 43, 35, 34, 32, 33, 37, 36, 38, 39, 55, 54, 52, 53, 49, 48, 50, 51, 59, 58, 56, 57, 61, 60, 62, 63, 95, 94, 92, 93, 89, 88, 90, 91, 83

Offset: 0

Reinhard Zumkeller, Aug 15 2010

A180199(n) = a(a(n));
a(A180198(n)) = A180198(a(n)) = A180200(n);
a(A075427(n)) = A075427(n).
This permutation transforms the enumeration system of positive irreducible fractions A245325/A245326 into the enumeration system A007305/A047679 (Stern-Brocot), and enumeration system A071766/A229742 (HCS) into A162909/A162910 (Bird). - Yosu Yurramendi, Jun 09 2015

Index entries for sequences that are permutations of the natural numbers

#
maxn <- 63 # by choice
a <- 1
for(n in 1:maxn){
a[2*n  ] <- 2*a[n] + (n%%2 == 0)
a[2*n+1] <- 2*a[n] + (n%%2 != 0)}
a <- c(0, a)
# Yosu Yurramendi, May 23 2020

a(n) = A233280(A258746(n)) = A117120(A233280(n)), n > 0. - Yosu Yurramendi, Apr 10 2017 [Corrected by Yosu Yurramendi, Mar 14 2025]
a(0) = 0, a(1) = 1, for n > 0 a(2*n) = 2*a(n) + [n even], a(2*n + 1) = 2*a(n) + [n odd]. - Yosu Yurramendi, May 23 2020
From Alan Michael Gómez Calderón, Mar 04 2025: (Start)
a(n) = A054429(n) XOR floor(n/2) for n > 0.
a(n) = A054429(A003188(n)) for n > 0. (End)
a(n) = A154436(A054429(n)), n > 0. - Yosu Yurramendi, Mar 11 2025

A273494 a(n) = A245325(n) + A245326(n).

Original entry on oeis.org

2, 3, 3, 5, 4, 5, 4, 8, 7, 7, 5, 8, 7, 7, 5, 13, 11, 12, 9, 11, 10, 9, 6, 13, 11, 12, 9, 11, 10, 9, 6, 21, 18, 19, 14, 19, 17, 16, 11, 18, 15, 17, 13, 14, 13, 11, 7, 21, 18, 19, 14, 19, 17, 16, 11, 18, 15, 17, 13, 14, 13, 11, 7, 34, 29, 31, 23, 30, 27, 25, 17, 31, 26, 29, 22, 25, 23, 20, 13, 29, 25, 26, 19, 27, 24, 23, 16, 23

Offset: 1

Yosu Yurramendi, May 23 2016

nonn

The terms (n>0) may be written as a left-justified array with rows of length 2^m, m >= 0:
   2,
   3, 3,
   5, 4, 5, 4,
   8, 7, 7, 5, 8, 7, 7, 5,
  13,11,12, 9,11,10, 9, 6,13,11,12, 9,11,10, 9, 6,
  21,18,19,14,19,17,16,11,18,15,17,13,14,13,11, 7,21,18,19,14,19,17,...
All columns have the Fibonacci sequence property: a(2^(m+2) + k) = a(2^(m+1) + k) + a(2^m + k), m >= 0, 0 <= k < 2^m (empirical observations).
The terms (n>0) may also be written as a right-justified array with rows of length 2^m, m >= 0:
                                                                           2,
                                                                        3, 3,
                                                                  5, 4, 5, 4,
                                                      8, 7, 7, 5, 8, 7, 7, 5,
                             13,11,12, 9,11,10, 9, 6,13,11,12, 9,11,10, 9, 6,
..., 18,15,17,13,14,13,11, 7,21,18,19,14,19,17,16,11,18,15,17,13,14,13,11, 7,
Each column is an arithmetic sequence. The differences of the arithmetic sequences give the sequence A071585: a(2^(m+1)-1-k) - a(2^m-1-k) = A071585(k), m >= 0, 0 <= k < 2^m.
n > 1 occurs in this sequence phi(n) = A000010(n) times, as it occurs in A007306 (Franklin T. Adams-Watters's comment), which is the sequence obtained by adding numerator and denominator in the Calkin-Wilf enumeration system of positive rationals. A245325(n)/A245326(n) is also an enumeration system of all positive rationals, and in each level m >= 0 (ranks between 2^m and 2^(m+1)-1) rationals are the same in both systems. Thus a(n) has the same terms in each level as A007306.
The same property occurs in all numerator+denominator sequences of enumeration systems of positive rationals, as, for example, A007306 (A007305+A047679), A071585 (A229742+A071766), A086592 (A020650+A020651), A268087 (A162909+A162910).

Yosu Yurramendi, Table of n, a(n) for n = 1..4095

Cf. A007306, A268087, A071585, A086592, A273493

a(n) = my(x=1, y=1); for(i=0, logint(n, 2), if(bittest(n, i), [x, y]=[x+y, y], [x, y]=[y, x+y])); x \\ Mikhail Kurkov, Mar 10 2023

a(n) = A273493(A059893(n)), a(A059893(n)) = A273493(n), n > 0. - Yosu Yurramendi, May 30 2017

a(n) = A007306(A059893(A180200(n))) = A007306(A059894(A154435(n))). - Yosu Yurramendi, Sep 20 2021

A368734 Four-column table read by rows where row n lists the entries of the 2 X 2 matrix M(n) used to form Bird tree and Drib tree rationals.

Original entry on oeis.org

1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 2, 1, 2, 0, 1, 1, 0, 2, 1, 2, 1, 1, 1, 1, 2, 2, 3, 2, 3, 1, 1, 0, 1, 1, 3, 1, 3, 1, 2, 2, 1, 3, 1, 3, 1, 1, 0, 1, 1, 3, 2, 3, 2, 2, 1, 2, 3, 3, 5, 3, 5, 1, 2, 1, 1, 3, 4, 3, 4, 2, 3, 1, 3, 1, 4, 1, 4, 0, 1, 1, 2, 2, 5

Offset: 1

Philippe Deléham, Jan 04 2024

Row n is x(n), y(n), z(n), t(n) and the matrix is M(n) = [x(n), y(n) ; z(n), t(n)].
Bird tree rationals are formed by multiplication on the right of a row vector [1,1]*M(n) = [A162909(n), A162910(n)].
Drib tree rationals are formed by multiplication on the left of a column vector M(n)*[1;1] = [A162911(n), A162912(n)].
The two matrix rows f(n) = (x(n), y(n)) and g(n) = (z(n), t(n)) start f(1) = (1,0) and g(1) = (0,1) and then satisfy f(2*n) = g(n); g(2*n) = f(2*n+1) = f(n) + g(n); g(2*n+1) = f(n).
If the terms x(n), y(n), z(n) or t(n) are written as an array (left-aligned fashion) with rows of length 2^m, m = 0; 1, 2, 3, ... then each column k is a Fibonacci-type sequence.
For x(n):
  1;
  0, 1;
  1, 1, 1, 2;
  1, 2, 0, 1, 2, 3, 1, 3;
  2, 3, 1, 3, 1, 1, 1, 2, 3, 5, 1, 4, 3, 4, 2, 5;
  ...
For y(n):
  0;
  1, 1;
  1, 2, 0, 1;
  2, 3, 1, 3, 1, 1, 1, 2;
  3, 5, 1, 4, 3, 4, 2, 5, 1, 2, 0, 1, 2, 3, 1, 3;
  ...
For z(n):
  0;
  1, 1;
  1, 0, 2, 1;
  2, 1, 1, 1, 3, 1, 3, 2;
  3, 1, 3, 2, 1, 0, 2, 1, 5, 2, 4, 3, 4, 1, 5, 3;
  ...
For t(n):
  1;
  1, 0;
  2, 1, 1, 1;
  3, 1, 3, 2, 1, 0, 2, 1;
  5, 2, 4, 3, 4, 1, 5, 3, 2, 1, 1, 1, 3, 1, 3, 2;
  ...

			The table begins:
     |    f(n)   |    g(n)
  n  | x(n)| y(n)| z(n)| t(n)
  1  |  1  |  0  |  0  |  1
  2  |  0  |  1  |  1  |  1
  3  |  1  |  1  |  1  |  0
  4  |  1  |  1  |  1  |  2
  5  |  1  |  2  |  0  |  1
  6  |  1  |  0  |  2  |  1
  7  |  2  |  1  |  1  |  1
.
For n >= 1, f(n) = {(1,0); (0,1); (1,1); (1,1); (1,2); (1,0); ...}.
For n >= 1, g(n) = {(0,1); (1,1); (1,0); (1,2); (0,1); (2,1); ...}.
M(38) = [2, 3; 5, 7] ; Det(M(38)) = 2*7-3*5 = -1; 2+5 = 7 = A162909(38); 3+7 = 10 = A162910(38); 2+3 = 5 = A162911(38); 5+7 = 12 = A162912(38).

Cf. A000045, A054429, A122872, A162909, A162910, A162911, A162912.

x(n) + z(n) = A162909(n).
y(n) + t(n) = A162910(n).
x(n) + y(n) = A162911(n).
z(n) + t(n) = A162912(n).
Det(M(n)) = (-1)^p if 2^p <= n < 2^(p+1).
x(A054429(n)) = t(n).
y(A054429(n)) = z(n).
z(A054429(n)) = y(n).
t(A054429(n)) = x(n).
M(k)*M(n) = M(A122872(n,k)).
M(2^n) = [F(n-1), F(n); F(n), F(n+1)], F(n) = Fibonacci(n) = A000045(n).

cp's OEIS Frontend

A233280 Permutation of nonnegative integers: a(n) = A003188(A054429(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

R

Scheme

Formula

A052913 a(n+2) = 5*a(n+1) - 2*a(n), with a(0) = 1, a(1) = 4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A180201 Inverse permutation to A180200.

Views

Author

Keywords

Comments

Links

Programs

R

Formula

A273494 a(n) = A245325(n) + A245326(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A368734 Four-column table read by rows where row n lists the entries of the 2 X 2 matrix M(n) used to form Bird tree and Drib tree rationals.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A052913 a(n+2) = 5a(n+1) - 2a(n), with a(0) = 1, a(1) = 4.