A115637 -id:A115637 - cp's OEIS frontend

A374625 In the binary expansion of n, expand bits 1 -> 01 and 0 -> 10.

2, 1, 6, 5, 26, 25, 22, 21, 106, 105, 102, 101, 90, 89, 86, 85, 426, 425, 422, 421, 410, 409, 406, 405, 362, 361, 358, 357, 346, 345, 342, 341, 1706, 1705, 1702, 1701, 1690, 1689, 1686, 1685, 1642, 1641, 1638, 1637, 1626, 1625, 1622, 1621, 1450, 1449, 1446

Offset: 0

Darío Clavijo, Jul 14 2024

This is essentialy the Manchester encoding (defined by convention in IEEE802.3 opposed to the original version where the mappings are inverted published by G. E. Thomas in 1949 see ref) which transforms each bit by representing 1 as 01 and 0 as 10, ensuring a transition occurs in the middle of each bit period for synchronization.

			a(5) = 25 because:
  5 is 101 and:
   1 |  0 |  1
  01 | 10 | 01
  And: 11001 is 25.

Andrew S. Tanenbaum, Computer Networks (4th ed.), Prentice Hall, 2002, Pages 274-275, ISBN 0-13-066102-3.

Paolo Xausa, Table of n, a(n) for n = 0..10000
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003, equation 2.4 with a(n) = a_n for case alpha=4, c=2, d=1 and n >= 1.
Wikipedia, Manchester code.

Cf. A030101, A115637, A179888.

a:= n-> 2-(n mod 2)+`if`(n<2, 0, 4*a(iquo(n, 2))):
seq(a(n), n=0..50);  # Alois P. Heinz, Jul 15 2024

A374625[n_] := FromDigits[2 - IntegerDigits[n, 2], 4];
Array[A374625, 100, 0] (* Paolo Xausa, Jul 16 2024 *)

def a(n):
  s=''
  for b in bin(n)[2:]:
    s += '01'*(b=='1') + '10'*(b=='0')
  return int(s,2)
print([a(n) for n in range(0,51)])

def a(n):
  d = {'0': '10', '1': '01'}
  return int(''.join(map(d.get, bin(n)[2:])), 2)
print([a(n) for n in range(0,51)]) # Jason Yuen, Jul 15 2024

a = lambda n: int(''.join("101"[b=='1':(b=='1')+2] for b in bin(n)[2:]), 2)
# Peter Luschny, Jul 15 2024

def A374625(n): return ((1<<(n.bit_length()<<1)+1)-2)//3-int(bin(n)[2:],4) if n else 2 # Chai Wah Wu, Jul 16 2024

a(n) = a(n+1) + 1 for n even.
a(n) = A030101(A179888(A030101(n))) for n odd.
a(2*n) = 4*a(n) + 2 for n>=1.
a(2*n+1) = 4*a(n) + 1 for n>=1.

A115636 A divide-and-conquer number triangle.

Original entry on oeis.org

1, 1, -1, 4, 0, 1, 4, 0, 1, -1, 4, -4, 0, 0, 1, 4, -4, 0, 0, 1, -1, 16, 0, 4, 0, 0, 0, 1, 16, 0, 4, 0, 0, 0, 1, -1, 16, 0, 4, -4, 0, 0, 0, 0, 1, 16, 0, 4, -4, 0, 0, 0, 0, 1, -1, 16, -16, 0, 0, 4, 0, 0, 0, 0, 0, 1, 16, -16, 0, 0, 4, 0, 0, 0, 0, 0, 1, -1, 16, -16, 0, 0, 4, -4, 0, 0, 0, 0, 0, 0, 1, 16, -16, 0, 0, 4, -4, 0, 0, 0, 0, 0, 0, 1, -1

Offset: 0

