Mike Stay - cp's OEIS frontend

User: Mike Stay

Mike Stay has authored 4 sequences.

A194045 Numbers whose binary expansion is a preorder traversal of a binary tree.

0, 4, 20, 24, 84, 88, 100, 104, 112, 340, 344, 356, 360, 368, 404, 408, 420, 424, 432, 452, 456, 464, 480, 1364, 1368, 1380, 1384, 1392, 1428, 1432, 1444, 1448, 1456, 1476, 1480, 1488, 1504, 1620, 1624, 1636, 1640, 1648, 1684, 1688, 1700, 1704, 1712, 1732, 1736, 1744, 1760, 1812, 1816, 1828, 1832, 1840, 1860, 1864, 1872, 1888, 1924, 1928, 1936, 1952, 1984

Offset: 0

Mike Stay, Aug 13 2011

nonn

When traversing the tree in preorder, emit 1 at each node and 0 if it has no child on the current branch. The smallest binary tree is empty, so we emit 0 at the root; thus a(0) = 0. The next binary tree is a single node (emit 1) with no left (emit 0) or right child (emit 0); thus a(1) = 100 in binary or 4.

Cf. A000108.

// n is the number of internal nodes (or 1s in the binary expansion)
// f is a function to display each result
function trees(n, f) {
  // h is the "height", thinking of 1 as a step up and 0 as a step down
  // s is the current state
  function enumerate(n, h, s, f) {
    if (n===0 && h===0) { f(2 * s); }
    else {
      if (h > 0) { enumerate(n, h - 1, 2 * s, f) }
      if (n > 0) { enumerate(n - 1, h + 1, 2 * s + 1, f) }
    }
  }
  enumerate(n, 0, 0, f);
}

a(n) = 4 * A057520(n). [Joerg Arndt, Sep 22 2012]

a(0)=0, a(n) = 2 * A014486(n) for n>=1. [Joerg Arndt, Sep 22 2012]

A114567 a(n) is the number k such that the binary expansion of n mod 2^k is the postorder traversal of a binary tree, where 1 indicates a node and 0 indicates there are no children on that side.

Original entry on oeis.org

1, 3, 1, 5, 1, 5, 1, 7, 1, 3, 1, 7, 1, 7, 1, 9, 1, 3, 1, 7, 1, 7, 1, 9, 1, 3, 1, 9, 1, 9, 1, 11, 1, 3, 1, 5, 1, 5, 1, 9, 1, 3, 1, 9, 1, 9, 1, 11, 1, 3, 1, 9, 1, 9, 1, 11, 1, 3, 1, 11, 1, 11, 1, 13, 1, 3, 1, 5, 1, 5, 1, 9, 1, 3, 1, 9, 1, 9, 1, 11, 1, 3, 1, 9, 1, 9, 1, 11, 1, 3, 1, 11, 1, 11, 1, 13, 1, 3, 1, 5, 1

Offset: 0

Mike Stay, Feb 15 2006

Postorder traversals of a binary tree form an instantaneous code; any integer has a unique decomposition into codewords. To get the first codeword, find a(n). Then set n' = floor(n/2^(a(n))), find a(n'), and so on.

