A053645 -id:A053645 - cp's OEIS frontend

A073121 a(n) = ra(ceiling(n/2)) + sa(floor(n/2)) with a(1)=1 and (r,s)=(2,2).

1, 4, 10, 16, 28, 40, 52, 64, 88, 112, 136, 160, 184, 208, 232, 256, 304, 352, 400, 448, 496, 544, 592, 640, 688, 736, 784, 832, 880, 928, 976, 1024, 1120, 1216, 1312, 1408, 1504, 1600, 1696, 1792, 1888, 1984, 2080, 2176, 2272, 2368, 2464, 2560, 2656, 2752

Offset: 1

Jeffrey Shallit, Aug 25 2002

nonn

A recurrence occurring in the analysis of a regular expression algorithm.

			a(1)=1, a(2) = 2*(a(1)+a(1)) = 4, a(3) = 2*(a(2)+a(1)) = 10.

K. Ellul, J. Shallit and M.-w. Wang, Regular expressions: new results and open problems, in Descriptional Complexity of Formal Systems (DCFS), Proceedings of workshop, London, Ontario, Canada, 21-24 August 2002, pp. 17-34.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
Jean-Paul Allouche and Jeffrey Shallit, The Ring of k-regular Sequences, II
F. Barbero, G. Gutin, M. Jones, and B. Sheng, Parameterized and approximation algorithms for the load coloring problem, Algorithmica 79, No. 1, 211-229 (2017). Prop 3.
Keh-Ning Chang and Shi-Chun Tsai, Exact solution of a minimal recurrence, Inform. Process. Lett. 75 (2000), 61-64.
Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, Joseph S. B. Mitchell, Ronald L. Rivest, and Mihai Patrascu, Picture-Hanging Puzzles, arXiv:1203.3602 [cs.DS], 2012-2014.
Keith Ellul, Bryan Krawetz, Jeffrey Shallit, and Ming-wei Wang, Regular expressions: new results and open problems, Journal of Automata, Languages and Combinatorics, preprint.
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. 27, 37.
Jean-Marc Luck, Revisiting log-periodic oscillations, arXiv:2403.00432 [cond-mat.stat-mech], 2024. See p. 14.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions

Cf. A053644, A053645, A254575.

Sequences of form a(n) = r*a(ceiling(n/2)) + s*a(floor(n/2)), a(1)=1, for (r,s) = (1,1), (1,2), (2,1), (1,3), (2,2), (3,1), (1,4), (2,3), (3,2), (4,1): A000027, A006046, A064194, A130665, A073121, A268524, A116520, A268525, A268526, A268527.

a073121 n = a053644 n * (fromIntegral n + 2 * a053645 n)
-- Reinhard Zumkeller, Mar 23 2012

a:= proc(n) option remember; `if`(n=1, 1,
      2*((m-> a(m)+a(n-m))(iquo(n, 2))))
    end:
seq(a(n), n=1..70);  # Alois P. Heinz, Feb 01 2015

a[n_] := a[n] = If[n == 1, 1, 2*(a[Quotient[n, 2]] + a[n - Quotient[n, 2]])]; Table[a[n], {n, 1, 70}] (* Jean-François Alcover, Feb 24 2016, after Alois P. Heinz *)
a[ n_] := If[ n < 1, 0, Module[{m = 1, A = 1}, While[m < n, m *= 2; A = (Normal[A] /. x -> x^2) 2 (1 + x)^2 - 1 + O[x]^m]; Coefficient[A, x, n - 1]]]; (* Michael Somos, Jul 04 2017 *)

{a(n) = n--; if( n<0, 0, my(m=1, A = 1 + O(x)); while(m<=n, m*=2; A = subst(A, x, x^2) * 2 * (1 + x)^2 - 1); polcoeff(A, n))}; /* Michael Somos, Jul 04 2017 */