Paul Barry, Jan 27 2006

			Triangle begins
   1;
   1,  -1;
   4,   0,  1;
   4,   0,  1, -1;
   4,  -4,  0,  0,  1;
   4,  -4,  0,  0,  1, -1;
  16,   0,  4,  0,  0,  0,  1;
  16,   0,  4,  0,  0,  0,  1, -1;
  16,   0,  4, -4,  0,  0,  0,  0,  1;
  16,   0,  4, -4,  0,  0,  0,  0,  1, -1;
  16, -16,  0,  0,  4,  0,  0,  0,  0,  0,  1;
  16, -16,  0,  0,  4,  0,  0,  0,  0,  0,  1, -1;
  16, -16,  0,  0,  4, -4,  0,  0,  0,  0,  0,  0,  1;
  16, -16,  0,  0,  4, -4,  0,  0,  0,  0,  0,  0,  1, -1;
  64,   0, 16,  0,  0,  0,  4,  0,  0,  0,  0,  0,  0,  0,  1;
  64,   0, 16,  0,  0,  0,  4,  0,  0,  0,  0,  0,  0,  0,  1, -1;
  64,   0, 16,  0,  0,  0,  4, -4,  0,  0,  0,  0,  0,  0,  0,  0,  1;

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Cf. A115633 (inverse), A115637 (row sums), A115639 (first column).

A115633[n_, k_]:= If[k==n, (-1)^n, If[k==n-1, Mod[n,2], If[n==2*k+2, -4, 0]]];
T[n_, k_]:= T[n, k]= (-1)^k*If[k==n, 1, -Sum[T[n, j]*A115633[j, k], {j,k+1,n}] ];
Table[T[n, k], {n,0,18}, {k,0,n}]//Flatten (* G. C. Greubel, Nov 24 2021 *)

@CachedFunction
def A115633(n, k):
    if (k==n): return (-1)^n
    elif (k==n-1): return n%2
    elif (n==2*k+2): return -4
    else: return 0
def A115636(n,k):
    if (k==0): return 4^(floor(log(n+2, 2)) -1)
    elif (k==n): return (-1)^n
    elif (k==n-1): return (n%2)
    else: return (-1)^(k+1)*sum( A115636(n, j)*A115633(j, k) for j in (k+1..n) )
flatten([[A115636(n, k) for k in (0..n)] for n in (0..15)]) # G. C. Greubel, Nov 24 2021

T(n, 0) = A115639(n).
Sum_{k=0..n} T(n, k) = A115637(n).
T(n, k) = (-1)^k*( 1 if k = n otherwise (-1)*Sum_{j=k+1..n} T(n, j)*A115633(j, k) ). - G. C. Greubel, Nov 24 2021

A115638 A Jacobsthal-related divide-and-conquer sequence.

Original entry on oeis.org

1, -1, 5, -1, -3, -1, 21, -1, -3, -1, -11, -1, -3, -1, 85, -1, -3, -1, -11, -1, -3, -1, -43, -1, -3, -1, -11, -1, -3, -1, 341, -1, -3, -1, -11, -1, -3, -1, -43, -1, -3, -1, -11, -1, -3, -1, -171, -1, -3, -1, -11, -1, -3, -1, -43, -1, -3, -1, -11, -1, -3, -1, 1365, -1, -3, -1, -11, -1, -3, -1, -43

Offset: 0

Paul Barry, Jan 27 2006

Partial sums are A115637.

Antti Karttunen, Table of n, a(n) for n = 0..1024
R. Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.

Cf. A001045, A115637.

A115637[n_] := FromDigits[1 - IntegerDigits[n + 2, 2], 4];
Differences[Array[A115637, 100, -1]] (* Paolo Xausa, Jul 17 2024 *)

A115638(n) = if(!n,1, A115637(n)-A115637(n-1)); \\ (Needs also code from A115637) - Antti Karttunen, Nov 02 2018

def A115638(n): return int(bin((~(n+2))^(-1<<(n+2).bit_length()))[2:],4)-int(bin((~(n+1))^(-1<<(n+1).bit_length()))[2:],4) # Chai Wah Wu, Jul 17 2024

G.f.: Sum_{k>=0} 4^k*x^(2^(k+1)-2)/(1+x^(2^k)); the g.f. G(x) satisfies G(x) - 4*x^2*G(x^2) = 1/(1+x).

a(0) = 1; for n >= 1, a(n) = A115637(n) - A115637(n-1). - Antti Karttunen, Nov 02 2018

cp's OEIS Frontend

A374625 In the binary expansion of n, expand bits 1 -> 01 and 0 -> 10.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

Python

Python

Python

Formula

A115636 A divide-and-conquer number triangle.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Sage

Formula

A115638 A Jacobsthal-related divide-and-conquer sequence.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula