A003188 -id:A003188 - cp's OEIS frontend

A105081 a(n) = 1 + A003188(n - 1), n >= 1.

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

Offset: 1

Philippe Deléham, Apr 28 2005

A permutation of the natural numbers.

Inverse permutation: A066194.

Cf. A000069, A003188, A065621, A268718.

Nest[Join[#,Length[#]+Reverse[#]]&,{1},7] (* Vladimir Joseph Stephan Orlovsky, Feb 01 2012 *)

def A105081(n): return 1+(n-1^ n-1>>1) # Chai Wah Wu, Jun 29 2022

(define (A105081 n) (+ 1 (A003188 (- n 1)))) ;; Antti Karttunen, Feb 14 2016

a(1) = 1, a(2^k + j) = 2^k + a(2^k - j + 1) for 1 <= j <= 2^k.
A000069(a(n)) = A065621(n).
As a composition of related permutations:
a(n) = A268718(A003188(n)). - Antti Karttunen, Feb 14 2016

A277808 a(n) = number of iterations of map k -> A003188(A006068(k)/2) that are required (when starting from k = n) until k is an odious number.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Nov 03 2016

Antti Karttunen, Table of n, a(n) for n = 1..16384
Index entries for sequences related to binary expansion of n

One less than A277822.
A left inverse of A003945.
Cf. A277812 (gives the odious number where such an iteration is finished at when starting from k=n).
Cf. A000069, A001969, A001511, A003188, A006068, A010059, A010060, A245710, A268389.

a(n) = A010059(n) * A001511(n).
If A010060(n) = 1 [when n is one of the odious numbers, A000069], then a(n) = 0, otherwise a(n) = 1 + a(A003188(A006068(n)/2)).
Other identities:
For all n >= 0, a(A003945(n)) = n.

A302844 Permutation of nonnegative integers: a(n) = A003188(A163356(n)).

Original entry on oeis.org

0, 1, 2, 3, 12, 15, 14, 13, 10, 9, 8, 11, 4, 5, 6, 7, 24, 27, 26, 25, 30, 31, 28, 29, 18, 19, 16, 17, 22, 21, 20, 23, 40, 43, 42, 41, 46, 47, 44, 45, 34, 35, 32, 33, 38, 37, 36, 39, 56, 57, 58, 59, 52, 55, 54, 53, 50, 49, 48, 51, 60, 61, 62, 63, 192, 195, 194, 193, 198, 199, 196, 197, 202, 203, 200, 201, 206, 205

Offset: 0

Antti Karttunen, Apr 14 2018

nonn

When A207901, which is a multiplicative walk permutation, is composed from the right with this permutation, the result is A302781, another multiplicative walk permutation.

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

Cf. A302843 (inverse).

Cf. A003188, A006068, A057300, A163356, A302846, A302781.

A003188(n) = bitxor(n, n>>1);
A057300(n) = { my(t=1,s=0); while(n>0, if(1==(n%4),n++,if(2==(n%4),n--)); s += (n%4)*t; n >>= 2; t <<= 2); (s); };
A163356(n) = if(!n,n,my(i = (#binary(n)-1)\2, f = 4^i, d = (n\f)%4, r = (n%f)); (((((2+(i%2))^d)%5)-1)*f) + if(3==d,f-1-A163356(r),A057300(A163356(r)))); \\ Antti Karttunen, Apr 14 2018
A302844(n) = A003188(A163356(n));

a(n) = A003188(A163356(n)).

a(n) = A006068(A302846(n)).

A163237 a(i,j) = bits of binary expansion of A003188(i) interleaved with that of A003188(j), then converted with A163241.

Original entry on oeis.org

0, 1, 3, 5, 2, 15, 4, 6, 14, 12, 20, 7, 10, 13, 60, 21, 23, 11, 9, 61, 63, 17, 22, 27, 8, 57, 62, 51, 16, 18, 26, 24, 56, 58, 50, 48, 80, 19, 30, 25, 40, 59, 54, 49, 240, 81, 83, 31, 29, 41, 43, 55, 53, 241, 243, 85, 82, 95, 28, 45, 42, 39, 52, 245, 242, 255, 84, 86, 94

Offset: 0

Antti Karttunen, Jul 29 2009

Inverse: A163238. a(n) = A163241(A163233(n)). Transpose: A163239. Cf. A147995.

A245451 Self-inverse permutation of nonnegative integers, A075158-conjugate of gray code: a(n) = 1 + A075157(A003188(A075158(n-1))).

Original entry on oeis.org

1, 2, 4, 3, 8, 9, 16, 6, 5, 27, 32, 18, 64, 81, 25, 12, 128, 7, 256, 54, 125, 243, 512, 36, 10, 729, 15, 162, 1024, 49, 2048, 24, 625, 2187, 50, 14, 4096, 6561, 3125, 108, 8192, 343, 16384, 486, 75, 19683, 32768, 72, 20, 21, 15625, 1458, 65536, 35, 250, 324, 78125, 59049, 131072, 98, 262144, 177147, 375, 48

Offset: 1

Antti Karttunen, Jul 22 2014

nonn

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

Inverse: A245452.
Cf. A003188, A075157, A075158.
Similar permutations: A245454, A122111, A241909, A241916.

(define (A245451 n) (+ 1 (A075157 (A003188 (A075158 (- n 1))))))

a(n) = 1 + A075157(A003188(A075158(n-1))).

A322017 a(0) = 0; for n > 0, if A003188(n) > A003188(n-1) then a(n) = n-1, else if A003188(n+1) < A003188(n) then a(n) = n+1, otherwise a(n) = 0.

Original entry on oeis.org

0, 0, 1, 0, 3, 4, 7, 0, 7, 8, 9, 12, 0, 12, 15, 0, 15, 16, 17, 0, 19, 20, 23, 24, 0, 24, 25, 28, 0, 28, 31, 0, 31, 32, 33, 0, 35, 36, 39, 0, 39, 40, 41, 44, 0, 44, 47, 48, 0, 48, 49, 0, 51, 52, 55, 56, 0, 56, 57, 60, 0, 60, 63, 0, 63, 64, 65, 0, 67, 68, 71, 0, 71, 72, 73, 76, 0, 76, 79, 0, 79, 80, 81, 0, 83, 84, 87, 88, 0, 88, 89

Offset: 0

Antti Karttunen, Nov 24 2018

nonn

For all n, A207901(a(n)) divides A207901(n), and similarly for A302033.

Antti Karttunen, Table of n, a(n) for n = 0..16383
Index entries for sequences related to binary expansion of n

Cf. A003188, A322015, A322016, A322018.

Cf. also A207901, A302033.

g[n_] := BitXor[n, Floor[n/2]]; a[n_] := If[n == 0, 0, If[g[n] > g[n-1],  n-1, If[g[n+1] < g[n], n+1, 0]]]; Array[a, 100, 0] (* Amiram Eldar, Dec 05 2018 *)

A003188(n) = bitxor(n, n>>1);
A322017(n) = if(0==n, 0, if(A003188(n)>A003188(n-1), n-1, if(A003188(1+n) < A003188(n), n+1, 0)));

A048641 Partial sums of A003188 (Gray code).

Original entry on oeis.org

0, 1, 4, 6, 12, 19, 24, 28, 40, 53, 68, 82, 92, 103, 112, 120, 144, 169, 196, 222, 252, 283, 312, 340, 360, 381, 404, 426, 444, 463, 480, 496, 544, 593, 644, 694, 748, 803, 856, 908, 968, 1029, 1092, 1154, 1212, 1271, 1328, 1384, 1424, 1465, 1508, 1550, 1596

Offset: 1

Antti Karttunen, Jul 14 1999

Michael De Vlieger, Table of n, a(n) for n = 1..10001
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, pp. 39-40.
R. Stephan, Some divide-and-conquer sequences ...
R. Stephan, Table of generating functions

Cf. A000217, A003188.

Accumulate[Table[BitXor[n, Floor[n/2]], {n, 0, 100}]] (* Vladimir Joseph Stephan Orlovsky, Jul 19 2011 *)

a(n) = sum(k=0, n, bitxor(k, k>>1)); \\ Michel Marcus, Oct 02 2015

a(2^n-1) = A000217(2^n-1) for all n.
a(n) = Sum_{j=0..n} XORnos(j, floor(j/2)).
a(n) = b(n-1), with b(2n) = 2*(b(n) + b(n-1) + ceiling(n/2)), b(2n+1) = 4*b(n) + n + 1. - Ralf Stephan, Sep 13 2003

A048642 Partial products of A003188 (Gray code).

Original entry on oeis.org

1, 1, 3, 6, 36, 252, 1260, 5040, 60480, 786240, 11793600, 165110400, 1651104000, 18162144000, 163459296000, 1307674368000, 31384184832000, 784604620800000, 21184324761600000, 550792443801600000, 16523773314048000000

Offset: 0

Antti Karttunen, Jul 14 1999

Harvey P. Dale, Table of n, a(n) for n = 0..444

Cf. A000142, A003188.

Join[{1},FoldList[Times,Table[BitXor[n,Floor[n/2]],{n,20}]]] (* Harvey P. Dale, Oct 05 2016 *)

a(n) = prod(i=1, n, bitxor(i, i>>1)); \\ Michel Marcus, Apr 22 2013, Oct 02 2015

a(0) = 1, a(n) = product(XOR(j, floor(j/2)), j=1..n).

a((2^n)-1) = A000142((2^n)-1) for all n.

A055095 a(n) = 2A000120(A003188(A055094(n))) - (n-1) = 2A005811(A055094(n)) - (n-1).

Original entry on oeis.org

0, 1, 2, 1, 2, 3, 2, 1, 4, 1, 2, 1, 2, 3, 2, -3, 2, 7, 2, -3, 4, 3, 2, -3, 14, 1, 10, -3, 2, 3, 2, -11, 4, 1, -2, -7, 2, 3, 2, -11, 2, 7, 2, -7, -4, 3, 2, -19, 8, 25, 2, -11, 2, 19, -6, -15, 4, 1, 2, -19, 2, 3, -6, -23, -10, 7, 2, -15, 4, -5, 2, -27, 2, 1, 6, -15, -4, 3, 2, -39, 28, 1, 2, -27, -14, 3, 2, -27, 2, -9, -10, -19, 4, 3, -14, -47, 2, 15, -14, -19, 2, 3, 2, -35, -24

Offset: 1

Antti Karttunen, Apr 04 2000

sign

For all odd primes p, a(p) = +2 because Sum_{a=1..(p-2)} L((a(a+1))/p) = Sum_{a=1..(p-2)} L((1+(a^-1))/p) = -1; i.e. in Gray code expansion of A055094[p], the number of 1-bits is number of 0-bits + 2. However, a(n) = +2 also for some nonprime odd n = A055131.

See problem 9.2.2 in Elementary Number Theory by David M. Burton, ISBN 0-205-06978-9

Indranil Ghosh, Table of n, a(n) for n = 1..4096

A055095 := proc(n)
    2*A005811(A055094(n))-n+1 ;
end proc:
seq(A055095(n),n=1..20) ; # R. J. Mathar, Mar 10 2015

A005811[n_] := Length[Length /@ Split[IntegerDigits[n, 2]]];
A055094[n_] := With[{rr = Table[Mod[k^2, n], {k, 1, n-1}] // Union}, Boole[ MemberQ[rr, #]]& /@ Range[n-1]] // FromDigits[#, 2]&;
a[1] = 0; a[n_] := 2*A005811[A055094[n]] - (n-1);
Array[a, 105] (* Jean-François Alcover, Mar 05 2016 *)

from sympy.ntheory.residue_ntheory import quadratic_residues as q
def a055094(n):
    Q=q(n)
    z=0
    for i in range(1, n):
        z*=2
        if i in Q: z+=1
    return z
def a005811(n): return bin(n^(n>>1))[2:].count("1")
def a(n): return 0 if n == 1 else 2*a005811(a055094(n)) - (n - 1) # Indranil Ghosh, May 13 2017

a(n) = (2*wt(GrayCode(qrs2bincode(n))))-(n-1).

A153153 Permutation of natural numbers: A059893-conjugate of A003188.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Dec 20 2008

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

Inverse: A153154. a(n) = A059893(A003188(A059893(n))).

a <- 1
maxlevel <- 5 # by choice
#
for(m in 0:maxlevel) 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+k]
}
a <- c(0,a)
# Yosu Yurramendi, Jan 25 2020

a(n) = A065190(A231550(n)). - Yosu Yurramendi, Jan 15 2020

a(1) = 1, a(2^(m+1)+2*k) = 2*a(2^(m+1)-1-k), a(2^(m+1)+2*k+1) = 2*a(2^m+k), m >= 0, 0 <= k < 2^m. - Yosu Yurramendi, Jan 25 2020

cp's OEIS Frontend

A105081 a(n) = 1 + A003188(n - 1), n >= 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Scheme

Formula

A277808 a(n) = number of iterations of map k -> A003188(A006068(k)/2) that are required (when starting from k = n) until k is an odious number.

Views

Author

Keywords

Links

Crossrefs

Formula

A302844 Permutation of nonnegative integers: a(n) = A003188(A163356(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A163237 a(i,j) = bits of binary expansion of A003188(i) interleaved with that of A003188(j), then converted with A163241.

Views

Author

Keywords

Links

Crossrefs

A245451 Self-inverse permutation of nonnegative integers, A075158-conjugate of gray code: a(n) = 1 + A075157(A003188(A075158(n-1))).

Views

Author

Keywords

Links

Crossrefs

Programs

Scheme

Formula

A322017 a(0) = 0; for n > 0, if A003188(n) > A003188(n-1) then a(n) = n-1, else if A003188(n+1) < A003188(n) then a(n) = n+1, otherwise a(n) = 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A048641 Partial sums of A003188 (Gray code).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A048642 Partial products of A003188 (Gray code).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A055095 a(n) = 2*A000120(A003188(A055094(n))) - (n-1) = 2*A005811(A055094(n)) - (n-1).

Views

Author

Keywords

Comments

A055095 a(n) = 2A000120(A003188(A055094(n))) - (n-1) = 2A005811(A055094(n)) - (n-1).