A000523 -id:A000523 - cp's OEIS frontend

A096111 If n = 2^k - 1, then a(n) = k+1, otherwise a(n) = (A000523(n)+1)*a(A053645(n)).

1, 2, 2, 3, 3, 6, 6, 4, 4, 8, 8, 12, 12, 24, 24, 5, 5, 10, 10, 15, 15, 30, 30, 20, 20, 40, 40, 60, 60, 120, 120, 6, 6, 12, 12, 18, 18, 36, 36, 24, 24, 48, 48, 72, 72, 144, 144, 30, 30, 60, 60, 90, 90, 180, 180, 120, 120, 240, 240, 360, 360, 720, 720, 7, 7, 14, 14, 21, 21

Offset: 0

Amarnath Murthy, Jun 29 2004

nonn

Each n > 1 occurs 2*A045778(n) times in the sequence.
f(n+2^k) = (k+1)*f(n) if 2^k > n+1. - Robert Israel, Apr 25 2016
If the binary indices of n (row n of A048793) are the positions 1's in its reversed binary expansion, then a(n) is the product of all binary indices of n + 1. The number of binary indices of n is A000120(n), their sum is A029931(n), and their average is A326699(n)/A326700(n). - Gus Wiseman, Jul 27 2019

Peter Kagey, Table of n, a(n) for n = 0..10000

Permutation of A096115, i.e. a(n) = A096115(A122198(n+1)) [Note the different starting offsets]. Bisection: A121663. Cf. A096113, A052330.
Cf. A029931.
Cf. A000120, A034797, A048793, A070939, A291166, A326031, A326672, A326673.

f:= proc(n) local L;
    L:= convert(2*n+2,base,2);
    convert(subs(0=NULL,zip(`*`,L, [$0..nops(L)-1])),`*`);
end proc:
map(f, [$0..100]); # Robert Israel, Apr 25 2016

CoefficientList[(Product[1 + k x^(2^(k - 1)), {k, 7}] - 1)/x, x] (* Michael De Vlieger, Apr 08 2016 *)
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];Table[Times@@bpe[n+1],{n,0,100}] (* Gus Wiseman, Jul 26 2019 *)

N=166; q='q+O('q^N);
gf= (prod(n=1,1+ceil(log(N)/log(2)), 1+n*q^(2^(n-1)) ) - 1) / q;
Vec(gf)
/* Joerg Arndt, Oct 06 2012 */

(define (A096111 n) (cond ((pow2? (+ n 1)) (+ 2 (A000523 n))) (else (* (+ 1 (A000523 n)) (A096111 (A053645 n))))))
(define (pow2? n) (and (> n 0) (zero? (A004198bi n (- n 1)))))

G.f.: ( prod(k>=1, 1+k*x^(2^(k-1)) )- 1 ) / x. - Vladeta Jovovic, Nov 08 2005

a(n) is the product of the exponents in the binary expansion of 2*n + 2. - Peter Kagey, Apr 24 2016

Edited, extended and Scheme code added by Antti Karttunen, Aug 25 2006

A061168 Partial sums of floor(log_2(k)) (= A000523(k)).

Original entry on oeis.org

0, 1, 2, 4, 6, 8, 10, 13, 16, 19, 22, 25, 28, 31, 34, 38, 42, 46, 50, 54, 58, 62, 66, 70, 74, 78, 82, 86, 90, 94, 98, 103, 108, 113, 118, 123, 128, 133, 138, 143, 148, 153, 158, 163, 168, 173, 178, 183, 188, 193, 198, 203, 208, 213, 218, 223, 228, 233, 238, 243, 248

Offset: 1

Antti Karttunen, Apr 19 2001

Given a term b>0 of the sequence and its left hand neighbor c, the corresponding unique sequence index n with property a(n)=b can be determined by n(b)=e+(b-d*(e+1)+2*(e-1))/d, where d=b-c and e=2^d. - Hieronymus Fischer, Dec 05 2006
a(n) gives index of start of binary expansion of n in the binary Champernowne sequence A076478. - N. J. A. Sloane, Dec 14 2017
a(n) is the number of pairs in ancestor relationship (= transitive closure of the parent relationship) in all (binary) heaps on n elements. - Alois P. Heinz, Feb 13 2019

D. E. Knuth, Fundamental Algorithms, Addison-Wesley, 1973, Section 1.2.4, ex. 42(b).

Alois P. Heinz, Table of n, a(n) for n = 1..10000 (first 1000 terms from Harry J. Smith)
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197, ex. 27.
Sung-Hyuk Cha, On Integer Sequences Derived from Balanced k-ary Trees, Applied Mathematics in Electrical and Computer Engineering, 2012.
Sung-Hyuk Cha, On Complete and Size Balanced k-ary Tree Integer Sequences, International Journal of Applied Mathematics and Informatics, Issue 2, Volume 6, 2012, pp. 67-75.
Alan M. Cleary, Joseph Winjum, Jordan Dood, Hiroki Shibata, and Shunsuke Inenaga, Bit Packed Encodings for Grammar-Compressed Strings Supporting Fast Random Access, Leibniz Int'l Proc. Informatics (LIPIcs) 23rd Int'l Symp. on Experim. Algor. (SEA 2025) Art. No. 12, 12:1-12:17. See p. 12:8.
Martin Griffiths, More sums involving the floor function, Math. Gaz., 86 (2002), 285-287.
Hsien-Kuei Hwang, S. Janson, and 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, and 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.
Tamás Lengyel, On the 2-Adic Valuation of Differences of Harmonic Numbers, Integers (2024) Vol. 24, A27. See p. 8.
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap

Cf. A000523, A001855, A123753, A076478.

import Data.List (transpose)
a061168 n = a061168_list !! n
a061168_list = zipWith (+) [0..] (zipWith (+) hs $ tail hs) where
   hs = concat $ transpose [a001855_list, a001855_list]
-- Reinhard Zumkeller, Jun 03 2013

seq(add(floor(log[2](k)),k=1..j),j=1..100);
# second Maple program:
a:= proc(n) option remember; `if`(n<1, 0, ilog2(n)+a(n-1)) end:
seq(a(n), n=1..80);   # Alois P. Heinz, Feb 12 2019

Accumulate[Floor[Log[2,Range[110]]]] (* Harvey P. Dale, Jul 16 2012 *)
a[n_] := (n+1) IntegerLength[n+1, 2] - 2^IntegerLength[n+1, 2] - n + 1;
Table[a[n], {n, 1, 61}] (* Peter Luschny, Dec 02 2017 *)

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

a(n)=local(k); if(n<1,0,k=length(binary(n))-1; (n+1)*k-2*(2^k-1))

{ for (n=1, 1000, k=length(binary(n))-1; write("b061168.txt", n, " ", (n + 1)*k - 2*(2^k - 1)) ) } \\ Harry J. Smith, Jul 18 2009

def A061168(n):
    s, i, z = -n , n, 1
    while 0 <= i: s += i; i -= z; z += z
    return s
print([A061168(n) for n in range(1, 62)]) # Peter Luschny, Nov 30 2017

