A006165 -id:A006165 - cp's OEIS frontend

A356989 a(n) = n - a^[3](n - a^[4](n-1)) with a(1) = 1, where a^[3](n) = a(a(a(n))) and a^[4](n) = a(a(a(a(n)))).

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

Offset: 1

Peter Bala, Sep 08 2022

This is the third sequence in a family of nested-recurrent sequences with apparently similar structure defined as follows. Given a sequence s = {s(n): n >= 1} we define the k-th iterated sequence s^[k] by putting s^[1](n) = s(n) and setting s^[k](n) = s^[k-1](s(n)) for k >= 2. For k >= 1, we define a nested-recurrent sequence {u(n): n >= 1}, dependent on k, by putting u(1) = 1 and setting u(n) = n - u^[k](n - u^[k+1](n-1)) for n >= 2. The present sequence is the case k = 3. For other cases see A006165 (k = 1), A356988 (k = 2) and A356990 (k = 4).
The sequence is slow, that is, for n >= 1, a(n+1) - a(n) is either 0 or 1. The line graph of the sequence {a(n)} thus consists of a series of plateaus (where the value of the ordinate a(n) remains constant as n increases) joined by lines of slope 1.
The sequence of plateau heights begins 4, 6, 9, 13, 19, 28, 41, 60, ..., conjecturally A000930.
The plateaus start at absiccsa values n = 5, 8, 12, 17, 25, 37, 54, 79, ..., conjecturally A179070, and terminate at abscissa values n = 6, 9, 13, 19, 28, 41, 60, ..., conjecturally A000930.

Cf. A000930, A006165, A179070, A356988, A356990.

a := proc (n) option remember; if n = 1 then 1 else n - a(a(a(n - a(a(a(a(n-1))))))) end if; end proc:
seq(a(n), n = 1..100);

A279521 Maximum number of single-direction edges in leveled binary trees with n nodes.

Original entry on oeis.org

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

Offset: 1

Adrijan Božinovski, Dec 14 2016

nonn

A leveled binary tree is a binary tree where every level, except possibly the last, is completely filled.
Unlike a complete binary tree, where nodes in the last level are always stacked linearly from left to right, insertion in a leveled binary tree can be done in any order.
The formula for this integer sequence determines the maximum number of single-direction edges in a leveled binary tree of an arbitrary size n, and is presented alongside its proof. The same formula gives the maximum number of right, as well as the maximum number of left, edges in any leveled binary tree. The proof is analogous for both cases.
This sequence also gives the number of different nonordered neighboring pairs in the Stern-Brocot sequence A002487. - Horst H. Manninger, Jun 10 2021
Number of nodes in the left subheap of a binary heap of length n. - Alois P. Heinz, Jun 24 2024

			In a leveled binary tree with 1 node, there are at most 0 strictly right edges: n=1 => a(n)=0.
.   o
In a leveled binary tree with 2 nodes, there are at most 1 strictly right edges: n=2 => a(n)=1.
.   o
.    \ <=
.     o
In a leveled binary tree with 3 nodes, there are at most 1 strictly right edges: n=3 => a(n)=1.
.     o
.    / \ <=
.   o   o
In a leveled binary tree with 4 nodes, there are at most 2 strictly right edges: n=4 => a(n)=2.
.     o
.    / \ <=
.   o   o
.    \ <=
.     o
In a leveled binary tree with 5 nodes, there are at most 3 strictly right edges: n=5 => a(n)=3.
.     o___
.    /    \ <=
.   o      o
.    \ <=   \ <=
.     o      o
In a leveled binary tree with 6 nodes, there are at most 3 strictly right edges: n=6 => a(n)=3.
.       ___o___
.      /       \ <=
.     o         o
.    / \ <=      \ <=
.   o   o         o
In a leveled binary tree with 7 nodes, there are at most 3 strictly right edges: n=7 => a(n)=3.
.       ___o___
.      /       \ <=
.     o         o
.    / \ <=    / \ <=
.   o   o     o   o
In a leveled binary tree with 8 nodes, there are at most 4 strictly right edges: n=8 => a(n)=4.
.         ___o___
.        /       \ <=
.     __o         o
.    /   \ <=    / \ <=
.   o     o     o   o
.    \ <=
.     o
In a leveled binary tree with 9 nodes, there are at most 5 strictly right edges: n=9 => a(n)=5.
.         ___o___
.        /       \ <=
.     __o         o
.    /   \ <=    / \ <=
.   o     o     o   o
.    \ <=  \ <=
.     o     o
And so on.

