A020651 -id:A020651 - cp's OEIS frontend

Previous Showing 11-20 of 21 results. Next

A086592 Denominators in left-hand half of Kepler's tree of fractions.

2, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 7, 7, 8, 8, 6, 6, 9, 9, 10, 10, 11, 11, 9, 9, 12, 12, 11, 11, 13, 13, 7, 7, 11, 11, 13, 13, 14, 14, 13, 13, 17, 17, 15, 15, 18, 18, 11, 11, 16, 16, 17, 17, 19, 19, 14, 14, 19, 19, 18, 18, 21, 21, 8, 8, 13, 13, 16, 16, 17, 17, 17, 17, 22, 22, 19, 19, 23

Offset: 1

Antti Karttunen, Aug 28 2003

Form a tree of fractions by beginning with 1/1 and then giving every node i/j two descendants labeled i/(i+j) and j/(i+j).
Level n of the left-hand half of the tree consists of 2^(n-1) nodes: 1/2; 1/3, 2/3; 1/4, 3/4, 2/5, 3/5; 1/5, 4/5, 3/7, 4/7, 2/7, 5/7, 3/8, 5/8; ... .
The right-hand half is identical to the left-hand half. - Michel Dekking, Oct 05 2017
n>1 occurs in this sequence phi(n) = A000010(n) times, as it occurs in A007306 (Franklin T. Adams-Watters' comment), that is the sequence obtained by adding numerator and denominator in the Calkin-Wilf enumeration system of positive rationals. A020650(n)/A020651(n) is also an enumeration system of all positive rationals (Yu-Ting system), 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), and A268087 (A162909+A162910). - Yosu Yurramendi, Apr 06 2016

Johannes Kepler, Mysterium cosmographicum, Tuebingen, 1596, 1621, Caput XII.
Johannes Kepler, Harmonice Mundi, Linz, 1619, Liber III, Caput II.
Johannes Kepler, The Harmony of the World [1619], trans. E. J. Aiton, A. M. Duncan and J. V. Field, American Philosophical Society, Philadelphia, 1997, p. 163.

Johannes Kepler, Harmonices mundi libri V ... (A Latin original scanned in Internet Archive. The fraction-tree is illustrated on the page 27 of the third book (Liber III), which is on the page 117 of the PDF-document.)
Johannes Kepler, Excerpt from the Chapter II of the Book III of the Harmony of the World: On the seven harmonic divisions of the string (Illustrates the A020651/A086592-tree).
OEIS Wiki, Historical sequences
Pelegrí Viader, Jaume Paradís and Lluís Bibiloni, A New Light on Minkowski's ?(x) Function, J. Number Theory, 73 (2) (1998), 212-227. See p. 215.
Index entries for fraction trees
Index entries for sequences related to music

Bisection of A020650.
See A093873/A093875 for the full tree.
A020651 gives the numerators. Bisection: A086593. Cf. A002487, A004169.

(* b = A020650 *) b[1] = 1; b[2] = 2; b[3] = 1; b[n_] := b[n] = Switch[ Mod[n, 4], 0, b[n/2 + 1] + b[n/2], 1, b[(n - 1)/2 + 1], 2, b[(n - 2)/2 + 1] + b[(n - 2)/2], 3, b[(n - 3)/2]]; a[n_] := b[2n]; Array[a, 100] (* Jean-François Alcover, Jan 22 2016 *)

maxlevel <- 15
d <- c(1,2)
for(m in 0:maxlevel)
for(k in 1:2^m) {
   d[2^(m+1)    +k] <- d[k] + d[2^m+k]
   d[2^(m+1)+2^m+k] <- d[2^(m+1)+k]
}
b <- vector()
for(m in 0:maxlevel) for(k in 0:(2^m-1)) b[2^m+k] <- d[2^(m+1)+k]
a <- vector()
for(n in 1:2^maxlevel) {a[2*n-1] <- b[n]; a[2*n] <- b[n+1]}
a[1:128]
# Yosu Yurramendi, May 16 2018

a(n) = A020650(n) + A020651(n) = A020650(2n).
a(n) = A071585(A059893(n)), a(A059893(n)) = A071585(n), n > 0. - Yosu Yurramendi, May 30 2017
a(2*n-1) = A086593(n); a(2*n) = A086593(n+1), n > 0. - Yosu Yurramendi, May 16 2018
a(n) = A007306(A231551(n)), n > 0. - Yosu Yurramendi, Aug 07 2021

Entry revised by N. J. A. Sloane, May 24 2004

A092569 Permutation of integers a(a(n)) = n. In binary representation of n, transformation of inner bits, 1 <-> 0, gives binary representation of a(n).

Original entry on oeis.org

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

Offset: 0

Zak Seidov, Feb 28 2004

Primes which stay primes under transformation "opposite inner bits", A092570.
This permutation transforms the enumeration system of positive irreducible fractions A020651/A020650 into the enumeration system A245327/A245326, and vice versa. - Yosu Yurramendi, Jun 16 2015
A117120(a(n)) = a(A117120(n)), n > 0.
A258996(a(n)) = a(A258996(n)), n > 0.
A258746(a(n)) = a(A258746(n)), n > 0.
A054429(a(n)) = a(A054429(n)), n > 0.
a(n) = A054429(A065190(n)) = A065190(A054429(n)), n > 0. - Yosu Yurramendi, Mar 23 2017

			a(9)=15 because 9_10 = 1001_2, transformation of inner bits gives 1001_2 -> 1111_2 = 15_10.

Michael De Vlieger, Table of n, a(n) for n = 0..10000

Cf. A092570.

bb={0, 1, 2, 3};Do[id=IntegerDigits[n, 2];Do[id[[i]]=1-id[[i]], {i, 2, Length[id]-1}];bb=Append[bb, FromDigits[id, 2]], {n, 4, 1000}];fla=Flatten[bb]
(* Second program: *)
Table[If[n < 2, n, Function[b, FromDigits[#, 2] &@ Join[{First@ b}, Most[Rest@ b] /. { 0 -> 1, 1 -> 0}, {Last@ b}]]@ IntegerDigits[n, 2]], {n, 0, 70}] (* Michael De Vlieger, Apr 03 2017 *)

T(n)={pow2=2;v=binary(n);L=#v-1;forstep(k=L,2,-1,if(v[k],n-=pow2,n+=pow2);pow2*=2);return(n)};
for(n=0,70,print1(T(n),", ")) \\ Washington Bomfim, Jan 18 2011

maxrow <- 8 # by choice
a <- 1:3 # If it were c(1, 3, 2), it would be A054429
for(m in 1:maxrow) for(k in 0:(2^m-1)){
a[2^(m+1)+    k] = a[2^m+k] + 2^(m+1)
a[2^(m+1)+2^m+k] = a[2^m+k] + 2^m
}
a
# Yosu Yurramendi, Apr 10 2017

a(0) = 0, a(1) = 1, a(2) = 2, a(3) = 3, a(2^(m+1) +k) = a(2^m+k) + 2^(m+1),

a(2^(m+1)+2^m+k) = a(2^m+k) + 2^m, m >= 1, 0 <= k < 2^m. - Yosu Yurramendi, Apr 02 2017

A245327 Numerators in recursive bijection from positive integers to positive rationals, where the bijection is f(1) = 1, f(2n) = 1/(f(n)+1), f(2n+1) = f(n)+1.

Original entry on oeis.org

1, 1, 2, 2, 3, 1, 3, 3, 5, 2, 5, 3, 4, 1, 4, 5, 8, 3, 8, 5, 7, 2, 7, 4, 7, 3, 7, 4, 5, 1, 5, 8, 13, 5, 13, 8, 11, 3, 11, 7, 12, 5, 12, 7, 9, 2, 9, 7, 11, 4, 11, 7, 10, 3, 10, 5, 9, 4, 9, 5, 6, 1, 6, 13, 21, 8, 21, 13, 18, 5, 18, 11, 19, 8, 19, 11, 14, 3, 14, 12, 19, 7, 19, 12, 17, 5, 17, 9, 16, 7, 16, 9, 11, 2, 11, 11, 18, 7, 18, 11

Offset: 1

Yosu Yurramendi, Jul 18 2014

a(n)/A245328(n) enumerates all the reduced nonnegative rational numbers exactly once.
If the terms (n>0) are written as an array (left-aligned fashion) with rows of length 2^m, m = 0,1,2,3,...
   1,
   1, 2,
   2, 3,1, 3,
   3, 5,2, 5,3, 4,1, 4,
   5, 8,3, 8,5, 7,2, 7,4, 7,3, 7,4,5,1,5,
   8,13,5,13,8,11,3,11,7,12,5,12,7,9,2,9,7,11,4,11,7,10,3,10,5,9,4,9,5,6,1,6,
then the sum of the m-th row is 3^m (m = 0,1,2,), and each column k is a Fibonacci sequence.
If the rows are written in a right-aligned fashion:
                                                                        1,
                                                                      1,2,
                                                                  2,3,1,3,
                                                          3,5,2,5,3,4,1,4,
                                      5, 8,3, 8,5, 7,2, 7,4,7,3,7,4,5,1,5,
8,13,5,13,8,11,3,11,7,12,5,12,7,9,2,9,7,11,4,11,7,10,3,10,5,9,4,9,5,6,1,6,
then each column is an arithmetic sequence.
If the sequence is considered by blocks of length 2^m, m = 0,1,2,..., the blocks of this sequence are permutations of terms of blocks from A002487 (Stern's diatomic series or Stern-Brocot sequence), and, more precisely, the reverses of blocks of A020650 ( a(2^m+k) = A020650(2^(m+1)-1-k), m = 0,1,2,..., k = 0,1,2,...,2^m-1).
Moreover, each block is the bit-reversed permutation of the corresponding block of A245325.

Michael De Vlieger, Table of n, a(n) for n = 1..16383, rows 1-14, flattened.
Index entries for fraction trees

Cf. A002487, A020651, A245325, A245328, A273493.

f[n_] := Which[n == 1, 1, EvenQ@ n, 1/(f[n/2] + 1), True, f[(n - 1)/2] + 1]; Table[Numerator@ f@ k, {n, 7}, {k, 2^(n - 1), 2^n - 1}] // Flatten (* Michael De Vlieger, Mar 02 2017 *)

a(n) = my(A=0); forstep(i=logint(n, 2), 0, -1, if(bittest(n, i), A++, A=1/(A+1))); numerator(A) \\ Mikhail Kurkov, Mar 12 2023

N  <- 25 # arbitrary
a <- c(1,1,2)
for(n in 1:N){
  a[4*n]   <-          a[2*n+1]
  a[4*n+1] <- a[2*n] + a[2*n+1]
  a[4*n+2] <- a[2*n]
  a[4*n+3] <- a[2*n] + a[2*n+1]
}
a

a(2n) = A245328(2n+1) , a(2n+1) = A245328(2n) , n=0,1,2,3,...
a((2*n+1)*2^m - 2) = A273493(n), n > 0, m > 0. For n = 0, m > 0, A273493(0) = 1 is needed. For n = 1, m = 0, A273493(0) = 1 is needed. For n > 1, m = 0, numerator((2*n-1) = num+den(n-1). - Yosu Yurramendi, Mar 02 2017
a(n) = A002487(A284459(n)). - Yosu Yurramendi, Aug 23 2021

A093875 Denominators in Kepler's tree of harmonic fractions.

Original entry on oeis.org

1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 4, 4, 5, 5, 5, 5, 7, 7, 7, 7, 8, 8, 5, 5, 7, 7, 7, 7, 8, 8, 6, 6, 9, 9, 10, 10, 11, 11, 9, 9, 12, 12, 11, 11, 13, 13, 6, 6, 9, 9, 10, 10, 11, 11, 9, 9, 12, 12, 11, 11, 13, 13, 7, 7, 11, 11, 13, 13, 14, 14, 13, 13, 17, 17, 15, 15, 18, 18, 11, 11, 16, 16

Offset: 1

N. J. A. Sloane and Reinhard Zumkeller, May 24 2004

Form a tree of fractions by beginning with 1/1 and then giving every node i/j two descendants labeled i/(i+j) and j/(i+j).

It appears that A071585 is a bisection of this sequence, which itself is a bisection of A093873. - Yosu Yurramendi, Jan 09 2016

			The first few fractions are:
1 1 1 1 2 1 2 1 3 2 3 1 3 2 3 1 4 3 4 2 5 3 5 1 4 3 4 2 5 3 5
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ...
1 2 2 3 3 3 3 4 4 5 5 4 4 5 5 5 5 7 7 7 7 8 8 5 5 7 7 7 7 8 8

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Index entries for fraction trees

The numerators are in A093873. Usually one only considers the left-hand half of the tree, which gives the fractions A020651/A086592. See A086592 for more information, references to Kepler, etc.

Cf. A071585, A093873

num[1] = num[2] = 1; den[1] = 1; den[2] = 2; num[n_?EvenQ] := num[n] = num[n/2]; den[n_?EvenQ] := den[n] = num[n/2] + den[n/2]; num[n_?OddQ] := num[n] = den[(n-1)/2]; den[n_?OddQ] := den[n] = num[(n-1)/2] + den[(n-1)/2]; A093875 = Table[den[n], {n, 1, 83}] (* Jean-François Alcover, Dec 16 2011 *)

a(n) = a([n/2]) + A093873([n/2]).
Conjecture of the comment in detail: a(2n+1) = a(2n), n > 0;  a(2n+1) = A071585(n), n >= 0; a(2n) = A071585(n), n > 0. - Yosu Yurramendi, Jun 22 2016
a(2n) - A093873(2n) = a(n), n > 0; a(2n+1) - A093873(2n+1) = A093873(n), n > 0. - Yosu Yurramendi, Jul 23 2016
From Yosu Yurramendi, Jul 25 2016: (Start)
a(2^m)  = m+1, m >= 0; a(2^m + 2) = 2m - 1, m >= 1; a(2^m - 1) = A000045(m+2), m >= 1.
a(2^(m+1) + k) - a(2^m + k) = a(k),   m > 0, 0 <= k < 2^m. For k=0, a(0) = 1 is needed.
a(2^(m+2) - k - 1) = a(2^(m+1) - k - 1) + a(2^m - k - 1), m >= 0, 0 <= k < 2^m. (End)

A231551 Position of n in A231550.

Original entry on oeis.org

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

Offset: 0

Alex Ratushnyak, Nov 10 2013

This permutation transforms the enumeration system of positive irreducible fractions A002487/A002487' (Calkin-Wilf) into the enumeration system A020651/A020650, and A162911/A162912 (Drib) the enumeration system into A245327/A245326. - Yosu Yurramendi, Jun 16 2015

Cf. A003188, A006068, A231550.

Join[{0, 1}, Table[d = Reverse@IntegerDigits[n, 2]; FromDigits[Reverse@Append[FoldList[BitXor, d[[1]], Most@Rest@d], d[[-1]]], 2], {n, 2, 67}]] (* Ivan Neretin, Dec 28 2016 *)

for n in range(99):
  bits = [0]*64
  orig = [0]*64
  l = int.bit_length(int(n))
  t = n
  for i in range(l):
    bits[i] = orig[i] = t&1
    t>>=1
  #for i in range(1, l-1):  bits[i] ^= orig[i-1]   # A231550
  for i in range(1, l-1):  bits[i] ^= bits[i-1]   # A231551
  #for i in range(l-1):  bits[i] ^= orig[i+1]      # A003188
  #for i in range(1, l):  bits[l-1-i] ^= bits[l-i]  # A006068
  t = 0
  for i in range(l):  t += bits[i]<

R

maxrow <- 8 # by choice b01 <- 0 # b01 is going to be A010059 a <- 1 for(m in 0:maxrow) for(k in 0:(2^m-1)){ b01[2^(m+1)+ k] <- b01[2^m+k] a[2^(m+1)+ k] <- a[2^m+k] + 2^(m+b01[2^(m+1)+ k]) b01[2^(m+1)+2^m+k] <- 1 - b01[2^m+k] a[2^(m+1)+2^m+k] <- a[2^m+k] + 2^(m+b01[2^(m+1)+2^m+k]) } (a <- c(0,a)) # Yosu Yurramendi, Apr 10 2017

R

maxblock <- 8 # by choice a <- 1:3 for(n in 4:2^maxblock){ ones <- which(as.integer(intToBits(n)) == 1) nbit <- as.integer(intToBits(n))[1:tail(ones, n = 1)] anbit <- nbit for(i in 2:(length(anbit) - 1)) anbit[i] <- bitwXor(anbit[i], anbit[i-1]) # ?bitwXor a <- c(a, sum(anbit*2^(0:(length(anbit) - 1)))) } (a <- c(0,a)) # Yosu Yurramendi, Apr 25 2021

Formula

A231550(a(n)) = a(A231550(n)) = n.

a(n) = A258996(A284460(n)) = A284459(A092569(n)), n > 0. - Yosu Yurramendi, Apr 10 2017

a(n) = A054429(A153154(n)), n > 0. - Yosu Yurramendi, Oct 04 2021

A245328 Denominators in recursive bijection from positive integers to positive rationals (the bijection is f(1) = 1, f(2n) = 1/(f(n)+1), f(2n+1) = f(n)+1).

Original entry on oeis.org

1, 2, 1, 3, 2, 3, 1, 5, 3, 5, 2, 4, 3, 4, 1, 8, 5, 8, 3, 7, 5, 7, 2, 7, 4, 7, 3, 5, 4, 5, 1, 13, 8, 13, 5, 11, 8, 11, 3, 12, 7, 12, 5, 9, 7, 9, 2, 11, 7, 11, 4, 10, 7, 10, 3, 9, 5, 9, 4, 6, 5, 6, 1, 21, 13, 21, 8, 18, 13, 18, 5, 19, 11, 19, 8, 14, 11, 14, 3, 19, 12, 19, 7, 17, 12, 17, 5, 16, 9, 16, 7, 11, 9, 11, 2, 18, 11, 18, 7, 15

Offset: 1

Views

Graph

List

Refs

Listen

History

Text

Internal format

Author

Yosu Yurramendi, Jul 18 2014

Keywords

nonn
frac

Comments

A245327(n)/a(n) enumerates all the reduced nonnegative rational numbers exactly once.

If the terms (n>0) are written as an array (left-aligned fashion) with rows of length 2^m, m = 0,1,2,3,...

1,

2,1,

3,2, 3,1,

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

8,5, 8,3, 7,5, 7,2, 7,4, 7,3,5,4,5,1,

13,8,13,5,11,8,11,3,12,7,12,5,9,7,9,2,11,7,11,4,10,7,10,3,9,5,9,4,6,5,6,1,

then the sum of the m-th row is 3^m (m = 0,1,2,), and each column k is a Fibonacci sequence.

If the rows are written in a right-aligned fashion:

1,

2,1,

3,2,3,1,

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

8,5, 8,3, 7,5, 7,2,7,4,7,3,5,4,5,1,

13,8,13,5,11,8,11,3,12,7,12,5,9,7,9,2,11,7,11,4,10,7,10,3,9,5,9,4,6,5,6,1,

then each column is an arithmetic sequence. The differences of the arithmetic sequences, except the first on the right, give the sequence A093873 (Numerators in Kepler's tree of harmonic fractions) (a(2^(m+1)-1-k) - a(2^m-1-k) = A093873(k), m = 0,1,2,..., k = 0,1,2,...,2^m-1).

If the sequence is considered by blocks of length 2^m, m = 0,1,2,..., the blocks of this sequence are permutations of terms of blocks from A002487 (Stern's diatomic series or Stern-Brocot sequence), and, more precisely, the reverses of blocks of A020651 ( a(2^m+k) = A020651(2^(m+1)-1-k), m = 0,1,2,..., k = 0,1,2,...,2^m-1).

Moreover, each block is the bit-reversed permutation of the corresponding block of A245326.

Links

Michael De Vlieger, Table of n, a(n) for n = 1..16383, rows 1-14, flattened.

Index entries for fraction trees

Crossrefs

Cf. A002487, A020651, A093873, A245326, A245327, A273493.

Programs

Mathematica

f[n_] := Which[n == 1, 1, EvenQ@ n, 1/(f[n/2] + 1), True, f[(n - 1)/2] + 1]; Table[Denominator@ f@ k, {n, 7}, {k, 2^(n - 1), 2^n - 1}] // Flatten (* Michael De Vlieger, Mar 02 2017 *)

PARI

a(n) = my(A=0); forstep(i=logint(n, 2), 0, -1, if(bittest(n, i), A++, A=1/(A+1))); denominator(A) \\ Mikhail Kurkov, Mar 12 2023

R

N <- 25 # arbitrary a <- c(1,2,1) for(n in 1:N){ a[4*n] <- a[2*n] + a[2*n+1] a[4*n+1] <- a[2*n] a[4*n+2] <- a[2*n] + a[2*n+1] a[4*n+3] <- a[2*n+1] } a

Formula

a(2n) = A245327(2n+1) , a(2n+1) = A245328(2n) , n=1,2,3,...

a((2*n+1)*2^m - 1) = A273493(n), n > 0, m >= 0. For n = 0 A273493(0) = 1 is needed. - Yosu Yurramendi, Mar 02 2017

a(n) = A002487(1+A284459(n)). - Yosu Yurramendi, Aug 23 2021

A268087 a(n) = A162909(n) + A162910(n).

Original entry on oeis.org

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

Offset: 1

Views

Graph

List

Refs

Listen

History

Text

Internal format

Author

Yosu Yurramendi, Jan 26 2016

Keywords

nonn
easy

Comments

If the terms (n>0) are written as an array (in a left-aligned fashion) with rows of length 2^m, m >= 0:

2,

3, 3,

5, 4, 4, 5,

8, 7, 5, 7, 7, 5, 7, 8,

13,11, 9,12, 9, 6,10,11,11,10,6, 9,12, 9,11,13,

21,18,14,19,16,11,17,19,14,13,7,11,17,13,15,18,18,15,13,17,11,7,13,14,19,17,11,16, ...

a(n) is palindromic in each level m >= 0 (ranks between 2^m and 2^(m+1)-1), because in each level m >= 0 A162910 is the reverse of A162909:

a(2^m + k) = a(2^(m+1) - 1 - k), m >= 0, 0 <= k < 2^m.

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

a(2^m + k) = A162909(2^(m+2) + k), a(2^m + k) = A162909(2^(m+1)+ 2^m + k), a(2^m + k) = A162910(2^(m+1) + k), m >= 0, 0 <= k < 2^m (empirical observations).

a(n) = A162911(n) + A162912(n), where A162911(n)/A162912(n) is the bit reversal permutation of A162909(n)/A162910(n) in each level m >= 0 (empirical observations).

a(n) = A162911(2n+1), a(n) = A162912(2n) for n > 0 (empirical observations). 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. A162909(n)/A162910(n) is also an enumeration system of all positive rationals (Bird system), 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), and A086592 (A020650+A020651).

Examples

m = 3, k = 6: a(38) = 17, a(22) = 10, a(14) = 7.

Crossrefs

Cf. A162909, A162910, A162911, A162912, A007306, A071585, A086592.

Programs

PARI

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

Formula

a(2^(m+2)+k) = a(2^(m+1)+k) + a(2^m+k) with m = 0, 1, 2, ... and 0 <= k < 2^m (empirical observation).

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

From Yosu Yurramendi, May 14 2019: (Start)

Take the smallest m > 0 such that 0 <= k < 2^(m-1), and choose any M >= m,

a((1/3)*( A016921(2^(m-1)+k)*4^(M-m)-1)) = 2*a(2^(m-1)+k)*(M-m) + a(2^m+2*k ).

a((1/3)*(2*A016921(2^(m-1)+k)*4^(M-m)-2)) = 2*a(2^(m-1)+k)*(M-m) + a(2^m+2*k ) + a(2^(m-1)+k).

a((1/3)*( A016969(2^(m-1)+k)*4^(M-m)-2)) = 2*a(2^(m-1)+k)*(M-m) + a(2^m+2*k+1).

a((1/3)*(2*A016969(2^(m-1)+k)*4^(M-m)-1)) = 2*a(2^(m-1)+k)*(M-m) + a(2^m+2*k+1) + a(2^(m-1)+k). (End)

a(n) = A007306(A258996(n)), n > 0. - Yosu Yurramendi, Jun 23 2021

A086593 Bisection of A086592, denominators of the left-hand half of Kepler's tree of fractions.

Original entry on oeis.org

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

Offset: 1

Views

Graph

List

Refs

Listen

History

Text

Internal format

Author

Antti Karttunen, Aug 28 2003

Keywords

nonn

Comments

Also denominator of alternate fractions in Kepler's tree as shown in A294442. - N. J. A. Sloane, Nov 20 2017

Links

Antti Karttunen, Table of n, a(n) for n = 1..2048 (computed from b-file of A020650 provided by _T. D. Noe_)

Crossrefs

Cf. A000045, A020650, A020651, A071585, A071766, A086592, A294442.

Programs

Mathematica

(* b = A020650 *) b[1] = 1; b[2] = 2; b[3] = 1; b[n_] := b[n] = Switch[ Mod[n, 4], 0, b[n/2 + 1] + b[n/2], 1, b[(n - 1)/2 + 1], 2, b[(n - 2)/2 + 1] + b[(n - 2)/2], 3, b[(n - 3)/2]]; a[1] = 2; a[n_] := b[4 n - 4]; Array[a, 100] (* Jean-François Alcover, Jan 22 2016, after Yosu Yurramendi's formula for A020650 *)

R

maxlevel <- 15 d <- c(1,2) for(m in 0:maxlevel) for(k in 1:2^m) { d[2^(m+1) +k] <- d[k] + d[2^m+k] d[2^(m+1)+2^m+k] <- d[2^(m+1)+k] } a <- vector() for(m in 0:maxlevel) for(k in 0:(2^m-1)) a[2^m+k] <- d[2^(m+1)+k] a[1:63] # Yosu Yurramendi, May 16 2018

Formula

a(n) = A086592(2n-1) = A020650(4n-2).

a(n+1) = A071585(n) + A071766(n), n >= 0. - Yosu Yurramendi, Jun 30 2014

From Yosu Yurramendi, Jan 04 2016: (Start)

a(2^(m+1)+k+1) - a(2^m+k+1) = A071585(k), m >= 0, 0 <= k < 2^m.

a(2^(m+2)-k) = a(2^(m+1)-k) + a(2^m-k), m > 0, 0 <= k < 2^m-1.

(End)

a(2^n) = A000045(n+3). - Antti Karttunen, Jan 29 2016, based on above.

a(n) = A020651(4n-1), a(n+1) = A020651(4n+1), n > 0. - Yosu Yurramendi, May 08 2018

a(2^m+k) = A071585(2^(m+1)+k), m >= 0, 0 <= k < 2^m. - Yosu Yurramendi, May 16 2018

A153154 Permutation of natural numbers: A059893-conjugate of A006068.

Original entry on oeis.org

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

Offset: 0

Views

Graph

List

Refs

Listen

History

Text

Internal format

Author

Antti Karttunen, Dec 20 2008

Keywords

nonn
base

Comments

A002487(1+a(n)) = A020651(n) and A002487(a(n)) = A020650(n). So, it generates the enumeration system of positive rationals based on Stern's sequence A002487. - Yosu Yurramendi, Feb 26 2020

Links

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

Index entries for sequences that are permutations of the natural numbers

Crossrefs

Inverse: A153153. a(n) = A059893(A006068(A059893(n))).

Programs

R

maxn <- 63 # by choice a <- c(1,3,2) # for(n in 2:maxn){ a[2*n] <- 2*a[n] + 1 if(n%%2==0) a[2*n+1] <- 2*a[n+1] else a[2*n+1] <- 2*a[n-1] } (a <- c(0,a)) # Yosu Yurramendi, Feb 26 2020

R

# Given n, compute a(n) by taking into account the binary representation of n maxblock <- 8 # by choice a <- c(1, 3, 2) for(n in 4:2^maxblock){ ones <- which(as.integer(intToBits(n)) == 1) nbit <- as.integer(intToBits(n))[1:tail(ones, n = 1)] anbit <- nbit for(i in 2:(length(anbit) - 1)) anbit[i] <- bitwXor(anbit[i], anbit[i - 1]) # ?bitwXor anbit[0:(length(anbit) - 1)] <- 1 - anbit[0:(length(anbit) - 1)] a <- c(a, sum(anbit*2^(0:(length(anbit) - 1)))) } (a <- c(0, a)) # Yosu Yurramendi, Oct 04 2021

Formula

From Yosu Yurramendi, Feb 26 2020: (Start)

a(1) = 1, for all n > 0 a(2*n) = 2*a(n) + 1, a(2*n+1) = 2*a(A065190(n)).

a(1) = 1, a(2) = 3, a(3) = 2, for all n > 1 a(2*n) = 2*a(n) + 1, and if n even a(2*n+1) = 2*a(n+1), else a(2*n+1) = 2*a(n-1).

a(n) = A054429(A231551(n)) = A231551(A065190(n)) = A284459(A054429(n)) =

A332769(A284459(n)) = A258996(A154437(n)). (End)

A231550 Permutation of nonnegative integers: for each bit[i] in the binary representation, except the most and the least significant bits, set bit[i] = bit[i] XOR bit[i-1], where bit[i-1] is the less significant bit, XOR is the binary logical exclusive or operator.

Original entry on oeis.org

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

Offset: 0

Views

Graph

List

Refs

Listen

History

Text

Internal format

Author

Alex Ratushnyak, Nov 10 2013

Keywords

nonn
look
base
easy

Comments

This permutation transforms the enumeration system of positive irreducible fractions A020651/A020650 into the enumeration system A002487/A002487' (Calkin-Wilf), and enumeration system A245327/A245326 into A162911/A162912 (Drib). - Yosu Yurramendi, Jun 16 2015

Links

Ivan Neretin, Table of n, a(n) for n = 0..8192

Index entries for sequences that are permutations of the nonnegative integers

Crossrefs

Cf. A003188, A006068, A231551.

Programs

Mathematica

Join[{0, 1}, Table[d = IntegerDigits[n, 2]; FromDigits[Join[{d[[1]]}, BitXor[Most@Rest@d, Rest@Rest@d], {d[[-1]]}], 2], {n, 2, 68}]] (* Ivan Neretin, Dec 28 2016 *)

PARI

a(n) = bitxor(n, if(n>3, bitand(n<<1, bitneg(0,logint(n,2))))); \\ Kevin Ryde, Jul 17 2021

Python

for n in range(99): bits = [0]*64 orig = [0]*64 l = int.bit_length(int(n)) t = n for i in range(l): bits[i] = orig[i] = t&1 t>>=1 for i in range(1, l-1): bits[i] ^= orig[i-1] # A231550 #for i in range(1, l-1): bits[i] ^= bits[i-1] # A231551 #for i in range(l-1): bits[i] ^= orig[i+1] # A003188 #for i in range(1,l): bits[l-1-i] ^= bits[l-i] # A006068 t = 0 for i in range(l): t += bits[i]<

R

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

Formula

a(A231551(n)) = A231551(a(n)) = n.

a(n) = A284460(A258996(n)) = A092569(A284460(n)), n > 0. - Yosu Yurramendi, Apr 10 2017

Previous Showing 11-20 of 21 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.
Content is available under The OEIS End-User License Agreement.

cp's OEIS Frontend

A086592 Denominators in left-hand half of Kepler's tree of fractions.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

R

Formula

Extensions

A092569 Permutation of integers a(a(n)) = n. In binary representation of n, transformation of inner bits, 1 <-> 0, gives binary representation of a(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

R

Formula

A245327 Numerators in recursive bijection from positive integers to positive rationals, where the bijection is f(1) = 1, f(2n) = 1/(f(n)+1), f(2n+1) = f(n)+1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

R

Formula

A093875 Denominators in Kepler's tree of harmonic fractions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A231551 Position of n in A231550.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

R

R

Formula

A245328 Denominators in recursive bijection from positive integers to positive rationals (the bijection is f(1) = 1, f(2n) = 1/(f(n)+1), f(2n+1) = f(n)+1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

R

Formula

A268087 a(n) = A162909(n) + A162910(n).

Views

Author

Keywords

Comments