A088698 -id:A088698 - cp's OEIS frontend

A048678 Binary expansion of nonnegative integers expanded to "Zeckendorffian format" with rewrite rules 0->0, 1->01.

0, 1, 2, 5, 4, 9, 10, 21, 8, 17, 18, 37, 20, 41, 42, 85, 16, 33, 34, 69, 36, 73, 74, 149, 40, 81, 82, 165, 84, 169, 170, 341, 32, 65, 66, 133, 68, 137, 138, 277, 72, 145, 146, 293, 148, 297, 298, 597, 80, 161, 162, 325, 164, 329, 330, 661, 168, 337, 338, 677, 340

Offset: 0

Antti Karttunen

No two adjacent 1-bits. Permutation of A003714.

Replace 1 with 01 in binary. - Ralf Stephan, Oct 07 2003

			11=1011 in binary, thus is rewritten as 100101 = 37 in decimal.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
N. J. A. Sloane, Transforms

Cf. A003714, A005203, A048679, A048680.
MASKTRANS transform of A053644.
Cf. A084471, A088697, A088698.
Cf. A124108.

a048678 0 = 0
a048678 x = 2 * (b + 1) * a048678 x' + b
            where (x', b) = divMod x 2
-- Reinhard Zumkeller, Mar 31 2015

rewrite_0to0_1to01 := proc(n) option remember; if(n < 2) then RETURN(n); else RETURN(((2^(1+(n mod 2))) * rewrite_0to0_1to01(floor(n/2))) + (n mod 2)); fi; end;

f[n_] := FromDigits[ Flatten[IntegerDigits[n, 2] /. {1 -> {0, 1}}], 2]; Table[f@n, {n, 0, 60}] (* Robert G. Wilson v, Dec 11 2009 *)

a(n)=if(n<1,0,(3-(-1)^n)*a(floor(n/2))+(1-(-1)^n)/2)

a(n) = if(n == 0, 0, my(A = -2); sum(i = 0, logint(n, 2), A++; if(bittest(n, i), 1 << (A++)))) \\ Mikhail Kurkov, Mar 14 2024

def a(n):
    return 0 if n==0 else (3 - (-1)**n)*a(n//2) + (1 - (-1)**n)//2
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 30 2017

def A048678(n): return int(bin(n)[2:].replace('1','01'),2) # Chai Wah Wu, Mar 18 2024

a(n) = rewrite_0to0_1to01(n) [ Each 0->1, 1->10 in binary expansion of n ].
a(0)=0; a(n) = (3-(-1)^n)*a(floor(n/2))+(1-(-1)^n)/2. - Benoit Cloitre, Aug 31 2003
a(0)=0, a(2n) = 2a(n), a(2n+1) = 4a(n) + 1. - Ralf Stephan, Oct 07 2003

A341520 Square array A(n,k) = A156552(A005940(1+n)*A005940(1+k)), read by antidiagonals.

Original entry on oeis.org

0, 1, 1, 2, 3, 2, 3, 5, 5, 3, 4, 7, 6, 7, 4, 5, 9, 11, 11, 9, 5, 6, 11, 10, 15, 10, 11, 6, 7, 13, 13, 19, 19, 13, 13, 7, 8, 15, 14, 23, 12, 23, 14, 15, 8, 9, 17, 23, 27, 21, 21, 27, 23, 17, 9, 10, 19, 18, 31, 22, 27, 22, 31, 18, 19, 10, 11, 21, 21, 35, 39, 29, 29, 39, 35, 21, 21, 11, 12, 23, 22, 39, 20, 47, 30, 47, 20, 39, 22, 23, 12

Offset: 0

Antti Karttunen, Feb 13 2021

The indices run as A(0,0), A(0,1), A(1,0), A(0,2), A(1,1), A(2,0), etc. The array is symmetric.
This array defines a binary operation on the nonnegative integers that matches up the zeros in the binary representation of each operand (starting from the right, and including as many leading zeros as necessary) and concatenates the two (possibly null) strings of ones to the right of each matched pair of zeros. See the examples. - Peter Munn, Feb 14 2021.
As such it could be useful for implementing multiplication, say, in Turing machines, with a "tape-like" unary-binary encoding of the prime factorization of n (A156552). However, such representation is not very useful if addition or subtraction is also needed.

			The top left {0..15} X {0..16} corner of the array:
   0,  1,  2,  3,  4,  5,   6,   7,   8,   9,  10,  11,  12,  13,  14,  15,
   1,  3,  5,  7,  9, 11,  13,  15,  17,  19,  21,  23,  25,  27,  29,  31,
   2,  5,  6, 11, 10, 13,  14,  23,  18,  21,  22,  27,  26,  29,  30,  47,
   3,  7, 11, 15, 19, 23,  27,  31,  35,  39,  43,  47,  51,  55,  59,  63,
   4,  9, 10, 19, 12, 21,  22,  39,  20,  25,  26,  43,  28,  45,  46,  79,
   5, 11, 13, 23, 21, 27,  29,  47,  37,  43,  45,  55,  53,  59,  61,  95,
   6, 13, 14, 27, 22, 29,  30,  55,  38,  45,  46,  59,  54,  61,  62, 111,
   7, 15, 23, 31, 39, 47,  55,  63,  71,  79,  87,  95, 103, 111, 119, 127,
   8, 17, 18, 35, 20, 37,  38,  71,  24,  41,  42,  75,  44,  77,  78, 143,
   9, 19, 21, 39, 25, 43,  45,  79,  41,  51,  53,  87,  57,  91,  93, 159,
  10, 21, 22, 43, 26, 45,  46,  87,  42,  53,  54,  91,  58,  93,  94, 175,
  11, 23, 27, 47, 43, 55,  59,  95,  75,  87,  91, 111, 107, 119, 123, 191,
  12, 25, 26, 51, 28, 53,  54, 103,  44,  57,  58, 107,  60, 109, 110, 207,
  13, 27, 29, 55, 45, 59,  61, 111,  77,  91,  93, 119, 109, 123, 125, 223,
  14, 29, 30, 59, 46, 61,  62, 119,  78,  93,  94, 123, 110, 125, 126, 239,
  15, 31, 47, 63, 79, 95, 111, 127, 143, 159, 175, 191, 207, 223, 239, 255,
  16, 33, 34, 67, 36, 69,  70, 135,  40,  73,  74, 139,  76, 141, 142, 271,
...
From _Peter Munn_, Feb 24 2021: (Start)
We consider the case of n = 10, k = 41, following the procedure in the Feb 14 2021 comment.
First, write 10 and 41 in binary:
  10 = 1010_2
  41 = 101001_2
Add at least one leading zero to each number, equalizing number of zeros:
  0  0  1  0  1  0
  0  1  0  1  0  0  1
Align zeros, but separate ones:
  0     0  1     0  1  0
  |     |        |     |
  0  1  0     1  0     0  1
---------------------------
  0  1  0  1  1  0  1  0  1
Concatenating the ones, as shown above, we get 10110101_2 = 181.
So A(10, 41) = 181.
(End)

Cf. A005940, A156552.
Cf. A088698 (main diagonal).
Rows/columns 0-3: A001477, A005408, A341522, A004767. Row/column 7: A004771.
Cf. A341521 (the lower triangular section).
Cf. also A003991, A268725, A297164, A331590, A341509, A341510, A351960, A351961, A351962

Block[{nn = 12, a = {1}}, Do[AppendTo[a, If[EvenQ[i], Times @@ Map[Prime[PrimePi[#1] + 1]^#2 & @@ # &, FactorInteger[#]] &@ a[[(i/2) + 1]], 2 a[[((i - 1)/2) + 1]]]], {i, nn}]; Table[Floor@ Total@ Flatten@ MapIndexed[#1 2^(#2 - 1) &, Flatten[Table[2^(PrimePi@ #1 - 1), {#2}] & @@@ FactorInteger@ #]] &[a[[1 + n - k]]*a[[1 + k]] ], {n, 0, nn}, {k, n, 0, -1}]] // Flatten (* Michael De Vlieger, Feb 24 2021 *)

up_to = 105;
A005940(n) = { my(p=2, t=1); n--; until(!n\=2, if((n%2), (t*=p), p=nextprime(p+1))); (t); };
A156552(n) = { my(f = factor(n), p, p2 = 1, res = 0); for(i = 1, #f~, p = 1 << (primepi(f[i, 1]) - 1); res += (p * p2 * (2^(f[i, 2]) - 1)); p2 <<= f[i, 2]); res };
A341520sq(n,k) = A156552(A005940(1+n)*A005940(1+k));
A341520list(up_to) = { my(v = vector(1+up_to), i=0); for(a=0,oo, for(col=0,a, i++; if(i > #v, return(v)); v[i] = A341520sq(col,(a-(col))))); (v); };
v341520 = A341520list(up_to);
A341520(n) = v341520[1+n];

A(x, y) = A156552(A005940(1+x) * A005940(1+y)).
For all n>=0, A(0, n) = A(n, 0) = n.
For all x>=0, y>=0, A(x, y) = A(y, x).
For all x, y, z >= 0, A(x, A(y, z)) = A(A(x, y), z).
From Antti Karttunen, Feb 27 2022: (Start)
For all x, y >= 0, A(x, y) = A(A351961(x,y), A351962(x,y)).
For x >= 0, y > 0, A(x, y) = A351960(x, A(x, A297164(y))).
(End)

A084471 Change 0 to 00 in binary representation of n.

Original entry on oeis.org

1, 4, 3, 16, 9, 12, 7, 64, 33, 36, 19, 48, 25, 28, 15, 256, 129, 132, 67, 144, 73, 76, 39, 192, 97, 100, 51, 112, 57, 60, 31, 1024, 513, 516, 259, 528, 265, 268, 135, 576, 289, 292, 147, 304, 153, 156, 79, 768, 385, 388, 195, 400, 201, 204, 103, 448, 225

Offset: 1

Reinhard Zumkeller, May 27 2003

a(n) = n iff n = 2^k - 1, k>0.

A023416(a(n))=A023416(n)*2; A000120(a(n))=A000120(n);

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A084472(n)=A007088(a(n)), A084473, A038573.
Ordered terms are in A060142.
Column k=2 of A340666.
Cf. A088698, A175047. - Robert G. Wilson v, Dec 10 2009

a084471 1 = 1
a084471 x = 2 * (2 - d) * a084471 x' + d  where (x',d) = divMod x 2
-- Reinhard Zumkeller, Jul 16 2012

a:= n-> Bits[Join](subs(0=[0$2][], Bits[Split](n))):
seq(a(n), n=1..60);  # Alois P. Heinz, Jan 15 2021

f[n_] := FromDigits[Flatten[IntegerDigits[n, 2] /. {0 -> {0, 0}}], 2]; Array[f, 60] (* Robert G. Wilson v, Dec 10 2009 *)

a(1)=1, a(2*k+1)=2*a(k)+1, a(2*k)=4*a(k).

A088697 Replace 0 with 10 in binary representation of n.

Original entry on oeis.org

0, 1, 6, 3, 26, 13, 14, 7, 106, 53, 54, 27, 58, 29, 30, 15, 426, 213, 214, 107, 218, 109, 110, 55, 234, 117, 118, 59, 122, 61, 62, 31, 1706, 853, 854, 427, 858, 429, 430, 215, 874, 437, 438, 219, 442, 221, 222, 111, 938, 469, 470, 235, 474, 237

Offset: 0

Ralf Stephan, Oct 07 2003

			n=9: 1001 -> 110101 = 53, so a(9) = 53.

Rémy Sigrist, Table of n, a(n) for n = 0..8192

Cf. A084471, A048678, A088698.

Join[{0},Table[FromDigits[Flatten[IntegerDigits[n,2]/.(0->{1,0})],2],{n,80}]] (* Harvey P. Dale, Dec 05 2023 *)

a(n)=if(n<1,0,if(n%2==0,4*a(n/2)+2,2*a((n-1)/2)+1))

a(0)=0, a(2n) = 4a(n) + 2, a(2n+1) = 2a(n) + 1.

A341521 Triangular array T(n,k) = A156552(A005940(1+n)*A005940(1+k)), read by rows, with n >= 0, 0 <= k <= n.

Original entry on oeis.org

0, 1, 3, 2, 5, 6, 3, 7, 11, 15, 4, 9, 10, 19, 12, 5, 11, 13, 23, 21, 27, 6, 13, 14, 27, 22, 29, 30, 7, 15, 23, 31, 39, 47, 55, 63, 8, 17, 18, 35, 20, 37, 38, 71, 24, 9, 19, 21, 39, 25, 43, 45, 79, 41, 51, 10, 21, 22, 43, 26, 45, 46, 87, 42, 53, 54, 11, 23, 27, 47, 43, 55, 59, 95, 75, 87, 91, 111, 12, 25, 26, 51, 28, 53, 54, 103, 44, 57, 58, 107, 60

Offset: 0

Antti Karttunen, Feb 15 2021

A341520 is the main entry for this dyadic function. See comments there.

			The triangle begins as:
  0,
  1,  3,
  2,  5,  6,
  3,  7, 11, 15,
  4,  9, 10, 19, 12,
  5, 11, 13, 23, 21, 27,
  6, 13, 14, 27, 22, 29, 30,
  7, 15, 23, 31, 39, 47, 55, 63,
  8, 17, 18, 35, 20, 37, 38, 71, 24,
  9, 19, 21, 39, 25, 43, 45, 79, 41, 51,
etc.

The lower triangular region of A341520 read by rows.
Cf. A005940, A156552.
Cf. A001477 (the left edge), A088698 (the right edge).

up_to = 104;
A005940(n) = { my(p=2, t=1); n--; until(!n\=2, if((n%2), (t*=p), p=nextprime(p+1))); (t); };
A156552(n) = { my(f = factor(n), p2 = 1, res = 0); for(i = 1, #f~, p = 1 << (primepi(f[i, 1]) - 1); res += (p * p2 * (2^(f[i, 2]) - 1)); p2 <<= f[i, 2]); res };
A341520sq(n,k) = A156552(A005940(1+n)*A005940(1+k));
A341521list(up_to) = { my(v = vector(1+up_to), i=0); for(n=0,oo, for(k=0,n, i++; if(i > #v, return(v)); v[i] = A341520sq(n,k))); (v); };
v341521 = A341521list(up_to);
A341521(n) = v341521[1+n]; \\ Antti Karttunen, Feb 15 2021

T(n,k) = A341520(n,k).

A346705 The a(n)-th composition in standard order is the even bisection of the n-th composition in standard order.

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Aug 19 2021

nonn

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again.

a(n) is the row number in A066099 of the even bisection (even-indexed terms) of the n-th row of A066099.

			Composition number 741 in standard order is (2,1,1,3,2,1), with even bisection (1,3,1), which is composition number 25 in standard order, so a(741) = 25.

Length of the a(n)-th standard composition is A000120(n)/2 rounded down.
Positions of first appearances appear to be A088698, sorted: A277335.
The version for reversed prime indices appears to be A329888, sums A346700.
Sum of the a(n)-th standard composition is A346633.
An unordered reverse version for odd bisection is A346701, sums A346699.
The version for odd bisection is A346702, sums A209281(n+1).
An unordered version for odd bisection is A346703, sums A346697.
An unordered version is A346704, sums A346698.
A011782 counts compositions.
A029837 gives length of binary expansion, or sometimes A070939.
A066099 lists compositions in standard order.
A097805 counts compositions by alternating sum.
Cf. A000302, A025047, A088218, A124754, A124767, A228351, A290258, A290259, A344618, A345197.

Table[Total[2^Accumulate[Reverse[Last/@Partition[ Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse,2]]]]/2,{n,0,100}]

A029837(a(n)) = A346633(n).

cp's OEIS Frontend

A048678 Binary expansion of nonnegative integers expanded to "Zeckendorffian format" with rewrite rules 0->0, 1->01.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Python

Formula

A341520 Square array A(n,k) = A156552(A005940(1+n)*A005940(1+k)), read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A084471 Change 0 to 00 in binary representation of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

A088697 Replace 0 with 10 in binary representation of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A341521 Triangular array T(n,k) = A156552(A005940(1+n)*A005940(1+k)), read by rows, with n >= 0, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A346705 The a(n)-th composition in standard order is the even bisection of the n-th composition in standard order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula