OFFSET
1,2
COMMENTS
Sequence is self-inverse: a(a(n)) = n.
A002487(1+a(n)) = A162911(n) and A002487(a(n)) = A162912(n). So, a(n) generates the enumeration system of positive rationals based on Stern's sequence A002487 called 'drib'.
Given n, one can compute a(n) by taking into account the binary representation of n, and by flipping every second bit starting from the lowest until reaching the highest 1, which is not flipped.
LINKS
Yosu Yurramendi, Table of n, a(n) for n = 1..8191
FORMULA
a(1) = 1; for m >= 0 and 0 <= k < 2^m, a(2^(m+1)+2*k) = 2*a(2^(m+1)-1-k) + 1, a(2^(m+1)+2*k+1) = 2*a(2^(m+1)-1-k).
EXAMPLE
n = 23 = 10111_2
x x
10010_2 = 18 = a(n).
n = 33 = 100001_2
x x x
110100_2 = 52 = a(n).
PROG
(R)
maxrow <- 6 # by choice
a <- 1
for(m in 0:maxrow) for(k in 0:(2^m-1)){
a[2^(m+1)+2*k ] <- 2*a[2^(m+1)-1-k] + 1
a[2^(m+1)+2*k+1] <- 2*a[2^(m+1)-1-k]
}
a
(R) # Given n, compute a(n) by taking into account the binary representation of n
maxblock <- 7 # 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
anbit[seq(1, length(anbit) - 1, 2)] <- 1 - anbit[seq(1, length(anbit) - 1, 2)]
a <- c(a, sum(anbit*2^(0:(length(anbit) - 1))))
}
a
# Yosu Yurramendi, Mar 30 2021
(PARI) a(n) = bitxor(n, 2<<bitor(logint(n, 2)-1, 1)\3); \\ Kevin Ryde, Mar 30 2021
CROSSREFS
KEYWORD
nonn
AUTHOR
Yosu Yurramendi, Feb 23 2020
STATUS
approved