Equivalently, the number of bits of n, starting from the least significant, in which the number of 0's first exceeds the number of 1's (including 0's above the most significant bit of n if necessary). - Kevin Ryde, Sep 30 2024

			a(37) = 1 + a(floor(37/2)) + a(floor(37/2^(a(floor(37/2)) + 1)))
  = 1 + a(18) + a(floor(37/2^(a(18) + 1)))
  = 1 + 1 + a(floor(37/2^(1 + 1)))
  = 2 + a(9)
  = 2 + 1 + a(floor(9/2)) + a(floor(9/2^(a(floor(9/2)) + 1)))
  = 3 + a(4) + a(floor(9/2^(a(4) + 1)))
  = 3 + 1 + a(floor(9/4))
  = 4 + a(2)
  = 5.
37 mod 2^5 = 5 = 00101, which is the postorder traversal of the binary tree with a root node and a single left child.

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

Cf. A036991.

a := proc(n) option remember; if 0 = n mod 2 then 1; else 1 + a(floor(n/2)) + a(floor(n/2^(a(floor(n/2)) + 1))); end if; end proc; # Petros Hadjicostas, Nov 20 2019

a[n_] := a[n] = If[EvenQ[n], 1, 1 + a[Floor[n/2]] + a[ Floor[ n/2^( a[Floor[n/2]] + 1)]]]; a /@ Range[0, 100] (* Giovanni Resta, Nov 21 2019 *)

A114567(n) = if(!(n%2),1,1+A114567(n\2) + A114567(n>>(1+A114567(n\2)))); \\ Antti Karttunen, Mar 30 2021, after the Maple-program

a(n) = my(delta=1); for(i=0,oo, if(bittest(n,i), delta++, delta--||return(i+1))); \\ Kevin Ryde, Sep 30 2024

a(n) = 1, if n is even, and a(n) = 1 + a(floor(n/2)) + a(floor(n/2^{a(floor(n/2)) + 1})), if n is odd.

A114724 Each term is the sum of the next two digits starting with a(1)=2.

Original entry on oeis.org

2, 11, 6, 5, 14, 9, 5, 4, 13, 8, 5, 3, 2, 11, 6, 5, 14, 9, 5, 4, 13, 8, 5, 3, 2, 11, 6, 5, 14, 9, 5, 4, 13, 8, 5, 3, 2, 11, 6, 5, 14, 9, 5, 4, 13, 8, 5, 3, 2, 11, 6, 5, 14, 9, 5, 4, 13, 8, 5, 3, 2, 11, 6, 5, 14, 9, 5, 4, 13, 8, 5, 3, 2, 11, 6, 5, 14, 9, 5, 4, 13, 8, 5, 3, 2, 11, 6, 5

Offset: 1

N. J. A. Sloane, based on Dec 06 2005 posting from Mike Stay to the SeqFan list, Feb 27 2006

			E.g. 2=1+1, 11=6+5, ...

Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,0,0,0,0,0,0,1).

Cf. A113779.

&cat[[2, 11, 6, 5, 14, 9, 5, 4, 13, 8, 5, 3]^^10]; // Vincenzo Librandi, May 27 2019

PadRight[{},120,{2,11,6,5,14,9,5,4,13,8,5,3}] (* Harvey P. Dale, May 23 2019 *)

Cycles with period 12.

A108234 Minimum m such that n*2^m+k is prime, for k < 2^m. In other words, assuming you've read n out of a binary stream, a(n) is the minimum number of additional bits (appended to the least significant end of n) you must read before it is possible to obtain a prime.

Original entry on oeis.org

1, 0, 0, 2, 0, 1, 0, 1, 1, 2, 0, 3, 0, 1, 1, 2, 0, 1, 0, 1, 1, 2, 0, 2, 2, 1, 2, 2, 0, 1, 0, 2, 1, 2, 1, 1, 0, 3, 1, 2, 0, 3, 0, 1, 2, 3, 0, 1, 2, 1, 1, 2, 0, 1, 2, 1, 2, 2, 0, 2, 0, 2, 1, 2, 1, 4, 0, 1, 1, 2, 0, 3, 0, 1, 1, 2, 2, 1, 0, 3, 1, 2, 0, 2, 3, 1, 2, 2, 0, 1, 2, 3, 2, 2, 1, 1, 0, 1, 1, 2

Offset: 1

Mike Stay, Jun 16 2005

Somewhat related to the Riesel problem, A040081, the minimum m such that n*2^m-1 is prime.

			a(12) = 3 because 12 = 1100 in binary and 97 = 1100001 is the first prime that starts with 1100, needing 3 extra bits.

Antti Karttunen, Table of n, a(n) for n = 1..16384

Cf. A040081, A091991, A164022 (smallest prime).

% and Octave.
for n=1:100;m=0;k=0;while(~isprime(n*2^m+k))k=k+1;if k==2^m k=0;m=m+1;end;end;x(n)=m;end;x

A108234(n) = { my(m=0,k=0); while(!isprime((n*2^m)+k), k=k+1; if(2^m==k, k=0; m=m+1)); m; }; \\ Antti Karttunen, Dec 16 2017, after Octave/MATLAB code

Definition clarified by Antti Karttunen, Dec 16 2017

cp's OEIS Frontend

User: Mike Stay

A194045 Numbers whose binary expansion is a preorder traversal of a binary tree.

Views

Author

Keywords

Comments

Crossrefs

Programs

JavaScript

Formula

A114567 a(n) is the number k such that the binary expansion of n mod 2^k is the postorder traversal of a binary tree, where 1 indicates a node and 0 indicates there are no children on that side.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A114724 Each term is the sum of the next two digits starting with a(1)=2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A108234 Minimum m such that n*2^m+k is prime, for k < 2^m. In other words, assuming you've read n out of a binary stream, a(n) is the minimum number of additional bits (appended to the least significant end of n) you must read before it is possible to obtain a prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

MATLAB

PARI

Extensions