A053645 -id:A053645 - cp's OEIS frontend

A160588 Interleaving of A053645 and A000027.

0, 1, 0, 2, 1, 3, 0, 4, 1, 5, 2, 6, 3, 7, 0, 8, 1, 9, 2, 10, 3, 11, 4, 12, 5, 13, 6, 14, 7, 15, 0, 16, 1, 17, 2, 18, 3, 19, 4, 20, 5, 21, 6, 22, 7, 23, 8, 24, 9, 25, 10, 26, 11, 27, 12, 28, 13, 29, 14, 30, 15, 31, 0, 32, 1, 33, 2, 34, 3, 35, 4, 36, 5, 37, 6, 38, 7, 39, 8, 40, 9, 41, 10, 42, 11

Offset: 0

Reinhard Zumkeller, May 20 2009

a(2*n) = A053645(n+1); a(2*n+1) = A001477(n) = n;

for n>1: a(A028399(n)) = A000225(n-2), a(A000918(n)) = 0.

R. Zumkeller, Table of n, a(n) for n = 0..1000

import Data.List (transpose)
a160588 n = a160588_list !! n
a160588_list = concat $ transpose [a053645_list, a000027_list]
-- Reinhard Zumkeller, Dec 12 2012

a(n)=f(n,2) with f(n,m) = if n

Definition corrected by Reinhard Zumkeller, Dec 12 2012

A257697 a(n)=0 for n <= 1; for n >= 2, a(n) = largest number that can be obtained by rotating non-msb bits of binary expansion of n (with A080541 or A080542), without the most significant bit of n: a(n) = A053645(A256999(n)).

Original entry on oeis.org

0, 0, 0, 1, 0, 2, 2, 3, 0, 4, 4, 6, 4, 6, 6, 7, 0, 8, 8, 12, 8, 10, 12, 14, 8, 12, 10, 14, 12, 14, 14, 15, 0, 16, 16, 24, 16, 20, 24, 28, 16, 20, 20, 26, 24, 26, 28, 30, 16, 24, 20, 28, 20, 26, 26, 30, 24, 28, 26, 30, 28, 30, 30, 31, 0, 32, 32, 48, 32, 40, 48, 56, 32, 36, 40, 50, 48, 52, 56, 60, 32, 40, 36, 52, 40, 42, 50, 58, 48, 50, 52, 54, 56, 58, 60

Offset: 0

Antti Karttunen, May 16 2015

For each n, apart from powers of 2, a(n) gives the lexicographically largest representative from the equivalence class of binary necklaces obtained by successively rotating (with A080541 or A080542) all the other bits than the most significant bit in the binary representation of n.

Antti Karttunen, Table of n, a(n) for n = 0..8192

Cf. A000079, A053645, A072376, A080541, A080542, A256999.

(define (A257697 n) (A053645 (A256999 n)))

a(n) = A053645(A256999(n)).
Other identities and observations:
For all n >= 0, a(n) >= A053645(n).
Apart from powers of 2 (A000079), for any other n, a(n) >= A072376(n).

A258159 Numbers n such that A053645(n) (n with the most significant binary digit removed) divides A004526(n) (n with the least significant binary digit removed).

Original entry on oeis.org

3, 5, 7, 9, 15, 17, 19, 21, 31, 33, 63, 65, 67, 71, 73, 85, 127, 129, 255, 257, 259, 261, 271, 273, 307, 341, 511, 513, 519, 585, 1023, 1025, 1027, 1035, 1055, 1057, 1117, 1365, 2047, 2049, 2071, 2137, 4095, 4097, 4099, 4101, 4103, 4105, 4109, 4111, 4117, 4131, 4135, 4141, 4159

Offset: 1

Ivan Neretin, Jul 26 2015

Also, numbers of the form 2^k + d, where d is any divisor of (2^k - 1).

Ivan Neretin, Table of n, a(n) for n = 1..1091

Flatten[Table[2^n + Divisors[2^n - 1], {n, 15}]]

A380645 The expansion of the Stieltjes continued fraction 1/(1 - x/(1 - a(A053645(0))x/(1 - a(A053645(1))x/(1 - a(A053645(2))*x/...)))) gives the sequence itself.

Original entry on oeis.org

1, 1, 2, 5, 15, 52, 201, 857, 4370, 34365, 478287, 9095996, 189526537, 4036216585, 87129122290, 2478683501397, 2450240534552191, 12482183328151728692, 65634092872761268943625, 345370818796643845031835465, 1817414952852912380501431441282

Offset: 0

Thomas Scheuerle, Feb 06 2025

nonn

			The sequence 1, a(A053645(0)), a(A053645(1)), ... begins:
1, 1, 1, 2, 1, 2, 5, 15, 1, 2, 5, 15, 52, 201, 857, 4370, 1, 2, 5, 15, 52, 201, 857, 4370, 34365, 478287, 9095996, 189526537, 4036216585, 87129122290, 2478683501397, 2450240534552191, 1, 2, 5, 15, ...
This also forms a fractal sequence as it is invariant under the removal of each term's first occurrence:
 , 1, 1,  , 1, 2,  ,  , 1, 2, 5, 15,  ,  ,  ,  , 1, 2, 5, 15, 52, 52, 201, 857, ...
We insert this fractal sequence into the Stilties continued fractions and expand:
  1/(1 - 1*x/(1 - 1*x/(1 - 1*x/(1 - 2*x/(1 - 1*x/(1 - 2*x/(1 - 5*x/(...)))))))) =
  1 + 1*x + 2*x^2 + 5*x^3 + 15*x^4 + 52*x^5 + 201*x^6 + 857*x^7 + 4070*x^8 + 21765*x^9 + ... .

Wikipedia, Moment problem.

Cf. A053645.

cf(v) = {my(f = O(x)); for(k=1, #v, f=1/(1-v[#v+1-k]*x*f)); Vec(f+O(x^(#v)))}
vectorA(numiter) = {my(v = [1]); for(k=0, numiter, v=concat(v, cf(v))); v[1+#v/2..#v]}

Let s(n) be the Hankel transform of this sequence. Starting: 1, 1, 1, 2, 8, 2400, 1440000,... .
s(n) = Product_{m=0..n-2} Product_{k=1..m} a(A053645(2*k))*a(A053645(2*k+1)). This formula is particular interesting here, because if we expand the Hankel determinants based on A380645: s(0) = 1, s(1) = a(0), s(2) = a(0)*a(2) - a(1)^2, ..., then we will be able to obtain A380645 directly from a system of equations. This means the product formula for the Hankel determinant is also definition of this sequence.
The Hankel transforms of this sequence starting with offset 0 and starting with offset 1 are both strictly positive, this means this sequence can be considered as a sequence of moments in the Stieltjes moment problem: a(n) = Integral_{x>=0} x^n*V(n, x) dx. It is conjectured that the measure V(n, x) is related to some kind of interesting distribution which shows self similarity over intervals of powers of two.

A363417 a(n) = Sum_{j=0..2^n - 1} b(j) for n >= 0 where b(n) = (A023416(n) + 1)b(A053645(n)) + [A036987(n) = 0]b(A266341(n)) for n > 0 with b(0) = 1.

Original entry on oeis.org

1, 2, 6, 23, 106, 566, 3415, 22872, 167796, 1334596, 11414192, 104270906, 1011793389, 10379989930, 112134625986, 1271209859403, 15077083642150, 186588381229340, 2403775013224000, 32168379148440968, 446341838086450308, 6410107231501731012, 95136428354649665256

Offset: 0

Mikhail Kurkov, Jun 11 2023 [verification needed]

nonn

Note that [A036987(n) = 0]*b(A266341(n)) is the same as max((1 - T(n, j))*b(A053645(n) + 2^j*(1 - T(n, j))) | 0 <= j <= A000523(n)) where T(n, k) = floor(n/2^k) mod 2.

In fact b(n) is a generalization of A347205 just as A329369 is a generalization of A341392.

Cf. A000523, A023416, A036987, A053645, A266341.

Similar recurrences: A284005, A329369, A341392, A347205.

A063250(n)=my(L=logint(n, 2), A=0); for(i=0, L, my(B=n\2^(L-i)+1); A++; A-=logint(B, 2)==valuation(B, 2)); A
upto(n)=my(v, v1); v=vector(2^n, i, 0); v[1]=1; v1=vector(n+1, i, 0); v1[1]=1; for(i=1, #v-1, my(L=logint(i, 2), A=i - 2^L, B=A063250(i)); v[i+1]=(L - hammingweight(i) + 2)*v[A+1] + if(B>0, v[A + 2^(B-1) + 1])); for(i=1, n, v1[i+1]=v1[i] + sum(j=2^(i-1)+1, 2^i, v[j])); v1

A366600 a(n) = (1 + A033264(n))*a(A053645(n)) for n > 0 with a(0) = 1.

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 4, 1, 2, 2, 6, 2, 4, 4, 8, 1, 2, 2, 6, 2, 6, 6, 12, 2, 4, 4, 18, 4, 8, 8, 16, 1, 2, 2, 6, 2, 6, 6, 12, 2, 6, 6, 24, 6, 12, 12, 24, 2, 4, 4, 18, 4, 18, 18, 36, 4, 8, 8, 54, 8, 16, 16, 32, 1, 2, 2, 6, 2, 6, 6, 12, 2, 6, 6, 24, 6, 12, 12, 24, 2

Offset: 0

Mikhail Kurkov, Oct 14 2023

			a(6) = 4 because the binary expansion of 6 is 110 and we have [(10), 1(10)] -> [1, 1]. Increasing these values by 1 gives us 2*2 = 4.
a(18) = 6 because the binary expansion of 18 is 10010 and we have [(10), (10)0(10)] -> [1, 2]. Increasing these values by 1 gives us 2*3 = 6.
a(26) = 18 because the binary expansion of 26 is 11010 and we have [(10), (10)(10), 1(10)(10)] -> [1, 2, 2]. Increasing these values by 1 gives us 2*3*3 = 18.
For n=482, the bits of n and the resulting product for a(n) are
  n    = 482 = binary 1 1 1 1 0 0 0 1 0
  a(n) = 162 =        3*3*3*3      *2
n=3863 = binary 111100010111 is the same a(n) = 162 since its final trailing "111" has no effect.

Cf. A033264, A053645, A346422.

A033264[n_] := SequenceCount[IntegerDigits[n, 2], {1, 0}];
A053645[n_] := n - 2^Floor@Log2@n;
a[n_] := a[n] = If[n == 0, 1, (1 + A033264[n]) a[A053645[n]]];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Nov 14 2023 *)

a(n) = my(A = 1, B = 1); if(n, for(i=1, logint(n, 2), if(bittest(n, i), A *= (B += !bittest(n, i-1))))); A

a(2n + 1) = a(n).
a(4n) = a(2n) with a(0) = 1.
a(4n + 2) = 2*b(n), b(2n + 1) = 2*b(n), b(2n) = 3*c(n - 1, 1) with b(0) = 1.
c(2n + 1,  k) = c(n, k), c(4n + 2, k) = (k + 2)*c(2n, k), c(4n, k) = (k + 3)*c(n - 1, k + 1) with c(0, k) = 1.
Another way to compute a(4n + 2):
a(2*(4^n - 1)/3) = (n + 1)!.
a(2^(2m)*(2k + 1) + 2*(4^m - 1)/3) = (m + 1)*a(2^(2m)*k + 2*(4^m - 1)/3).
a(2^(2m + 1)*(2k + 1) + 2*(4^(m + 1) - 1)/3) = a(2^(2m + 1)*k + 2*(4^(m + 1) - 1)/3).
Note that a(4n + 2) is completely defined by these 3 last formulas. However, it looks like that it is not so easy to identify m and k for a given n, which makes these formulas useless for computing this sequence.

A005940 The Doudna sequence: write n-1 in binary; power of prime(k) in a(n) is # of 1's that are followed by k-1 0's.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 9, 8, 7, 10, 15, 12, 25, 18, 27, 16, 11, 14, 21, 20, 35, 30, 45, 24, 49, 50, 75, 36, 125, 54, 81, 32, 13, 22, 33, 28, 55, 42, 63, 40, 77, 70, 105, 60, 175, 90, 135, 48, 121, 98, 147, 100, 245, 150, 225, 72, 343, 250, 375, 108, 625, 162, 243, 64, 17, 26, 39

Offset: 1

N. J. A. Sloane and J. H. Conway

A permutation of the natural numbers. - Robert G. Wilson v, Feb 22 2005
Fixed points: A029747. - Reinhard Zumkeller, Aug 23 2006
The even bisection, when halved, gives the sequence back. - Antti Karttunen, Jun 28 2014
From Antti Karttunen, Dec 21 2014: (Start)
This irregular table can be represented as a binary tree. Each child to the left is obtained by applying A003961 to the parent, and each child to the right is obtained by doubling the parent:
                                      1
                                      |
                   ...................2...................
                  3                                       4
        5......../ \........6                   9......../ \........8
       / \                 / \                 / \                 / \
      /   \               /   \               /   \               /   \
     /     \             /     \             /     \             /     \
    7       10         15       12         25       18         27       16
  11 14   21  20     35  30   45  24     49  50   75  36    125  54   81  32
etc.
Sequence A163511 is obtained by scanning the same tree level by level, from right to left. Also in binary trees A253563 and A253565 the terms on level of the tree are some permutation of the terms present on the level n of this tree. A252464(n) gives the distance of n from 1 in all these trees.
A252737(n) gives the sum and A252738(n) the product of terms on row n (where 1 is on row 0, 2 on row 1, 3 and 4 on row 2, etc.). A252745(n) gives the number of nodes on level n whose left child is larger than the right child, A252750 the difference between left and right child for each node from node 2 onward.
(End)
-A008836(a(1+n)) gives the corresponding numerator for A323505(n). - Antti Karttunen, Jan 19 2019
(a(2n+1)-1)/2 [= A244154(n)-1, for n >= 0] is a permutation of the natural numbers. - George Beck and Antti Karttunen, Dec 08 2019
From Peter Munn, Oct 04 2020: (Start)
Each term has the same even part (equivalently, the same 2-adic valuation) as its index.
Using the tree depicted in Antti Karttunen's 2014 comment:
Numbers are on the right branch (4 and descendants) if and only if divisible by the square of their largest prime factor (cf. A070003).
Numbers on the left branch, together with 2, are listed in A102750.
(End)
According to Kutz (1981), he learned of this sequence from American mathematician Byron Leon McAllister (1929-2017) who attributed the invention of the sequence to a graduate student by the name of Doudna (first name Paul?) in the mid-1950's at the University of Wisconsin. - Amiram Eldar, Jun 17 2021
From David James Sycamore, Sep 23 2022: (Start)
Alternative (recursive) definition: If n is a power of 2 then a(n)=n. Otherwise, if 2^j is the greatest power of 2 not exceeding n, and if k = n - 2^j, then a(n) is the least m*a(k) that has not occurred previously, where m is an odd prime.
Example: Use recursion with n = 77 = 2^6 + 13. a(13) = 25 and since 11 is the smallest odd prime m such that m*a(13) has not already occurred (see a(27), a(29),a(45)), then a(77) = 11*25 = 275. (End)
The odd bisection, when transformed by replacing all prime(k)^e in a(2*n - 1) with prime(k-1)^e, returns a(n), and thus gives the sequence back. - David James Sycamore, Sep 28 2022

			From _N. J. A. Sloane_, Aug 22 2022: (Start)
Let c_i = number of 1's in binary expansion of n-1 that have i 0's to their right, and let p(j) = j-th prime.  Then a(n) = Product_i p(i+1)^c_i.
If n=9, n-1 is 1000, c_3 = 1, a(9) = p(4)^1 = 7.
If n=10, n-1 = 1001, c_0 = 1, c_2 = 1, a(10) = p(1)*p(3) = 2*5 = 10.
If n=11, n-1 = 1010, c_1 = 1, c_2 = 1, a(11) = p(2)*p(3) = 15. (End)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Antti Karttunen, Table of n, a(n) for n = 1..8192 (terms 1..1024 from Reinhard Zumkeller)
Michael De Vlieger, 6 row Doudna Tree diagram as mentioned in Comments.
Michael De Vlieger, Annotated fan-style binary tree showing 10 levels, with a color function where 2^m is shown in medium blue in row m, k < 2^m is darker blue, and k > 2^m is brighter green, with records in each row shown in red.
Ronald E. Kutz, Two unusual sequences, Two-Year College Mathematics Journal, Vol. 12, No. 5 (1981), pp. 316-319.
Index entries for sequences that are permutations of the natural numbers

Cf. A103969. Inverse is A005941 (A156552).
Cf. A125106. [From Franklin T. Adams-Watters, Mar 06 2010]
Cf. A252737 (gives row sums), A252738 (row products), A332979 (largest on row).
Related permutations of positive integers: A163511 (via A054429), A243353 (via A006068), A244154, A253563 (via A122111), A253565, A332977, A334866 (via A225546).
A000120, A003602, A003961, A006519, A053645, A070939, A246278, A250246, A252753, A253552 are used in a formula defining this sequence.
Formulas for f(a(n)) are given for f = A000265, A003963, A007949, A055396, A056239.
Numbers that occur at notable sets of positions in the binary tree representation of the sequence: A000040, A000079, A002110, A070003, A070826, A102750.
Cf. also A000142, A001511, A002450, A112798, A252463, A252464, A252745, A252750, A324054, A324106, A323505, A323508.
Cf. A106737, A290077, A323915, A324052, A324054, A324055, A324056, A324057, A324058, A324114, A324335, A324340, A324348, A324349 for various number-theoretical sequences applied to (i.e., permuted by) this sequence.
k-adic valuation: A007814 (k=2), A337821 (k=3).
Positions of multiples of 3: A091067.
Primorial deflation: A337376 / A337377.
Sum of prime indices of a(n) is A161511, reverse version A359043.
A048793 lists binary indices, ranked by A019565.
A066099 lists standard comps, partial sums A358134 (ranked by A358170).
Cf. A001222, A029837, A059893, A241916, A242628, A253566, A359042.

a005940 n = f (n - 1) 1 1 where
   f 0 y _          = y
   f x y i | m == 0 = f x' y (i + 1)
           | m == 1 = f x' (y * a000040 i) i
           where (x',m) = divMod x 2
-- Reinhard Zumkeller, Oct 03 2012
(Scheme, with memoization-macro definec from Antti Karttunen's IntSeq-library)
(define (A005940 n) (A005940off0 (- n 1))) ;; The off=1 version, utilizing any one of three different offset-0 implementations:
(definec (A005940off0 n) (cond ((< n 2) (+ 1 n)) (else (* (A000040 (- (A070939 n) (- (A000120 n) 1))) (A005940off0 (A053645 n))))))
(definec (A005940off0 n) (cond ((<= n 2) (+ 1 n)) ((even? n) (A003961 (A005940off0 (/ n 2)))) (else (* 2 (A005940off0 (/ (- n 1) 2))))))
(define (A005940off0 n) (let loop ((n n) (i 1) (x 1)) (cond ((zero? n) x) ((even? n) (loop (/ n 2) (+ i 1) x)) (else (loop (/ (- n 1) 2) i (* x (A000040 i)))))))
;; Antti Karttunen, Jun 26 2014

f := proc(n,i,x) option remember ; if n = 0 then x; elif type(n,'even') then procname(n/2,i+1,x) ; else procname((n-1)/2,i,x*ithprime(i)) ; end if; end proc:
A005940 := proc(n) f(n-1,1,1) ; end proc: # R. J. Mathar, Mar 06 2010

f[n_] := Block[{p = Partition[ Split[ Join[ IntegerDigits[n - 1, 2], {2}]], 2]}, Times @@ Flatten[ Table[q = Take[p, -i]; Prime[ Count[ Flatten[q], 0] + 1]^q[[1, 1]], {i, Length[p]}] ]]; Table[ f[n], {n, 67}] (* Robert G. Wilson v, Feb 22 2005 *)
Table[Times@@Prime/@(Join@@Position[Reverse[IntegerDigits[n,2]],1]-Range[DigitCount[n,2,1]]+1),{n,0,100}] (* Gus Wiseman, Dec 28 2022 *)

A005940(n) = { my(p=2, t=1); n--; until(!n\=2, n%2 && (t*=p) || p=nextprime(p+1)); t } \\ M. F. Hasler, Mar 07 2010; update Aug 29 2014

a(n)=my(p=2, t=1); for(i=0,exponent(n), if(bittest(n,i), t*=p, p=nextprime(p+1))); t \\ Charles R Greathouse IV, Nov 11 2021

from sympy import prime
import math
def A(n): return n - 2**int(math.floor(math.log(n, 2)))
def b(n): return n + 1 if n<2 else prime(1 + (len(bin(n)[2:]) - bin(n)[2:].count("1"))) * b(A(n))
print([b(n - 1) for n in range(1, 101)]) # Indranil Ghosh, Apr 10 2017

from math import prod
from itertools import accumulate
from collections import Counter
from sympy import prime
def A005940(n): return prod(prime(len(a)+1)**b for a, b in Counter(accumulate(bin(n-1)[2:].split('1')[:0:-1])).items()) # Chai Wah Wu, Mar 10 2023

From Reinhard Zumkeller, Aug 23 2006, R. J. Mathar, Mar 06 2010: (Start)
a(n) = f(n-1, 1, 1)
  where f(n, i, x) = x if n = 0,
                   = f(n/2, i+1, x) if n > 0 is even
                   = f((n-1)/2, i, x*prime(i)) otherwise. (End)
From Antti Karttunen, Jun 26 2014: (Start)
Define a starting-offset 0 version of this sequence as:
  b(0)=1, b(1)=2, [base cases]
and then compute the rest either with recurrence:
  b(n) = A000040(1+(A070939(n)-A000120(n))) * b(A053645(n)).
or
  b(2n) = A003961(b(n)), b(2n+1) = 2 * b(n). [Compare this to the similar recurrence given for A163511.]
Then define a(n) = b(n-1), where a(n) gives this sequence A005940 with the starting offset 1.
Can be also defined as a composition of related permutations:
a(n+1) = A243353(A006068(n)).
a(n+1) = A163511(A054429(n)). [Compare the scatter plots of this sequence and A163511 to each other.]
This permutation also maps between the partitions as enumerated in the lists A125106 and A112798, providing identities between:
A161511(n) = A056239(a(n+1)). [The corresponding sums ...]
A243499(n) = A003963(a(n+1)). [... and the products of parts of those partitions.]
(End)
From Antti Karttunen, Dec 21 2014  - Jan 04 2015: (Start)
A002110(n) =  a(1+A002450(n)). [Primorials occur at (4^n - 1)/3 in the offset-0 version of the sequence.]
a(n) = A250246(A252753(n-1)).
a(n) = A122111(A253563(n-1)).
For n >= 1, A055396(a(n+1)) = A001511(n).
For n >= 2, a(n) = A246278(1+A253552(n)).
(End)
From Peter Munn, Oct 04 2020: (Start)
A000265(a(n)) = a(A000265(n)) = A003961(a(A003602(n))).
A006519(a(n)) = a(A006519(n)) = A006519(n).
a(n) = A003961(a(A003602(n))) * A006519(n).
A007814(a(n)) = A007814(n).
A007949(a(n)) = A337821(n) = A007814(A003602(n)).
a(n) = A225546(A334866(n-1)).
(End)
a(2n) = 2*a(n), or generally a(2^k*n) = 2^k*a(n). - Amiram Eldar, Oct 03 2022
If n-1 = Sum_{i} 2^(q_i-1), then a(n) = Product_{i} prime(q_i-i+1). These are the Heinz numbers of the rows of A125106. If the offset is changed to 0, the inverse is A156552. - Gus Wiseman, Dec 28 2022

More terms from Robert G. Wilson v, Feb 22 2005
Sign in a formula switched and Maple program added by R. J. Mathar, Mar 06 2010
Binary tree illustration and keyword tabf added by Antti Karttunen, Dec 21 2014

A002262 Triangle read by rows: T(n,k) = k, 0 <= k <= n, in which row n lists the first n+1 nonnegative integers.

Original entry on oeis.org

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

Offset: 0

Angele Hamel (amh(AT)maths.soton.ac.uk)

The point with coordinates (x = A025581(n), y = A002262(n)) sweeps out the first quadrant by upwards antidiagonals. N. J. A. Sloane, Jul 17 2018
Old name: Integers 0 to n followed by integers 0 to n+1 etc.
a(n) = n - the largest triangular number <= n. - Amarnath Murthy, Dec 25 2001
The PARI functions t1, t2 can be used to read a square array T(n,k) (n >= 0, k >= 0) by antidiagonals downwards: n -> T(t1(n), t2(n)). - Michael Somos, Aug 23 2002
Values x of unique solution pair (x,y) to equation T(x+y) + x = n, where T(k)=A000217(k). - Lekraj Beedassy, Aug 21 2004
a(A000217(n)) = 0; a(A000096(n)) = n. - Reinhard Zumkeller, May 20 2009
Concatenation of the set representation of ordinal numbers, where the n-th ordinal number is represented by the set of all ordinals preceding n, 0 being represented by the empty set. - Daniel Forgues, Apr 27 2011
An integer sequence is nonnegative if and only if it is a subsequence of this sequence. - Charles R Greathouse IV, Sep 21 2011
a(A195678(n)) = A000040(n) and a(m) <> A000040(n) for m < A195678(n), an example of the preceding comment. - Reinhard Zumkeller, Sep 23 2011
A sequence B is called a reluctant sequence of sequence A, if B is triangle array read by rows: row number k coincides with first k elements of the sequence A. A002262 is reluctant sequence of 0,1,2,3,... The nonnegative integers, A001477. - Boris Putievskiy, Dec 12 2012

			From _Daniel Forgues_, Apr 27 2011: (Start)
Examples of set-theoretic representation of ordinal numbers:
  0: {}
  1: {0} = {{}}
  2: {0, 1} = {0, {0}} = {{}, {{}}}
  3: {0, 1, 2} = {{}, {0}, {0, 1}} = ... = {{}, {{}}, {{}, {{}}}} (End)
From _Omar E. Pol_, Jul 15 2012: (Start)
  0;
  0, 1;
  0, 1, 2;
  0, 1, 2, 3;
  0, 1, 2, 3, 4;
  0, 1, 2, 3, 4, 5;
  0, 1, 2, 3, 4, 5, 6;
  0, 1, 2, 3, 4, 5, 6, 7;
  0, 1, 2, 3, 4, 5, 6, 7, 8;
  0, 1, 2, 3, 4, 5, 6, 7, 8, 9;
  0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10;
(End)

Charles R Greathouse IV, Rows n = 0..100, flattened
Boris Putievskiy, Transformations [Of] Integer Sequences And Pairing Functions, arXiv preprint arXiv:1212.2732 [math.CO], 2012.
Michael Somos, Sequences used for indexing triangular or square arrays

Cf. A002024, A002260, A004736, A025581, A025675, A025682.
Cf. A025691, A048645, A053186, A053645, A056558, A127324.
As a sequence, essentially same as A048151.
Cf. A060510 (parity).

a002262 n k = a002262_tabl !! n !! k
a002262_row n = a002262_tabl !! n
a002262_tabl = map (enumFromTo 0) [0..]
a002262_list = concat a002262_tabl
-- Reinhard Zumkeller, Aug 05 2015, Jul 13 2012, Mar 07 2011

seq(seq(i,i=0..n),n=0..14); # Peter Luschny, Sep 22 2011
A002262 := n -> n - binomial(floor((1/2)+sqrt(2*(1+n))),2);

m[n_]:= Floor[(-1 + Sqrt[8n - 7])/2]
b[n_]:= n - m[n] (m[n] + 1)/2
Table[m[n], {n, 1, 105}]     (* A003056 *)
Table[b[n], {n, 1, 105}]     (* A002260 *)
Table[b[n] - 1, {n, 1, 120}] (* A002262 *)
(* Clark Kimberling, Jun 14 2011 *)
Flatten[Table[k, {n, 0, 14}, {k, 0, n}]] (* Alonso del Arte, Sep 21 2011 *)
Flatten[Table[Range[0,n], {n,0,15}]] (* Harvey P. Dale, Jan 31 2015 *)

PARI
```
a(n)=n-binomial(round(sqrt(2+2*n)),2)
```

t1(n)=n-binomial(floor(1/2+sqrt(2+2*n)),2) /* A002262, this sequence */

t2(n)=binomial(floor(3/2+sqrt(2+2*n)),2)-(n+1) /* A025581, cf. comment by Somos for reading arrays by antidiagonals */

concat(vector(15,n,vector(n,i,i-1)))  \\ M. F. Hasler, Sep 21 2011

apply( {A002262(n)=n-binomial(sqrtint(8*n+8)\/2,2)}, [0..99]) \\ M. F. Hasler, Oct 20 2022

for i in range(16):
    for j in range(i):
        print(j, end=", ") # Mohammad Saleh Dinparvar, May 13 2020

from math import comb, isqrt
def a(n): return n - comb((1+isqrt(8+8*n))//2, 2)
print([a(n) for n in range(105)]) # Michael S. Branicky, May 07 2023

a(n) = A002260(n) - 1.
a(n) = n - (trinv(n)*(trinv(n)-1))/2; trinv := n -> floor((1+sqrt(1+8*n))/2) (cf. A002024); # gives integral inverses of triangular numbers
a(n) = n - A000217(A003056(n)) = n - A057944(n). - Lekraj Beedassy, Aug 21 2004
a(n) = A140129(A023758(n+2)). - Reinhard Zumkeller, May 14 2008
a(n) = f(n,1) with f(n,m) = if nReinhard Zumkeller, May 20 2009
a(n) = (1/2)*(t - t^2 + 2*n), where t = floor(sqrt(2*n+1) + 1/2) = round(sqrt(2*n+1)). - Ridouane Oudra, Dec 01 2019
a(n) = ceiling((-1 + sqrt(9 + 8*n))/2) * (1 - ((1/2)*ceiling((1 + sqrt(9 + 8*n))/2))) + n. - Ryan Jean, Sep 03 2022
G.f.: x*y/((1 - x)*(1 - x*y)^2). - Stefano Spezia, Feb 21 2024

New name from Omar E. Pol, Jul 15 2012

Typo in definition fixed by Reinhard Zumkeller, Aug 05 2015

A003188 Decimal equivalent of Gray code for n.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

Inverse of sequence A006068 considered as a permutation of the nonnegative integers, i.e., A006068(A003188(n)) = n = A003188(A006068(n)). - Howard A. Landman, Sep 25 2001
Restricts to a permutation of each {2^(i - 1) .. 2^i - 1}. - Jason Kimberley, Apr 02 2012
a(n) mod 2 = floor(((n + 1) mod 4) / 2), see also A021913. - Reinhard Zumkeller, Apr 28 2012
Invented by Emile Baudot (1845-1903), originally called a "cyclic-permuted" code. Gray codes are named after Frank Gray, who patented their use for shaft encoders in 1953. [F. Gray, "Pulse Code Communication", U.S. Patent 2,632,058, March 17, 1953.] - Robert G. Wilson v, Jun 22 2014
For n >= 2, let G_n be the graph whose vertices are labeled as 0,1,...,2^n-1, and two vertices are adjacent if and only if their binary expansions differ in exactly one bit, then a(0),a(1),...,a(2^n-1),a(0) is a Hamilton cycle in G_n. - Jianing Song, Jun 01 2022

			For n = 13, the binary reflected Gray code representation of n is '1011' and 1011_2 = 11_10. So, a(13) = 11. - _Indranil Ghosh_, Jan 23 2017

M. Gardner, Mathematical Games, Sci. Amer. Vol. 227 (No. 2, Feb. 1972), p. 107.
M. Gardner, Knotted Doughnuts and Other Mathematical Entertainments. Freeman, NY, 1986, p. 15.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Indranil Ghosh, Table of n, a(n) for n = 0..32767 (first 1001 terms from N. J. A. Sloane)
M. W. Bunder, K. P. Tognetti, and G. E. Wheeler, On binary reflected Gray codes and functions, Discr. Math., 308 (2008), 1690-1700.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
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, p. 39.
P. Mathonet, M. Rigo, M. Stipulanti and N. Zénaïdi, On digital sequences associated with Pascal's triangle, arXiv:2201.06636 [math.NT], 2022.
J. A. Oteo and J. Ros, A Fractal Set from the Binary Reflected Gray Code, J. Phys. A: Math Gen. 38 (2005) 8935-8949.
Ed Pegg, Jr., Sequence Pictures, Math Games column, Dec 08 2003.
Ed Pegg, Jr., Sequence Pictures, Math Games column, Dec 08 2003 [Cached copy, with permission (pdf only)]
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Paul Tarau, Isomorphic Data Encodings and their Generalization to Hylomorphisms on Hereditarily Finite Data Types
Pierluigi Vellucci and Alberto Maria Bersani, Ordering of nested square roots of 2 according to Gray code, arXiv:1604.00222 [math.NT], 2016.
Index entries for sequences that are permutations of the natural numbers

a(2*A003714(n)) = 3*A003714(n) for all n. - Antti Karttunen, Apr 26 1999
Cf. A014550 (in binary), A055975 (first differences), A048724 (even bisection), A065621 (odd bisection).
Cf. A006068, A038554, A048641, A048642.

C
```
int a(int n) { return n ^ (n>>1); }
```

import Data.Bits (xor, shiftR)
a003188 n = n `xor` (shiftR n 1) :: Integer
-- Reinhard Zumkeller, May 26 2013, Apr 28 2012

// A recursive algorithm
N := 10; s := [[]];
for n in [1..N] do
for j in [#s..1 by -1] do
   Append(~s,Append(s[j],1));
   Append(~s[j],0);
end for;
end for;
[SequenceToInteger(b,2):b in s]; // Jason Kimberley, Apr 02 2012

// A direct algorithm
I2B := func< i | [b eq 1: b in IntegerToSequence(i,2)]>;
B2I := func< s | SequenceToInteger([b select 1 else 0:b in s],2)>;
[B2I(Xor(I2B(i),I2B(i div 2)cat[false])):i in [1..127]]; //Jason Kimberley, Apr 02 2012

with(combinat); graycode(6); # to produce first 64 terms
printf(cat(` %.6d`$64), op(map(convert, graycode(6), binary))); lprint(); # to produce binary strings
# alternative:
read("transforms"):
A003188 := proc(n)
    XORnos(n,floor(n/2)) ;
end proc: # R. J. Mathar, Mar 09 2015
# another Maple program:
a:= n-> Bits[Xor](n, iquo(n, 2)):
seq(a(n), n=0..70);  # Alois P. Heinz, Aug 16 2020

f[n_] := BitXor[n, Floor[n/2]]; Array[f, 70, 0] (* Robert G. Wilson v, Jun 09 2010 *)

PARI
```
a(n)=bitxor(n,n>>1);
```

a(n)=sum(k=1,n,(-1)^((k/2^valuation(k,2)-1)/2)*2^valuation(k,2))

def A003188(n):
    return int(bin(n^(n//2))[2:],2) # Indranil Ghosh, Jan 23 2017

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

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, Apr 10 2020
(C#)
static uint a(this uint n) => (n >> 1) ^ n; // Frank Hollstein, Mar 12 2021

a(n) = 2*a(floor(n/2)) + A021913(n - 1). - Henry Bottomley, Apr 05 2001
a(n) = n XOR floor(n/2), where XOR is the binary exclusive OR operator. - Paul D. Hanna, Jun 04 2002
G.f.: (1/(1-x)) * Sum_{k>=0} 2^k*x^2^k/(1 + x^2^(k+1)). - Ralf Stephan, May 06 2003
a(0) = 0, a(2n) = 2a(n) + [n odd], a(2n + 1) = 2a(n) + [n even]. - Ralf Stephan, Oct 20 2003
a(0) = 0, a(n) = 2 a(floor(n/2)) + mod(floor((n + 1)/2), 2).
a(n) = Sum_{k=1..n} 2^A007814(k) * (-1)^((k/2^A007814(k) - 1)/2). - Ralf Stephan, Oct 29 2003
a(0) = 0, a(n + 1) = a(n) XOR 2^A007814(n) - Jaume Simon Gispert (jaume(AT)nuem.com), Sep 11 2004
Inverse of sequence A006068. - Philippe Deléham, Apr 29 2005
a(n) = a(n-1) XOR A006519(n). - Franklin T. Adams-Watters, Jul 18 2011
From Mikhail Kurkov, Sep 27 2023: (Start)
a(2^m + k) = a(2^m - k - 1) + 2^m for 0 <= k < 2^m, m >= 0.
a(n) = a(A053645(A054429(n))) + A053644(n) for n > 0.
a(n) = A063946(a(A053645(n)) + A053644(n)) for n > 0. (End)

Previous Showing 11-20 of 91 results. Next

cp's OEIS Frontend

A085183 a(n) = A053645(A057520(n)), i.e., the terms of A014486 without their most significant bit (1) and the least significant bit (0).

Views

Author

Keywords

Crossrefs

A160588 Interleaving of A053645 and A000027.

Views

Author

Keywords

Comments

Links

Programs

Haskell

Formula

Extensions

A257697 a(n)=0 for n <= 1; for n >= 2, a(n) = largest number that can be obtained by rotating non-msb bits of binary expansion of n (with A080541 or A080542), without the most significant bit of n: a(n) = A053645(A256999(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

Formula

A258159 Numbers n such that A053645(n) (n with the most significant binary digit removed) divides A004526(n) (n with the least significant binary digit removed).

Views

Author

Keywords

Comments

Links

Programs

Mathematica

A380645 The expansion of the Stieltjes continued fraction 1/(1 - x/(1 - a(A053645(0))*x/(1 - a(A053645(1))*x/(1 - a(A053645(2))*x/...)))) gives the sequence itself.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A363417 a(n) = Sum_{j=0..2^n - 1} b(j) for n >= 0 where b(n) = (A023416(n) + 1)*b(A053645(n)) + [A036987(n) = 0]*b(A266341(n)) for n > 0 with b(0) = 1.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

A366600 a(n) = (1 + A033264(n))*a(A053645(n)) for n > 0 with a(0) = 1.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A005940 The Doudna sequence: write n-1 in binary; power of prime(k) in a(n) is # of 1's that are followed by k-1 0's.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Python

Formula

A380645 The expansion of the Stieltjes continued fraction 1/(1 - x/(1 - a(A053645(0))x/(1 - a(A053645(1))x/(1 - a(A053645(2))*x/...)))) gives the sequence itself.

A363417 a(n) = Sum_{j=0..2^n - 1} b(j) for n >= 0 where b(n) = (A023416(n) + 1)b(A053645(n)) + [A036987(n) = 0]b(A266341(n)) for n > 0 with b(0) = 1.