def A061168(n): return (n+1)*((m:=n.bit_length())-1)-(1<Chai Wah Wu, Mar 29 2023

a(n) = A001855(n+1) - n.
a(n) = Sum_{k=1..n} floor(log_2(k)) = (n+1)*floor(log_2(n)) - 2*(2^floor(log_2(n)) - 1). - Diego Torres (torresvillarroel(AT)hotmail.com), Oct 29 2002
G.f.: 1/(1-x)^2 * Sum(k>=1, x^2^k). - Ralf Stephan, Apr 13 2002
a(n) = A123753(n) - 2*n - 1. - Peter Luschny, Nov 30 2017

A080301 Local ranking function for totally balanced binary sequences: if n's binary expansion is totally balanced (A080116(n)=1), then a(n) is its zero-based position among A000108((A000523(n)+1)/2) lexicographically ordered totally balanced binary sequences of the same width, otherwise -1.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Feb 21 2003

sign

Maple procedure CatalanRank is adapted from the algorithm 3.23 of the CAGES book.

			We have Cat(0)=1 totally balanced binary sequences of length 2*0: 0, thus a(0)=0, Cat(1)=1 of length 2*1: 10, thus a(2)=0, Cat(2)=2 of length 2*2: 1010 (= 10.) and 1100 (= 12.), thus a(10)=0 and a(12)=1, plus altogether Cat(3)=5 totally balanced binary sequences of length 2*3: 101010 (= 42), 101100 (= 44), 110010 (= 50), 110100 (= 52), 111000 (= 56), thus a(42)=0, a(44)=1, a(50)=2, a(52)=3 and a(56)=4. Et cetera.

D. L. Kreher and D. R. Stinson, Combinatorial Algorithms, Generation, Enumeration and Search, CRC Press, 1998.

Used to compute A080300. Cf. A009766, A000523.

A080301 := n -> `if`(0 = A080116(n),-1,CatalanRank((A000523(n)+1)/2,n));
CatalanRank := proc(n,aa) local y,r,lo,a; a := aa; r := 0; y := -1; lo := 0; while (a > 0) do if(0 = (a mod 2)) then r := r+1; lo := lo + A009766(r,y); else y := y+1; fi; a := floor(a/2); od; RETURN((binomial(2*n,n)/(n+1))-(lo+1)); end;

A116623 a(0)=1, a(2n) = a(n)+A000079(A000523(2n)), a(2n+1) = 3*a(n) + A000079(A000523(2n+1)+1).

Original entry on oeis.org

1, 5, 7, 19, 11, 29, 23, 65, 19, 49, 37, 103, 31, 85, 73, 211, 35, 89, 65, 179, 53, 143, 119, 341, 47, 125, 101, 287, 89, 251, 227, 665, 67, 169, 121, 331, 97, 259, 211, 601, 85, 223, 175, 493, 151, 421, 373, 1087, 79, 205, 157, 439, 133, 367, 319, 925, 121

Offset: 0

Antti Karttunen, Feb 20 2006. Proposed by Pierre Lamothe (plamothe(AT)aei.ca), May 21 2004

Viewed as a binary tree, this is (1); 5; 7,19; 11,29,23,65; ... Related to the parity vectors of Collatz and Terras trajectories.

Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. a(n) = A116640(A059893(n)). a(A000225(n)) = A001047(n+1). For n>= 1 a(A000079(n)) = A062709(n+1). A116641 gives the terms in ascending order and without duplicates.

A116623 := proc(n)
    option remember;
    if n = 0 then
        1;
    elif type(n,'even') then
        procname(n/2)+2^A000523(n) ;
    else
        3*procname(floor(n/2))+2^(1+A000523(n)) ;
    end if;
end proc: # R. J. Mathar, Nov 28 2016

a[n_] := a[n] = Which[n == 0, 1, EvenQ[n], a[n/2] + 2^Floor@Log2[n], True, 3a[Floor[n/2]] + 2^(1 + Floor@Log2[n])];
Table[a[n], {n, 0, 56}] (* Jean-François Alcover, Sep 01 2023 *)

A372354 Array read by upward antidiagonals: A(n, k) = A000523(A372282(n, k)), n,k >= 1, where A000523(x) is one less than the number of bits in the binary expansion of x.

Original entry on oeis.org

0, 4, 1, 12, 4, 2, 28, 12, 8, 2, 60, 28, 20, 5, 3, 124, 60, 44, 10, 6, 3, 252, 124, 92, 19, 13, 6, 3, 508, 252, 188, 40, 26, 11, 8, 3, 1020, 508, 380, 84, 51, 24, 20, 6, 4, 2044, 1020, 764, 172, 104, 52, 44, 11, 7, 4, 4092, 2044, 1532, 348, 212, 108, 92, 19, 16, 6, 4, 8188, 4092, 3068, 700, 428, 220, 188, 40, 36, 13, 12, 4

Offset: 1

Antti Karttunen, Apr 30 2024

			Array begins:
n\k|    1     2     3    4    5    6     7    8     9   10    11   12   13   14
---+-----------------------------------------------------------------------------
1  |    0,    1,    2,   2,   3,   3,    3,   3,    4,   4,    4,   4,   4,   4,
2  |    4,    4,    8,   5,   6,   6,    8,   6,    7,   6,   12,   7,   8,   7,
3  |   12,   12,   20,  10,  13,  11,   20,  11,   16,  13,   28,  11,  14,  12,
4  |   28,   28,   44,  19,  26,  24,   44,  19,   36,  26,   60,  24,  29,  23,
5  |   60,   60,   92,  40,  51,  52,   92,  40,   76,  51,  124,  52,  58,  44,
6  |  124,  124,  188,  84, 104, 108,  188,  84,  156, 104,  252, 108, 115,  84,
7  |  252,  252,  380, 172, 212, 220,  380, 172,  316, 212,  508, 220, 232, 165,
8  |  508,  508,  764, 348, 428, 444,  764, 348,  636, 428, 1020, 444, 468, 326,
9  | 1020, 1020, 1532, 700, 860, 892, 1532, 700, 1276, 860, 2044, 892, 940, 650,

Cf. A000523, A371094, A372282, A372356 (columnwise first differences), A372357.

Row 1 is 0 followed by A113473.

up_to = 78;
A000523(n) = logint(n,2);
A371094(n) = { my(m=1+3*n, e=valuation(m,2)); ((m*(2^e)) + (((4^e)-1)/3)); };
A372282sq(n,k) = if(1==n,2*k-1,A371094(A372282sq(n-1,k)));
A372354sq(n,k) = A000523(A372282sq(n,k));
A372354list(up_to) = { my(v = vector(up_to), i=0); for(a=1,oo, for(col=1,a, i++; if(i > up_to, return(v)); v[i] = A372354sq((a-(col-1)),col))); (v); };
v372354 = A372354list(up_to);
A372354(n) = v372354[n];

A096115 If n = (2^k)-1, a(n) = a((n+1)/2) = k, if n = 2^k, a(n) = a(n-1)+1 = k+1, otherwise a(n) = (A000523(n)+1)*a(A035327(n-1)).

Original entry on oeis.org

1, 2, 2, 3, 6, 6, 3, 4, 12, 24, 24, 12, 8, 8, 4, 5, 20, 40, 40, 60, 120, 120, 60, 20, 15, 30, 30, 15, 10, 10, 5, 6, 30, 60, 60, 90, 180, 180, 90, 120, 360, 720, 720, 360, 240, 240, 120, 30, 24, 48, 48, 72, 144, 144, 72, 24, 18, 36, 36, 18, 12, 12, 6, 7, 42, 84, 84, 126

Offset: 1

Amarnath Murthy, Jun 30 2004

nonn

A fractal sequence. For k in range [1,(2^n)-1], a(2^n + k)/a(2^n - k) = n+1. Each n > 1 occurs 2*A045778(n) times in the sequence.

Permutation of A096111, i.e. a(n) = A096111(A122199(n)-1) [Note the different starting offsets]. Cf. A096113, A052330, A096114, A096116.

(define (A096115 n) (cond ((pow2? (+ n 1)) (+ 1 (A000523 n))) ((pow2? n) (+ 1 (A096115 (- n 1)))) (else (* (+ (A000523 n) 1) (A096115 (A035327 (- n 1)))))))
(define (pow2? n) (and (> n 0) (zero? (A004198bi n (- n 1)))))

Edited, extended and Scheme code added by Antti Karttunen, Aug 25 2006

A121663 a(0) = 1; if n = 2^k, a(n) = k+2, otherwise a(n)=(A000523(n)+2)*a(A053645(n)).

Original entry on oeis.org

1, 2, 3, 6, 4, 8, 12, 24, 5, 10, 15, 30, 20, 40, 60, 120, 6, 12, 18, 36, 24, 48, 72, 144, 30, 60, 90, 180, 120, 240, 360, 720, 7, 14, 21, 42, 28, 56, 84, 168, 35, 70, 105, 210, 140, 280, 420, 840, 42, 84, 126, 252, 168, 336, 504, 1008, 210, 420, 630, 1260, 840, 1680

Offset: 0

Antti Karttunen, Aug 25 2006

nonn

Each n occurs A045778(n) times in the sequence.

Ivan Neretin, Table of n, a(n) for n = 0..8192

Bisection of A096111.

f[0] := 1; f[n_] := If[(b = n - 2^(k = Floor[Log2[n]])) == 0, k + 2, (k + 2)*f[b]]; Table[f[n], {n, 0, 61}] (* Ivan Neretin, May 09 2015 *)

(define (A121663 n) (cond ((zero? n) 1) ((pow2? n) (+ 2 (A000523 n))) (else (* (+ 2 (A000523 n)) (A121663 (A053645 n))))))
(define (pow2? n) (and (> n 0) (zero? (A004198bi n (- n 1)))))

G.f.: Product_{k>=0} (1 + (k + 2) * x^(2^k)). - Ilya Gutkovskiy, Aug 19 2019

A372358 a(n) = n XOR A086893(1+A000523(n)), where XOR is a bitwise-XOR, A003987.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, May 01 2024

a(n) gives n xored with the unique term of A086893 that has the same binary length as n itself. The binary expansions of the terms of A086893 are of the form 10101...0101 (i.e., alternating 1's and 0's starting and ending with 1) when the binary length is odd, and of the form 110101...0101 (i.e., 1 followed by alternating 1's and 0's, and ending with 1) when the binary length is even. In other words, a(n) is n with its all its even-positioned bits (indexing starts from 0 which stands for the least significant bit) inverted, and additionally also the odd-positioned most significant bit inverted if the number of significant bits is even (i.e., n is a nonzero term of A053754).

			25 in binary is 11001_2, and inverting all the even-positioned bits gives 01100_2, and as A007088(12) = 1100, a(25) = 12.
46 in binary is 101110_2, so we flip all the even-positioned bits (starting from the rightmost, with position 0), and because there are even number of bits in the binary expansion, we flip also the most significant bit, thus we obtain 011011_2, and as A007088(27) = 11011, a(46) = 27.

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

Cf. A000523, A003987, A007088, A053754, A086893 (positions of 0's), A372359, A372360, A372361, A372446.

A000523(n) = logint(n,2);
A086893(n) = (if(n%2, 2^(n+1), 2^(n+1)+2^(n-1))\3); \\ From A086893
A372358(n) = bitxor(n, A086893(1+A000523(n)));

A372447 a(n) = A000523(A372443(n)); One less than the binary length of the n-th iterate of 27 with Reduced Collatz-function R.

Original entry on oeis.org

4, 5, 4, 5, 6, 6, 7, 6, 6, 7, 6, 7, 7, 7, 8, 8, 9, 8, 7, 7, 8, 8, 8, 8, 8, 9, 10, 10, 11, 9, 10, 11, 11, 9, 8, 8, 5, 4, 5, 5, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 0

Antti Karttunen, May 03 2024

nonn

Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A000523, A372443.

A000265(n) = (n>>valuation(n,2));
A000523(n) = logint(n,2);
A372443(n) = { my(x=27); while(n, x=A000265(3*x+1); n--); (x); };
A372447(n) = A000523(A372443(n));

A372449 a(n) = A000523(A372444(n)); One less than the length of binary expansion of the n-th iterate of 27 with A371094.

Original entry on oeis.org

4, 7, 12, 23, 44, 84, 165, 326, 650, 1297, 2590, 5177, 10349, 20695, 41386, 82766, 165527, 331048, 662093, 1324181, 2648358, 5296712, 10593418, 21186832, 42373658, 84747311, 169494616, 338989224, 677978441, 1355956875, 2711913744, 5423827481, 10847654953, 21695309901, 43390619796, 86781239588, 173562479173, 347124958346

Offset: 0

Antti Karttunen, May 04 2024

nonn

Antti Karttunen, Table of n, a(n) for n = 0..1001

Cf. A371093, A371094, A372443, A372444, A372447, A372448.

Column 14 of A372354.

A000265(n) = (n>>valuation(n,2));
A000523(n) = logint(n,2);
A372443(n) = { my(x=27); while(n, x=A000265(3*x+1); n--); (x); };
A371093(n) = valuation(1+3*n,2);
A372447(n) = A000523(A372443(n));
A372448(n) = if(!n,1,2*A372448(n-1)+A371093(A372443(n)));
A372449(n) = if(0==n,A372447(n),A372447(n)+2*A372448(n-1));

a(n) = A000523(A372444(n)).

a(0) = A372447(0) = 4, and for n > 0, a(n) = A372447(n) + 2*A372448(n-1).

cp's OEIS Frontend

A096111 If n = 2^k - 1, then a(n) = k+1, otherwise a(n) = (A000523(n)+1)*a(A053645(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Scheme

Formula

Extensions

A061168 Partial sums of floor(log_2(k)) (= A000523(k)).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Formula

A080301 Local ranking function for totally balanced binary sequences: if n's binary expansion is totally balanced (A080116(n)=1), then a(n) is its zero-based position among A000108((A000523(n)+1)/2) lexicographically ordered totally balanced binary sequences of the same width, otherwise -1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A116623 a(0)=1, a(2n) = a(n)+A000079(A000523(2n)), a(2n+1) = 3*a(n) + A000079(A000523(2n+1)+1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A372354 Array read by upward antidiagonals: A(n, k) = A000523(A372282(n, k)), n,k >= 1, where A000523(x) is one less than the number of bits in the binary expansion of x.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

A096115 If n = (2^k)-1, a(n) = a((n+1)/2) = k, if n = 2^k, a(n) = a(n-1)+1 = k+1, otherwise a(n) = (A000523(n)+1)*a(A035327(n-1)).

Views

Author

Keywords

Comments

Crossrefs

Programs

Scheme

Extensions

A121663 a(0) = 1; if n = 2^k, a(n) = k+2, otherwise a(n)=(A000523(n)+2)*a(A053645(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Scheme