Adrijan Božinovski, Table of n, a(n) for n = 1..10000
Stevo Bozinovski and Adrijan Bozinovski, Brain Rhythms, Pascal Triangle, and Brain-Computer Interface, ICEST (Ohrid, North Macedonia 2019), 191-193.
NIST, Height-balanced tree
NIST, Complete binary tree
NIST, Full binary tree

Cf. A002487, A006165, A056971, A277267, A002487.

Essentially partial sums of A086694.

static int a(int n)
{
    int h = (int) Math.floor(Math.log(n) / Math.log(2));
    int p2h = (int) Math.pow(2, h);
    int p2h_1 = (int) Math.pow(2, h-1);
    int He = Heaviside(-n + 3*p2h_1 - 1);
    return (int) ((n + p2h_1 - 1)*He + Math.pow(-1, He)*(p2h - 1));
}
static int Heaviside(double x)
{
    return x >= 0 ? 1 : 0;
}

a:= n-> (g-> min(g-1, n-g/2))(2^ilog2(n)):
seq(a(n), n=1..100);  # Alois P. Heinz, Nov 16 2020

Table[Function[h, n + 2^(h - 1) - 1 * Boole[# >= 0] # &@ (-n + 3*2^(h-1) - 1) + (-1) ^ Boole[# >= 0] # &@ (-n + 3*2^(h-1) - 1) * (2^h - 1)]@ Floor[Log2@ n], {n, 71}] (* George Tanev, Jan 01 2017 *)
a[0] = 0; a[1] = 1; lis = {}; m = 70;t = Flatten[Table[{a[2*n] = a[n], a[2*n + 1] = a[n] + a[n + 1]}, {n, m}]];
For[g = 2, g < m, g++, AppendTo[lis, Length[Sort[DeleteDuplicates[Sort[#] & /@ (Partition[t[[1 ;; g]], 2, 1])]]]]]
lis (* Horst H. Manninger, Jun 10 2021 *)

class A279521():
    @staticmethod
    def _heaviside(x):
        return 1 if x >= 0 else 0
    @staticmethod
    def at(n):
        h = n.bit_length() -1
        p2h = 2**h
        p2h_1 = 2**(h-1)
        hs = A279521._heaviside(-n + 3 * p2h_1 - 1)
        return ((n + p2h_1 - 1) * hs + (-1)**hs * (p2h - 1))
print([A279521.at(n) for n in range(1,100)])
# George Tanev, Jan 01 2017, indentation R. J. Mathar, Mar 29 2023

def a(n: Int): Int = {
    val h = Math.floor(Math.log(n) / Math.log(2)).toInt
    val p2h = Math.pow(2, h).toInt
    val p2h_1 = Math.pow(2, h - 1).toInt
    val hs = heaviside(-n + 3 * p2h_1 - 1)
    ((n + p2h_1 - 1) * hs + Math.pow(-1, hs) * (p2h - 1)).toInt
}
/** George Tanev, Jan 01 2017 */
def heaviside(x: Double): Int = if (x >= 0) 1 else 0

a(n) = (n + 2^(h-1) - 1)*He + (-1)^He * (2^h - 1), where h = floor(log_2(n)) and is the height of the binary tree, He = H(-n + 3*2^(h-1) - 1) and H is the Heaviside step function (i.e., H(x) = 1 if x >= 0 and H(x) = 0 if x < 0).
Proof:
If n = 2^k - 1 (for any k > 0), i.e., if n = {3, 7, 15, ...}, the binary tree is full, and, as any tree, contains n-1 edges (1 fewer than the number of nodes). Any n = 2^k - 1 is an odd number, so the number one less than that is always even. In a full binary tree, every internal (i.e., non-leaf) node has both a left and a right child node, so there will be equally as many right as left edges in such a tree. Thus, half of that number will be the number of strictly right or strictly left edges. In this proof, strictly right edges will be viewed (the proof is analogous for strictly left edges).
If n != 2^k - 1, the leveled binary tree is not full. More precisely, the last level (level h) isn't full, but the subtree consisting of the root and all the levels of the tree up to (and including) level h-1 is. As in one of the examples, the leveled tree with n = 8 is not full and has a height of h = 3, but its subtree up to and including level h = 2 is full. 2^h - 1 nodes will form the full subtree, which will have 2^h - 2 edges, and half of those edges, i.e., 2^(h-1) - 1, will be strictly right.
The last level of the leveled binary tree can contain at most 2^h nodes. If it is filled with right child nodes first, the number of right edges will increase, up to a point when all of the right child nodes have been inserted and the next node to be inserted will have to be a left child node. As is evident in the given examples, it is possible to insert right child nodes in the last level of the leveled binary trees with n = 4 and n = 5, but in a leveled binary tree with n = 6 a left child node must be inserted in the last level (h = 2), since there is no more room to insert right child nodes. This forces a stop in the increase of the number of right edges. It can be observed that the moment when the number of right edges in a leveled binary tree must stop increasing is when a node is entered after half of the possible positions to insert nodes in the last level, i.e., 2^h / 2 = 2^(h-1), have been occupied. The number of nodes in the leveled binary tree must be smaller than the number of nodes already present in the previous levels of the tree plus half of the nodes in the last level, in order for the maximum number of right edges to increase; otherwise the maximum number of right edges will remain 2^(h-1) - 1. Therefore, the number of strictly right edges will keep increasing until n < 2^h - 1 + 2^(h-1), i.e., n < 3*2^(h-1) - 1, or, stated differently, -n + 3*2^(h-1) - 1 > 0. This condition can be expressed with the Heaviside step function as He = H(-n + 3*2^(h-1) - 1).
There are two cases to consider:
1) When half of the nodes of the last level of the binary tree have been entered (i.e., it holds that He = H(-n + 3*2^(h-1) - 1) = 0), the number of right edges reaches the maximum and it remains constant until the next level starts being filled. This maximum number is 2^h - 1, i.e., the number of strictly right edges of a leveled binary tree of level h+1.
2) While the condition He = H(-n + 3*2^(h-1) - 1) = 1 (i.e., is true), it is possible to insert right child nodes in the last level of the binary tree, thus there are less than half of the possible 2^h nodes in the last level inserted. Since the number of edges in a tree is always one less than the number of nodes, and since the number of nodes in the full binary tree of level h-1 (the level before the last in the leveled binary tree) is 2^(h-1) - 1, the number of edges in the leveled binary tree of level h will be n - 1 - (2^(h-1) - 1) = n - 2^(h-1), as long as He = 1. Since the leveled tree will be filled with right child nodes (and thus right edges) first, n - 2^(h-1) will be the number of strictly right edges in a leveled binary tree of level h while half of the possible right child nodes in the last level have not been completely filled.
Therefore, the formula will be 2^h - 1 for He = 0 and n - 2^(h-1) for He = 1. The case for He = 1 can be expressed as n - 2^(h-1) = n + 2^(h-1) - 2^h = n + 2^(h-1) - 1 - 2^h + 1 = n + 2^(h-1) - 1 - (2^h - 1), meaning that the case for He = 1 contains the case for He = 0. Both cases can be represented with a single expression as (n + 2^(h-1) - 1)*He + (-1)^He * (2^h - 1), which is the formula for a(n).
For k > 0 we have: a(2k) = 1 + a(k-1) + a(k); a(2k+1) = 1 + 2*a(k). - Orson R. L. Peters, Aug 09 2019
a(n) = n - 1 - A277267(n). - Alois P. Heinz, Nov 16 2020
a(n) = A006165(n+1) - 1. - Alois P. Heinz, Feb 03 2024

A066997 Survivor number for 2nd-order Josephus problem.

Original entry on oeis.org

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

Offset: 2

Eugene McDonnell (eemcd(AT)aol.com), Jan 27 2002

Boyko Bantchev defines the survivor number for the second-order Josephus problem with n persons as follows: a(n) is not the number of the actual survivor but that of the person to be eliminated; that is, every second person in a circle is marked until only one remains - and that one is eliminated; having eliminated a(n), start again from the beginning with the remaining n-1 people, eliminate the one whose ordinal number in the new sequence is a(n-1), then do the same with the n-2 remaining and so forth, until only one is left. This is the survivor number.

			To find a(19): First method: let m = floor(log_2(n)) = 4, let k = n - 2^m = 3, then 1 + k + 2^(m-1) = 12. Binary method: 19 in binary is 1 0 0 1 1; drop first bit leaving 0 0 1 1; "OR" first bit with remaining bits giving 0 1 1; append leading 1 giving 1 0 1 1; convert to integer giving 11; add 1 giving 12.

Boyko Bantchev (bantchev(AT)math.bas.bg), Personal communication, Nov 30 2001

Hsien-Kuei Hwang, S. Janson, 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, 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.
Index entries for sequences related to the Josephus Problem

This is the same as A006165 except that it lacks two leading 1's.

a(n) = my(m = logint(n, 2), k = n - 2^m); if (k < 2^(m-1), 1+k+2^(m-1), 2^m); \\ Michel Marcus, Mar 26 2020

a(n) = 1+k+2^(m-1) for k < 2^(m-1) and 2^m otherwise, where m = floor(log_2(n)) and k = n-2^m. Also: write n in binary; drop first bit; "OR" new first bit with each remaining bit; append 1 as new first bit; convert to integer; add 1.

A283187 a(0) = 0; a(1) = 1; a(2n) = 2a(n), a(2*n+1) = a(n) + (-1)^a(n+1).

Original entry on oeis.org

0, 1, 2, 2, 4, 3, 4, 3, 8, 3, 6, 4, 8, 3, 6, 4, 16, 7, 6, 4, 12, 7, 8, 5, 16, 7, 6, 4, 12, 7, 8, 5, 32, 15, 14, 8, 12, 7, 8, 5, 24, 11, 14, 8, 16, 7, 10, 6, 32, 15, 14, 8, 12, 7, 8, 5, 24, 11, 14, 8, 16, 7, 10, 6, 64, 31, 30, 16, 28, 15, 16, 9, 24, 11, 14, 8, 16, 7, 10, 6, 48, 23, 22, 12, 28, 15, 16, 9, 32, 15, 14

Offset: 0

Ilya Gutkovskiy, Mar 02 2017

			a(0) = 0;
a(1) = 1;
a(2) = a(2*1) = 2*a(1) = 2*1 = 2;
a(3) = a(2*1+1) = a(1) + (-1)^a(2) = 1 + (-1)^2 = 2;
a(4) = a(2*2) = 2*a(2) = 2*2 = 4;
a(5) = a(2*2+1) = a(2) + (-1)^a(3) = 2 + (-1)^2 = 3, etc.

Indranil Ghosh, Table of n, a(n) for n = 0..10000
Michael Gilleland, Some Self-Similar Integer Sequences
Ilya Gutkovskiy, Extended graphical example

Cf. A000079 (fixed points), A006165, A087808, A283165.

a[0] = 0; a[1] = 1; a[n_] := If[EvenQ[n], 2 a[n/2], a[(n - 1)/2] + (-1)^a[(n + 1)/2]]; Table[a[n], {n, 0, 90}]

a(n) = if (n<2, n, if (n%2==0, 2*a(n/2), a((n-1)/2)+(-1)^(a(n+1)/2)));
tabl(nn)={for (n=0, nn, print1(a(n), ", "); ); };
tabl(90); \\ Indranil Ghosh, Mar 03 2017

def a(n):
    if n==0 or n==1: return n
    if n%2==0: return int(2*a(n/2))
    else: return int(a((n-1)/2)+(-1)**a((n+1)/2)) # Indranil Ghosh, Mar 03 2017

from functools import lru_cache
@lru_cache(maxsize=None)
def A283187(n): return n if n <= 1 else A283187(n//2) + (-1 if A283187((n+1)//2) % 2 else 1) if n % 2 else 2*A283187(n//2) # Chai Wah Wu, Mar 08 2022

cp's OEIS Frontend

A078881 Size of the largest subset S of {1,2,3,...,n} with the property that if i and j are distinct elements of S then i XOR j is not in S, where XOR is the bitwise exclusive-OR operator.

Views

Author

Keywords

Comments

References

Crossrefs

Formula

Extensions

A086694 A run of 2^n 1's followed by a run of 2^n 0's, for n=0, 1, 2, ...

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A356989 a(n) = n - a^[3](n - a^[4](n-1)) with a(1) = 1, where a^[3](n) = a(a(a(n))) and a^[4](n) = a(a(a(a(n)))).

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

A279521 Maximum number of single-direction edges in leveled binary trees with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Java

Maple

Mathematica

Python

Scala

Formula

A066997 Survivor number for 2nd-order Josephus problem.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

A283187 a(0) = 0; a(1) = 1; a(2*n) = 2*a(n), a(2*n+1) = a(n) + (-1)^a(n+1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Python

A352227 Number of length-n blocks in the Thue-Morse sequence with intertwining pattern AB AB AB... .

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A283187 a(0) = 0; a(1) = 1; a(2n) = 2a(n), a(2*n+1) = a(n) + (-1)^a(n+1).