a(n) = 2*(a(floor(n/2)) + a(ceiling(n/2))) for n >= 2; alternatively, a(n) = 2^c(n+2b) where n = 2^c + b, 0 <= b < 2^c.
a(n) == 1 (mod 3), a(n+1)-a(n) = 3*A053644(n). If k >= 1: a(2^k)=4^k, a(3*2^k)=(10/9)*4^k. More generally a(m*2^k) = a(m)*4^k. Hence for any n, n^2 <= a(n) <= C*n^2 where C is a constant 1.125 < C < 1.14 and it seems that C = lim_{k->infinity} a(A001045(k))/A001045(k)^2 where A001045(k) =(2^n - (-1)^n)/3 is the Jacobsthal sequence. In other words, in the range 2^k <= n <= 2^(k+1) the maximum of a(n)/n^2 is reached for the only possible n in the Jacobsthal sequence. - Benoit Cloitre, Aug 26 2002
For any n, n^2 <= a(n) <= 9/8 * n^2. - Arnoud van der Leer, Sep 01 2019
a(n) = 2*(a(floor(n/2)) + a(ceiling(n/2))) for n >= 2; alternatively, a(n) = 2^c(n+2b) where n = 2^c + b, 0 <= b < 2^c
G.f.: 3*x/(1-x)^2 * ((2*x+1)/3 + Sum_{k>=1} 2^(k-1)*x^2^k). - Ralf Stephan, Apr 18 2003
G.f.: A(x) = 2 * (1/x + 2 + x) * A(x^2) - x. - Michael Somos, Jul 04 2017

Edited by N. J. A. Sloane, Feb 16 2016

A164349 The limit of the string "0, 1" under the operation 'repeat string twice and remove last symbol'.

Original entry on oeis.org

0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1

Offset: 0

Jack W Grahl, Aug 13 2009

We start with the string 01, at each step we replace the string by two concatenated copies and remove the last symbol.
01 -> 010 -> 01001 -> 010010100 etc.
Each string consists of 2^n + 1 symbols and clearly after this step the first 2^n + 1 symbols do not change.
Equivalently this sequence is given as follows: a(0) = 0, a(1) = 1, and for n>1, a(n) = first one of g(n), g(g(n)), g(g(g(n))).. etc. to be either 0 or 1, where g(n) = A053645(n-1).
The proportion of 0's in this sequence converges to a number close to 0.645059. The exact nature of this constant is not known. It is easy to show there are no 2 consecutive 1's.
Start of the first occurrence of k consecutive zeros: 0, 2, 7, 2046, > 8388600, ..., . - Robert G. Wilson v, Aug 17 2009
Start of the first occurrence of 5 consecutive zeros is > 2^34 - 5. Sum of the first 10^n terms b(n) begins: 0, 3, 36, 355, 3549, 35494, 354942, 3549412, 35494122, 354941215, 3549412151. - Alex Ratushnyak, Aug 15 2012
a(A246439(n)) = 1; a(A246438(n)) = 0. - Reinhard Zumkeller, Aug 28 2014
The partial sums appear to give A101402. - Arie Groeneveld, Aug 27 2014

Robert G. Wilson v, Table of n, a(n) for n = 0..16384

Cf. A053645, A246438, A246439, A101402.

a164349 n = if n == 0 then 0 else until (<= 1) (a053645 . subtract 1) n
-- Reinhard Zumkeller, Aug 28 2014

Nest[ Most@ Flatten@ {#, #} &, {0, 1}, 7] (* Robert G. Wilson v, Aug 17 2009 *)

my $ab = "10"; for (my $j = 1; $j < 30; $j++) { $ab .= $ab; substr $ab, -1, 1, ""; print "$ab\n"; }

Spelling and notation corrected by Charles R Greathouse IV, Mar 23 2010

A284001 a(n) = A005361(A283477(n)).

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 4, 6, 1, 2, 4, 6, 8, 12, 18, 24, 1, 2, 4, 6, 8, 12, 18, 24, 16, 24, 36, 48, 54, 72, 96, 120, 1, 2, 4, 6, 8, 12, 18, 24, 16, 24, 36, 48, 54, 72, 96, 120, 32, 48, 72, 96, 108, 144, 192, 240, 162, 216, 288, 360, 384, 480, 600, 720, 1, 2, 4, 6, 8, 12, 18, 24, 16, 24, 36, 48, 54, 72, 96, 120, 32, 48, 72, 96, 108, 144, 192, 240, 162, 216, 288, 360, 384, 480

Offset: 0

Antti Karttunen, Mar 18 2017

a(n) is the product of elements of the multiset that covers an initial interval of positive integers with multiplicities equal to the parts of the n-th composition in standard order (graded reverse-lexicographic, A066099). This composition is obtained by taking the set of positions of 1's in the reversed binary expansion of n, prepending 0, taking first differences, and reversing again. For example, the 13th composition is (1,2,1) giving the multiset {1,2,2,3} with product 12, so a(13) = 12. - Gus Wiseman, Apr 26 2020

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

Cf. A005361, A283477, A284002, A284005.
Row products of A095684.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Weighted sum is A029931.
- Necklaces are A065609.
- Sum is A070939.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Lyndon words are A275692.
- Distinct parts are counted by A334028.
Cf. A003963, A034691, A053645, A057335, A305936, A318284, A333764, A333940, A333942, A334030.

Table[Times @@ FactorInteger[#][[All, -1]] &[Times @@ Map[#1^#2 & @@ # &, FactorInteger[#] /. {p_, e_} /; e == 1 :> {Times @@ Prime@ Range@ PrimePi@ p, e}] &[Times @@ Prime@ Flatten@ Position[#, 1] &@ Reverse@ IntegerDigits[n, 2]]], {n, 0, 93}] (* Michael De Vlieger, Mar 18 2017 *)

A005361(n) = factorback(factor(n)[, 2]); \\ From A005361
A034386(n) = prod(i=1, primepi(n), prime(i));
A108951(n) = { my(f=factor(n)); prod(i=1, #f~, A034386(f[i, 1])^f[i, 2]) };  \\ From A108951
A019565(n) = {my(j,v); factorback(Mat(vector(if(n, #n=vecextract(binary(n), "-1..1")), j, [prime(j), n[j]])~))}; \\ From A019565
A283477(n) = A108951(A019565(n));
A284001(n) = A005361(A283477(n));

(define (A284001 n) (A005361 (A283477 n)))

a(n) = A005361(A283477(n)).
a(n) = A003963(A057335(n)). - Gus Wiseman, Apr 26 2020
a(n) = A284005(A053645(n)) for n > 0 with a(0) = 1. - Mikhail Kurkov, Jun 05 2021 [verification needed]

A101402 a(0)=0, a(1)=1; for n>=2, let k = smallest power of 2 that is >= n, then a(n) = a(k/2) + a(n-1-k/2).

Original entry on oeis.org

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

Offset: 0

Odimar Fabeny, Jan 16 2005

Either a(n) = a(n-1) or a(n) = a(n-1) + 1. Proof: Suppose n is a power of 2, then a(n+1) = a(n) + a(0) = a(n). Otherwise let 2m be the largest power of 2 greater than n, so a(n) = a(m) + a(n-1-m) and a(n+1) = a(m) + a(n-m) and then proceed by induction. - Charles R Greathouse IV, Aug 27 2014
It appears that this sequence gives the partial sums of A164349. - Arie Groeneveld, Aug 27 2014
Each term other than zero appears at least twice. Suppose m is a power of 2, then a(2m) and a(4m) appear at least twice by my above comment. Otherwise suppose 3 <= k+2 <= 2m, then a(2m+k) = a(m) + a(m+k-1), a(2m+k+1) = a(m) + a(2m+k), and a(2m+k+2) = a(m) + a(m) + a(m+k+1), so a(2m+k+2) - a(2m+k) = a(m+k+1) - a(m+k-1). So if each term from a(m) to a(2m) appears at least twice then so will each term in a(2m) to a(4m). - Charles R Greathouse IV, Sep 10 2014
a(n) = Theta(n), see link. - Benoit Jubin, Sep 16 2014
The position of where n first appears: 0, 1, 4, 6, 10, 13, 15, 18, 21, 23, 27, 30, 32, 34, 37, 39, 43, 46, 48, 51, 54, 56, 60, 63, 66, 69, ... - Robert G. Wilson v, Sep 19 2014
The (10^k)-th term: 0, 3, 36, 355, 3549, 35494, 354942, ... - Robert G. Wilson v, Sep 19 2014

			a(2) = a(1) + a(0) = 1 = 1 + 0;
a(3) = a(2) + a(0) = 1 = 1 + 0;
a(4) = a(2) + a(1) = 2 = 1 + 1;
a(5) = a(4) + a(0) = 2 = 2 + 0;
a(6) = a(4) + a(1) = 3 = 2 + 1;
a(7) = a(4) + a(2) = 3 = 2 + 1;
a(8) = a(4) + a(3) = 3 = 2 + 1;
a(9) = a(8) + a(0) = 3 = 3 + 0; ...
The terms fall naturally into blocks of sizes 1,1,1,2,4,8,16,32,...:
0,
1,
1,
1, 2,
2, 3, 3, 3,
3, 4, 4, 4, 5, 5, 6, 6,
6, 7, 7, 7, 8, 8, 9, 9, 9, 9, 10, 10, 10, 11, 11, 12,
12, 13, 13, 13, 14, 14, ...
Then the definition says that the k-th block is the final term of the previous block added to the sequence starting from the beginning (e.g., 34445566 = 3 + 01112233).
The final terms of the blocks, a(2^k), appear to be given by A164363. - _N. J. A. Sloane_, Aug 27 2014

Charles R Greathouse IV, Table of n, a(n) for n = 0..10000
Benoit Jubin, Proof that A101402(n) = Theta(n)

Cf. A101403, A101404, A000045, A164363, A164369, A053644, A053645, A062383.

import Data.Function (on); import Data.List (genericIndex)
a101402 = genericIndex a101402_list
a101402_list = 0 : 1 : zipWith ((+) `on` a101402)
                       (tail a053644_list) a053645_list
-- Reinhard Zumkeller, Aug 27 2014

a[0] = 0; a[1] = 1; a[n_] := a[n] = Block[{p = 2^(Ceiling[Log[2, n]] - 1)}, a[p] + a[n - 1 - p]]; Table[ a@n, {n, 0, 100}] (* Robert G. Wilson v, Aug 17 2009 *)

a(n)=if(n<4, n>0, my(k=2^(log(n-.5)\log(2))); a(k) + a(n-1-k)) \\ Charles R Greathouse IV, Aug 25 2014

For n > 1: a(n) = a(A053644(n-1)) + a(A053645(n-1)). - Reinhard Zumkeller, Aug 27 2014

Offset corrected by R. J. Mathar, Aug 17 2009

More terms from Robert G. Wilson v, Aug 17 2009

A007549 Number of increasing rooted connected graphs where every block is a complete graph.

Original entry on oeis.org

1, 1, 3, 14, 89, 716, 6967, 79524, 1041541, 15393100, 253377811, 4596600004, 91112351537, 1959073928124, 45414287553455, 1129046241331316, 29965290866974493, 845605519848379436, 25282324544244718411, 798348403914242674980, 26549922456617388029641

Offset: 1

N. J. A. Sloane

In an increasing rooted graph, nodes are numbered and the numbers increase as you move away from the root.

(a(n+1)/a(n))/n tends to 1/A073003 = 1.676875... (same limit as A029768). - Vaclav Kotesovec, Jul 26 2014

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

Vaclav Kotesovec, Table of n, a(n) for n = 1..410 (first 200 terms from Vincenzo Librandi)
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to arXiv version]
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]

Cf. A007563, A030019, A035051-A035053.
Cf. A029768.
Row sums of A078341. Column k=1 of A264436.

exptr:= proc(p) local g; g:= proc(n) option remember; p(n) +add(binomial(n-1, k-1) *p(k) *g(n-k), k=1..n-1) end: end: b:= exptr(exptr(a)): a:= n-> `if`(n=0, 1, b(n-1)): seq(a(n), n=1..30); # Alois P. Heinz, Oct 07 2008

exptr[p_] := Module[{g}, g[n_] := g[n] = p[n] + Sum[ Binomial[n-1, k-1]*p[k]*g[n-k], {k, 1, n-1}]; g]; b = exptr[ exptr[a] ]; a[n_] := If[n == 0, 1, b[n-1]]; Table[ a[n], {n, 1, 19}] (* Jean-François Alcover, May 10 2012, after Alois P. Heinz *)

Shifts left when exponentiated twice.
Conjecture: a(n) = Sum_{i=0..2^(n-2) - 1} b(i) for n > 1 with a(1) = 1 where b(n) = (L(n) + 2)*b(f(n)) + Sum_{k=0..L(n) - 1} (1 - R(n,k))*b(f(n) + 2^k*(1 - R(n,k))) for n > 0 with b(0) = 1, L(n) = A000523(n), f(n) = A053645(n) and where R(n,k) = floor(n/2^k) mod 2. Here R(n,k) is the (k+1)-th bit from the right side in the binary expansion of n. - Mikhail Kurkov, Jul 21 2024
Conjecture: a(n) = D^(n-1)(exp(x)) evaluated at x = 0, where D denotes the operator exp(x)*(1 + x)*d/dx. - Peter Bala, Feb 24 2025

New description from Christian G. Bower, Oct 15 1998

A091932 Primes that remain prime when their leading digit in binary representation is replaced by 0.

Original entry on oeis.org

7, 11, 13, 19, 23, 29, 37, 43, 61, 67, 71, 83, 101, 107, 131, 139, 151, 157, 181, 199, 211, 229, 241, 263, 269, 293, 317, 353, 359, 383, 419, 449, 467, 479, 523, 541, 571, 601, 613, 619, 643, 661, 691, 709, 739, 751, 769, 823, 829, 859, 991, 1021, 1031, 1061

Offset: 1

Reinhard Zumkeller, Feb 14 2004

nonn

A053645(a(n)) is prime.

Primes p such that p - 2^floor(log_2(p)) is prime - T. D. Noe, Apr 08 2011

			A000040(12)=37 --> '100101' --> '[1]00101' --> '[0]00101' --> '101' --> 5, therefore 37 is a term.

T. D. Noe, Table of n, a(n) for n = 1..1000

Cf. A091931.

Cf. A118958.

Select[Prime[Range[100]], PrimeQ[# - 2^Floor[Log[2, #]]] &] (* T. D. Noe, Apr 08 2011 *)
Select[Prime[Range[200]],PrimeQ[FromDigits[Rest[ IntegerDigits[ #,2]],2]]&] (* Harvey P. Dale, Apr 08 2016 *)

from sympy import isprime, primerange
def ok(p): return isprime((1 << (p.bit_length()-1)) ^ p)
def aupto(lim): return [p for p in primerange(1, lim+1) if ok(p)]
print(aupto(1061)) # Michael S. Branicky, Jul 11 2021

A118953(A049084(a(n))) = 1; subsequence of A065380. - Reinhard Zumkeller, May 07 2006

A038556 Periodic derivative of n.

Original entry on oeis.org

0, 0, 3, 0, 5, 6, 3, 0, 9, 10, 15, 12, 5, 6, 3, 0, 17, 18, 23, 20, 29, 30, 27, 24, 9, 10, 15, 12, 5, 6, 3, 0, 33, 34, 39, 36, 45, 46, 43, 40, 57, 58, 63, 60, 53, 54, 51, 48, 17, 18, 23, 20, 29, 30, 27, 24, 9, 10, 15, 12, 5, 6, 3, 0, 65, 66, 71, 68, 77, 78, 75, 72, 89, 90, 95, 92, 85

Offset: 0

N. J. A. Sloane

Every term is an evil number (A001969) and every evil number occurs an infinite number of times in this sequence. Observe self-similarity in the graph of the sequence. - T. D. Noe, Jun 22 2007

			11=1011->1100 so a(11)=12.

Simmons, G. J. The structure of the differentiation digraphs of binary sequences. Ars Combin. 35 (1993), A, 71-88. Math. Rev. 95f:05052.

T. D. Noe, Table of n, a(n) for n=0..4096

Cf. A038554, A038557.

Cf. A053645.

import Data.Bits (xor)
a038556 n = n `xor` (a053645 $ 2 * n + 1) :: Integer

a[n_] := With[{bits = IntegerDigits[n, 2]}, FromDigits[ Thread[ BitXor[ bits, RotateLeft[bits]]], 2]]; Table[a[n], {n, 0, 76}] (* Jean-François Alcover, Aug 06 2012, from 2nd formula *)

If n=b_k b_{k-1} ... b_0 in base 2, a(n) is number with binary expansion (b_k+b_{k-1}) (b_{k-1}+b_{k-2}) ... (b_1+b_0) (b_0+b_{k}). Also n XOR (n rotate 1).

More terms from Naohiro Nomoto, Apr 08 2001

A122155 Simple involution of natural numbers: List each block of (2^k)-1 numbers (from (2^k)+1 to 2^(k+1) - 1) in reverse order and fix the powers of 2.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Aug 25 2006

nonn

From Kevin Ryde, Dec 29 2020: (Start)
a(n) is n with an 0<->1 complement applied to each bit between, but not including, the most significant and least significant 1-bits.  Dijkstra uses this form and calls the complemented bits the "internal" digits.
The fixed points a(n)=n are n=0 and n=A029744.  These are n=2^k by construction, and the middle of each reversed block is n=3*2^k.  In terms of bit complement, these n have nothing between their highest and lowest 1-bits.
(End)

			From _Kevin Ryde_, Dec 29 2020: (Start)
  n    = 4, 5, 6, 7, 8
  a(n) = 4, 7, 6, 5, 8  between powers of 2
             <----      block reverse
Or a single term by bits,
  n    = 236 = binary 11101100
  a(n) = 148 = binary 10010100  complement between
                       ^^^^     high and low 1's
(End)

Michael De Vlieger, Table of n, a(n) for n = 0..16384
Edsger W. Dijkstra, More about the function ``fusc'', 1976. Reprinted in Edsger W. Dijkstra, Selected Writings on Computing, Springer-Verlag, 1982, pages 230-232.
Index entries for sequences that are permutations of the natural numbers

Cf. A054429, A122198, A122199.

Cf. A029744 (fixed points), A334045 (complement high/low 1's too), A057889 (bit reversal).

Array[(1 + Boole[#1 - #2 != 0]) #2 - #1 + #2 & @@ {#, 2^(IntegerLength[#, 2] - 1)} &, 69] (* Michael De Vlieger, Jan 01 2023 *)

a(n) = bitxor(n,if(n,max(0, 1<Kevin Ryde, Dec 29 2020

def A122155(n): return int(('1'if (m:=len(s:=bin(n)[2:])-(n&-n).bit_length())>0 else '')+''.join(str(int(d)^1) for d in s[1:m])+s[m:],2) if n else 0 # Chai Wah Wu, May 19 2023

def A122155(n): return n^((1<Chai Wah Wu, Mar 10 2025

maxblock <- 5 # by choice
a <- 1
for(m in 1:maxblock){
                      a[2^m    ] <- 2^m
  for(k in 1:(2^m-1)) a[2^m + k] <- 2^(m+1) - k
}
(a <- c(0,a))
# Yosu Yurramendi, Mar 18 2021

(define (A122155 n) (cond ((< n 1) n) ((pow2? n) n) (else (- (* 2 (A053644 n)) (A053645 n)))))
(define (pow2? n) (and (> n 0) (zero? (A004198bi n (- n 1)))))

a(0) = 0; if n=2^k, a(n) = n; if n=2^k + i (with i > 0 and i < 2^k) a(n) = 2^(k+1) - i = 2*A053644(n) - A053645(n).

A002487(a(n)) = A002487(n), n >= 0 [Dijkstra]. - Yosu Yurramendi, Mar 18 2021

A344836 Square array T(n, k), n, k >= 0, read by antidiagonals; T(n, k) = (n * 2^max(0, w(k)-w(n))) XOR (k * 2^max(0, w(n)-w(k))) (where XOR denotes the bitwise XOR operator and w = A070939).

Original entry on oeis.org

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

Offset: 0

Rémy Sigrist, May 29 2021

In other words, we right pad the binary expansion of the lesser of n and k with zeros (provided it is positive) so that both numbers have the same number of binary digits, and then apply the bitwise XOR operator.

			Array T(n, k) begins:
  n\k|   0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15
  ---+-------------------------------------------------------
    0|   0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15
    1|   1  0  0  1  0  1  2  3  0  1   2   3   4   5   6   7
    2|   2  0  0  1  0  1  2  3  0  1   2   3   4   5   6   7
    3|   3  1  1  0  2  3  0  1  4  5   6   7   0   1   2   3
    4|   4  0  0  2  0  1  2  3  0  1   2   3   4   5   6   7
    5|   5  1  1  3  1  0  3  2  2  3   0   1   6   7   4   5
    6|   6  2  2  0  2  3  0  1  4  5   6   7   0   1   2   3
    7|   7  3  3  1  3  2  1  0  6  7   4   5   2   3   0   1
    8|   8  0  0  4  0  2  4  6  0  1   2   3   4   5   6   7
    9|   9  1  1  5  1  3  5  7  1  0   3   2   5   4   7   6
   10|  10  2  2  6  2  0  6  4  2  3   0   1   6   7   4   5
   11|  11  3  3  7  3  1  7  5  3  2   1   0   7   6   5   4
   12|  12  4  4  0  4  6  0  2  4  5   6   7   0   1   2   3
   13|  13  5  5  1  5  7  1  3  5  4   7   6   1   0   3   2
   14|  14  6  6  2  6  4  2  0  6  7   4   5   2   3   0   1
   15|  15  7  7  3  7  5  3  1  7  6   5   4   3   2   1   0

Rémy Sigrist, Table of n, a(n) for n = 0..10010
Rémy Sigrist, Colored representation of the table for n, k < 2^10

Cf. A003987, A053645, A070939.

Cf. A344834 (AND), A344835 (OR), A344837 (min), A344838 (max), A344839 (absolute difference).

T(n, k, op=bitxor, w=m->#binary(m)) = { op(n*2^max(0, w(k)-w(n)), k*2^max(0, w(n)-w(k))) }

T(n, k) = T(k, n).
T(n, n) = 0.
T(n, 0) = n.
T(n, 1) = A053645(n) for any n > 0.

A344839 Square array T(n, k), n, k >= 0, read by antidiagonals; T(n, k) = abs(n * 2^max(0, w(k)-w(n)) - k * 2^max(0, w(n)-w(k))) (where w = A070939).

Original entry on oeis.org

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

Offset: 0

Rémy Sigrist, May 29 2021

In other words, we right pad the binary expansion of the lesser of n and k with zeros (provided it is positive) so that both numbers have the same number of binary digits, and then take the absolute difference.

			Array T(n, k) begins:
  n\k|   0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15
  ---+-------------------------------------------------------
    0|   0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15
    1|   1  0  0  1  0  1  2  3  0  1   2   3   4   5   6   7
    2|   2  0  0  1  0  1  2  3  0  1   2   3   4   5   6   7
    3|   3  1  1  0  2  1  0  1  4  3   2   1   0   1   2   3
    4|   4  0  0  2  0  1  2  3  0  1   2   3   4   5   6   7
    5|   5  1  1  1  1  0  1  2  2  1   0   1   2   3   4   5
    6|   6  2  2  0  2  1  0  1  4  3   2   1   0   1   2   3
    7|   7  3  3  1  3  2  1  0  6  5   4   3   2   1   0   1
    8|   8  0  0  4  0  2  4  6  0  1   2   3   4   5   6   7
    9|   9  1  1  3  1  1  3  5  1  0   1   2   3   4   5   6
   10|  10  2  2  2  2  0  2  4  2  1   0   1   2   3   4   5
   11|  11  3  3  1  3  1  1  3  3  2   1   0   1   2   3   4
   12|  12  4  4  0  4  2  0  2  4  3   2   1   0   1   2   3
   13|  13  5  5  1  5  3  1  1  5  4   3   2   1   0   1   2
   14|  14  6  6  2  6  4  2  0  6  5   4   3   2   1   0   1
   15|  15  7  7  3  7  5  3  1  7  6   5   4   3   2   1   0

Rémy Sigrist, Table of n, a(n) for n = 0..10010
Rémy Sigrist, Colored representation of the table for n, k < 2^10

Cf. A049581, A053645, A070939.

Cf. A344834 (AND), A344835 (OR), A344836 (XOR), A344837 (min), A344838 (max).

T(n,k,op=(x,y)->abs(x-y),w=m->#binary(m)) = { op(n*2^max(0, w(k)-w(n)), k*2^max(0, w(n)-w(k))) }

T(n, k) = T(k, n).
T(n, n) = 0.
T(n, 0) = n.
T(n, 1) = A053645(n) for any n > 0.

cp's OEIS Frontend

A073121 a(n) = r*a(ceiling(n/2)) + s*a(floor(n/2)) with a(1)=1 and (r,s)=(2,2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A164349 The limit of the string "0, 1" under the operation 'repeat string twice and remove last symbol'.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

Perl

Extensions

A284001 a(n) = A005361(A283477(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Scheme

Formula

A101402 a(0)=0, a(1)=1; for n>=2, let k = smallest power of 2 that is >= n, then a(n) = a(k/2) + a(n-1-k/2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

Extensions

A007549 Number of increasing rooted connected graphs where every block is a complete graph.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A091932 Primes that remain prime when their leading digit in binary representation is replaced by 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A073121 a(n) = ra(ceiling(n/2)) + sa(floor(n/2)) with a(1)=1 and (r,s)=(2,2).