A056792 -id:A056792 - cp's OEIS frontend

A052955 a(2n) = 22^n - 1, a(2n+1) = 32^n - 1.

1, 2, 3, 5, 7, 11, 15, 23, 31, 47, 63, 95, 127, 191, 255, 383, 511, 767, 1023, 1535, 2047, 3071, 4095, 6143, 8191, 12287, 16383, 24575, 32767, 49151, 65535, 98303, 131071, 196607, 262143, 393215, 524287, 786431, 1048575, 1572863, 2097151, 3145727

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

a(n) is the least k such that A056792(k) = n.
One quarter of the number of positive integer (n+2) X (n+2) arrays with every 2 X 2 subblock summing to 1. - R. H. Hardin, Sep 29 2008
Number of length n+1 left factors of Dyck paths having no DUU's (here U=(1,1) and D=(1,-1)). Example: a(4)=7 because we have UDUDU, UUDDU, UUDUD, UUUDD, UUUDU, UUUUD, and UUUUU (the paths UDUUD, UDUUU, and UUDUU do not qualify).
Number of binary palindromes < 2^n (see A006995). - Hieronymus Fischer, Feb 03 2012
Partial sums of A016116 (omitting the initial term). - Hieronymus Fischer, Feb 18 2012
a(n - 1), n > 1, is the number of maximal subsemigroups of the monoid of order-preserving or -reversing partial injective mappings on a set with n elements. - Wilf A. Wilson, Jul 21 2017
Number of monomials of the algebraic normal form of the Boolean function representing the n-th bit of the product 3x in terms of the bits of x. - Sebastiano Vigna, Oct 04 2020

			G.f. = 1 + 2*x + 3*x^2 + 5*x^3 + 7*x^4 + 11*x^5 + 15*x^6 + 23*x^7 + ... - _Michael Somos_, Jun 24 2018

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Andrei Asinowski, Cyril Banderier, and Benjamin Hackl, On extremal cases of pop-stack sorting, Permutation Patterns (Zürich, Switzerland, 2019).
Andrei Asinowski, Cyril Banderier, and Benjamin Hackl, Flip-sort and combinatorial aspects of pop-stack sorting, arXiv:2003.04912 [math.CO], 2020.
J.-L. Baril, T. Mansour, and A. Petrossian, Equivalence classes of permutations modulo excedances, preprint, 2014.
J.-L. Baril, T. Mansour, and A. Petrossian, Equivalence classes of permutations modulo excedances, Journal of Combinatorics 5 (2014), 453-469.
David Blackman and Sebastiano Vigna, Scrambled Linear Pseudorandom Number Generators, ACM Transactions on Mathematical Software, Vol. 47, No. 4, p. 1-32, 2021; arXiv preprint, arXiv:1805.01407 [cs.DS], 2018.
James East, Jitender Kumar, James D. Mitchell, and Wilf A. Wilson, Maximal subsemigroups of finite transformation and partition monoids, arXiv:1706.04967 [math.GR], 2017. [_Wilf A. Wilson_, Jul 21 2017]
Brian Hopkins and Aram Tangboonduangjit, Water Cells in Compositions of 1s and 2s, arXiv:2412.11528 [math.CO], 2024. See p. 9.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1026
Mohammed A. Raouf, Fazirulhisyam Hashim, Jiun Terng Liew, and Kamal Ali Alezabi, Pseudorandom sequence contention algorithm for IEEE 802.11ah based internet of things network, PLoS ONE (2020) Vol. 15, No. 8, e0237386.
Mark Shattuck, Further Results for the Capacity Statistic Distribution on Compositions of 1's and 2's, arXiv:2501.09931 [math.CO], 2025. See p. 3.
Index to sequences related to the complexity of n
Index entries for linear recurrences with constant coefficients, signature (1,2,-2).

Cf. A000225 for even terms, A055010 for odd terms. See also A056792.
Essentially 1 more than A027383, 2 more than A060482. [Comment corrected by Klaus Brockhaus, Aug 09 2009]
Union of A000225 & A055010.
For partial sums see A027383.
See A016116 for the first differences.
Cf. A083329, A107659, A132666.
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A029744 = {s(n), n>=1}, the numbers 2^k and 3*2^k, as the parent: A029744 (s(n)); A052955 (s(n)-1), A027383 (s(n)-2), A354788 (s(n)-3), A347789 (s(n)-4), A209721 (s(n)+1), A209722 (s(n)+2), A343177 (s(n)+3), A209723 (s(n)+4); A060482, A136252 (minor differences from A354788 at the start); A354785 (3*s(n)), A354789 (3*s(n)-7). The first differences of A029744 are 1,1,1,2,2,4,4,8,8,... which essentially matches eight sequences: A016116, A060546, A117575, A131572, A152166, A158780, A163403, A320770. The bisections of A029744 are A000079 and A007283. - N. J. A. Sloane, Jul 14 2022

List([0..45], n-> ((5-(-1)^n)/2)*2^((2*n-1+(-1)^n)/4)-1); # G. C. Greubel, Oct 22 2019

a052955 n = a052955_list !! n
a052955_list = 1 : 2 : map ((+ 1) . (* 2)) a052955_list
-- Reinhard Zumkeller, Feb 22 2012

[((5-(-1)^n)/2)*2^((2*n-1+(-1)^n)/4)-1: n in [0..45]]; // G. C. Greubel, Oct 22 2019

spec := [S,{S=Prod(Sequence(Prod(Union(Z,Z),Z)),Union(Sequence(Z),Z))}, unlabeled ]: seq(combstruct[count ](spec,size=n), n=0..20);
a[0]:=0:a[1]:=1:for n from 2 to 100 do a[n]:=2*a[n-2]+2 od: seq(a[n]/2, n=2..43); # Zerinvary Lajos, Mar 16 2008

a[n_]:= If[EvenQ[n], 2^(n/2+1) -1, 3*2^((n-1)/2) -1]; Table[a[n], {n, 0, 41}] (* Robert G. Wilson v, Jun 05 2004 *)
a[0]=1; a[1]=2; a[n_]:= a[n]= 2 a[n-2] +1; Array[a, 42, 0]
a[n_]:= (2 + Mod[n, 2]) 2^Quotient[n, 2] - 1; (* Michael Somos, Jun 24 2018 *)

a(n)=(2+n%2)<<(n\2)-1 \\ Charles R Greathouse IV, Jun 19 2011

{a(n) = (n%2 + 2) * 2^(n\2) - 1}; /* Michael Somos, Jun 24 2018 */

# command line argument tells how high to take n
# Beyond a(38) = 786431 you may need a special code to handle large integers
  $lim = shift;
  sub show{};
$n = $incr = $P = 1;
show($n, $incr, $P);
$incr = 1;
for $n (2..$lim) {
    $P += $incr;
    show($n, $P, $incr, $P);
    $incr *=2 if ($n % 2); # double the increment after an odd n
}
sub show {
    my($n, $P) = @_;
    printf("%4d\t%16g\n", $n, $P);
}
# Mark A. Mandel (thnidu aT  g ma(il) doT c0m), Dec 29 2010

def A052955(n): return ((2|n&1)<<(n>>1))-1 # Chai Wah Wu, Jul 13 2023

[((5-(-1)^n)/2)*2^((2*n-1+(-1)^n)/4)-1 for n in (0..45)] # G. C. Greubel, Oct 22 2019

a(0)=1, a(1)=2; thereafter a(n) = 2*a(n-2) + 1, n >= 2.
G.f.: (1 + x - x^2)/((1 - x)*(1 - 2*x^2)).
a(n) = -1 + Sum_{alpha = RootOf(-1 + 2*Z^2)} (1/4) * (3 + 4*alpha) * alpha^(-1-n). (That is, the sum is indexed by the roots of the polynomial -1 + 2*Z^2.)
a(n) = 2^(n/2) * (3*sqrt(2)/4 + 1 - (3*sqrt(2)/4 - 1) * (-1)^n) - 1. - Paul Barry, May 23 2004
a(n) = 1 + Sum_{k=0..n-1} A016116(k). - Robert G. Wilson v, Jun 05 2004
A132340(a(n)) = A027383(n). - Reinhard Zumkeller, Aug 20 2007
From Hieronymus Fischer, Sep 15 2007: (Start)
a(n) = A027383(n-1) + 1 for n>0.
a(n) = A132666(a(n+1)-1).
a(n) = A132666(a(n-1)) + 1 for n>0.
A132666(a(n)) = a(n+1) - 1. (End)
a(n) = A027383(n+1)/2. - Zerinvary Lajos, Mar 16 2008
a(n) = (5 - (-1)^n)/2*2^floor(n/2) - 1. - Hieronymus Fischer, Feb 03 2012
a(2n+1) = (a(2*n) + a(2*n+2))/2. Combined with a(n) = 2*a(n-2) + 1, n >= 2 and a(0) = 1, this specifies the sequence. - Richard R. Forberg, Nov 30 2013
a(n) = ((5 - (-1)^n)/2)*2^((2*n - 1 + (-1)^n)/4) - 1. - Luce ETIENNE, Sep 20 2014
a(n) = -(2^(n+1)) * A107659(-3-n) for all n in Z. - Michael Somos, Jun 24 2018
E.g.f.: (1/4)*exp(-sqrt(2)*x)*(4 - 3*sqrt(2) + (4 + 3*sqrt(2))*exp(2*sqrt(2)*x) - 4*exp(x + sqrt(2)*x)). - Stefano Spezia, Oct 22 2019
A term k appears in this sequence <=> 4 does not divide binomial(k, j) for any j in 0..k. - Peter Luschny, Jun 28 2025

Formula and more terms from Henry Bottomley, May 03 2000
Additional comments from Robert G. Wilson v, Jan 29 2001
Minor edits from N. J. A. Sloane, Jul 09 2022

A232559 Sequence (or tree) generated by these rules: 1 is in S, and if x is in S, then x + 1 and 2*x are in S, and duplicates are deleted as they occur.

Original entry on oeis.org

1, 2, 3, 4, 6, 5, 8, 7, 12, 10, 9, 16, 14, 13, 24, 11, 20, 18, 17, 32, 15, 28, 26, 25, 48, 22, 21, 40, 19, 36, 34, 33, 64, 30, 29, 56, 27, 52, 50, 49, 96, 23, 44, 42, 41, 80, 38, 37, 72, 35, 68, 66, 65, 128, 31, 60, 58, 57, 112, 54, 53, 104, 51, 100, 98, 97

Offset: 1

Clark Kimberling, Nov 26 2013

Let S be the set of numbers defined by these rules:  1 is in S, and if x is in S, then x + 1 and 2*x are in S.  Then S is the set of all positive integers, which arise in generations.  Deleting duplicates as they occur, the generations are given by g(1) = (1), g(2) = (2), g(3) = (3,4), g(4) = (6,5,8), g(5) = (7,12,10,9,16), etc.  Concatenating these gives A232559, a permutation of the positive integers.  The number of numbers in g(n) is A000045(n), the n-th Fibonacci number.  It is helpful to show the results as a tree with the terms of S as nodes and edges from x to x + 1 if x + 1 has not already occurred, and an edge from x to 2*x if 2*x has not already occurred.  The positions of the odd numbers are given by A026352, and of the evens, by A026351.
The previously mentioned tree is an example of a fractal tree; that is, an infinite rooted tree T such that every complete subtree of T contains a subtree isomorphic to T. - Clark Kimberling, Jun 11 2016
The similar sequence S', generated by these rules: 0 is in S', and if x is in S', then 2*x and x+1 are in S', and duplicates are deleted as they occur, appears to equal A048679. - Rémy Sigrist, Aug 05 2017
From Katherine E. Stange and Glen Whitney, Oct 09 2021: (Start)
The beginning of this tree is
                1
                |
                2
               / \
         3..../   \......4
         |              / \
         6         5.../   \...8
        / \        |          / \
      7/   \12     10       9/   \16
This tree contains every positive integer, and one can show that the path from 1 to the integer n is exactly the sequence of intermediate values observed during the Double-And-Add Algorithm AKA Chandra Sutra Method (namely, the algorithm which begins with m = 0, reads the binary representation of n from left to right, and, for each digit 0 read, doubles m, and for each digit 1 read, doubles m and then adds 1 to m; when the algorithm terminates, m = n).
As such, the path between 1 and n is a function of the binary expansion of n.  The elements of the k-th row of the tree (generation g(k)) are all those elements whose binary expansion has k_1 digits and Hamming weight k_2, for some k_1 and k_2 such that k_1 + k_2 = k + 1.
The depth at which integer n appears in this tree is given by A014701(n) = A056792(n)-1.  For example, the depth of 1 is 0, the depth of 2 is 1, and the depths of 3 and 4 are both 2. (End)
Definition need not invoke deletion: Tree is rooted at 1, all even nodes have x+1 as a child, all nodes have 2*x as a child, and any x+1 child precedes its sibling. - Robert Munafo, May 08 2024

			Each x begets x + 1 and 2*x, but if either has already occurred it is deleted.  Thus, 1 begets 2, which begets (3,4); from which 3 begets only 6, and 4 begets (5,8).

Alois P. Heinz, Table of n, a(n) for n = 1..10000 (first 1000 terms from Clark Kimberling)
Katherine E. Stange, The Intuition behind the Double-And-Add / Square-And-Multiply Algorithm, YouTube video, 2021.
Dimitri Zucker, I Found a Simple Pattern That Encodes Different Bases, YouTube video, 2024. (Adds 0 above the root of the tree, and shows how to reconstruct the tree backwards from child nodes)
Robert Munafo, Sequences A232559 and A232561, Spanning Trees of N
Index entries for sequences that are permutations of the natural numbers

Cf. A232560 (inverse permutation), A232561, A232563, A226080, A226130.
Cf. A000045, A026352, A026351, A048679.
Cf. A243571 (rows sorted).
Cf. A014701, A056792.

a:= proc() local l, s; l, s:= [1], {1}:
      proc(n) option remember; local i, r; r:= l[1];
        l:= subsop(1=NULL, l);
        for i in [1+r, r+r] do if not i in s then
          l, s:=[l[], i], s union {i} fi
        od; r
      end
    end():
seq(a(n), n=1..100);  # Alois P. Heinz, Aug 06 2017

z = 12; g[1] = {1}; g[2] = {2}; g[n_] := Riffle[g[n - 1] + 1, 2 g[n - 1]]; j[2] = Join[g[1], g[2]]; j[n_] := Join[j[n - 1], g[n]]; g1[n_] := DeleteDuplicates[DeleteCases[g[n], Alternatives @@ j[n - 1]]]; g1[1] = g[1]; g1[2] = g[2]; t = Flatten[Table[g1[n], {n, 1, z}]]  (* this sequence *)
Table[Length[g1[n]], {n, 1, z}] (* Fibonacci numbers *)
t1 = Flatten[Table[Position[t, n], {n, 1, 200}]]  (* A232560 *)

def aupton(terms):
    alst, S, expand = [1, 2], {1, 2}, [2]
    while len(alst) < terms:
        x = expand.pop(0)
        new_elts = [y for y in [x+1, 2*x] if y not in S]
        alst.extend(new_elts); expand.extend(new_elts); S.update(new_elts)
    return alst[:terms]
print(aupton(66)) # Michael S. Branicky, Sep 14 2021

Conjecture: a(n) = A059894(A348366(n)) for n > 0. - Mikhail Kurkov, Jun 14 2022

A014701 Number of multiplications to compute n-th power by the Chandah-sutra method.

Original entry on oeis.org

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

Offset: 1

James Kilfiger (jamesk(AT)maths.warwick.ac.uk)

In other words, number of steps to reach 1 starting from n and using the process: x -> x-1 if n is odd and x -> x/2 otherwise.
a(n) = number of 0's + twice number of 1's (disregarding the leading digit 1) in the binary expansion of n, i.e., A007088(n). - Lekraj Beedassy, May 28 2010
From Daniel Forgues, Jul 31 2012: (Start)
For the binary Fibonacci rabbits sequence (A036299) (cf. OEIS Wiki link below) we have the substitution/concatenation rule: a(n), n >= 3, may be obtained by the concatenation of a(n-1) and a(n-2), with a(1) = 0, a(2) = 1. Thus, using . (dot) as the concatenation operator, we have the recursive substitution/concatenation
    a(n) = a(n-0)
    a(n) = a(n-1).a(n-2)
    a(n) = a(n-2).a(n-3).a(n-3).a(n-4)
    a(n) = a(n-3).a(n-4).a(n-4).a(n-5).a(n-4).a(n-5).a(n-5).a(n-6)
  which suggests the sequence
    {0}
    {1, 2}
    {2, 3, 3, 4}
    {3, 4, 4, 5, 4, 5, 5, 6}
  whose concatenation gives A014701 (this sequence).
Number of multiplications to compute n-th power by the Chandah-sutra method, also called left-to-right binary exponentiation:
  x^1 = x^(   1_2) =                                 (x)   (0 prod)
  x^2 = x^(  10_2) =                         (x^2)         (1 prod)
  x^3 = x^(  11_2) =                         (x^2) * (x)   (2 prod)
  x^4 = x^( 100_2) =               (x^2)^2                 (2 prod)
  x^5 = x^( 101_2) =               (x^2)^2         * (x)   (3 prod)
  x^6 = x^( 110_2) =               (x^2)^2 * (x^2)         (3 prod)
  x^7 = x^( 111_2) =               (x^2)^2 * (x^2) * (x)   (4 prod)
  x^8 = x^(1000_2) = ((x^2)^2)^2                           (3 prod) (End)
From Ya-Ping Lu, Mar 03 2021: (Start)
Index at which record m occurs is A052955(m).
First appearance of m in the sequence (or the record value m) is at n = 2^(m/2 + 1) - 1 for even m, and at n = 3*2^((m - 1)/2) - 1 for odd m.
The last appearance of m in the sequence is at n = 2^m. (End)
a(n) is the digit sum of n-1 in bijective base-2. Since the Fibonacci number F(m) can be defined as the number of ways to compose m as the sum of 1s and 2s, we get that m appears F(m) times in the sequence. - Oscar Cunningham, Apr 14 2024
Conjecture: a(n+1) is the minimal number of steps to go from 0 to n, by choosing before each step, after the first step, whether to keep the same step length or double it. The initial step length is 1. - Jean-Marc Rebert, May 15 2025

			5 -> 4 -> 2 -> 1 so 3 steps are needed to reach 1 hence a(5)=3; 9 -> 8 -> 4 -> 2 -> 1 hence a(9)=4.

Alois P. Heinz, Table of n, a(n) for n = 1..16384 (first 1000 terms from T. D. Noe)
Wawrzyniec Bieniawski, Piotr Masierak, Andrzej Tomski, and Szymon Łukaszyk, Assembly Theory - Formalizing Assembly Spaces and Discovering Patterns and Bounds, Preprints (2025).
C. K. Caldwell, The Prime Glossary, binary exponentiation
Hermann Gruber and Markus Holzer, Optimal Regular Expressions for Palindromes of Given Length, Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, Article No. 53, pp. 53:1-53:15, 2021.
J. Jordan and R. Southwell, Further Properties of Reproducing Graphs, Applied Mathematics, Vol. 1 No. 5, 2010, pp. 344-350. - From _N. J. A. Sloane_, Feb 03 2013
Szymon Łukaszyk and Wawrzyniec Bieniawski, Assembly Theory of Binary Messages (How to Assemble a Black Hole and Use it to Assemble New Binary Information?), Preprints (2024).
OEIS Wiki, Binary Fibonacci rabbits sequence
Index to sequences related to the complexity of n
Index entries for sequences related to binary expansion of n

Cf. A003313, A056791, A056792, A115964, A052955.

a014701 1 = 0
a014701 n = a007953 $ a007931 (n - 1)
-- Reinhard Zumkeller, Oct 26 2012

A014701 := proc(n) local j,k; j := n; k := 0; while(j>1) do if j mod 2=1 then j := j-1 else j := j/2 fi; k := k+1 od end;
# second Maple program:
a:= n-> add(i+1, i=Bits[Split](n))-2:
seq(a(n), n=1..128);  # Alois P. Heinz, Aug 30 2021

a[n_] := DigitCount[n, 2] /. {x_, y_} -> 2x + y - 2; Array[a, 100] (* Robert G. Wilson v, Jul 31 2012 *)

a(n)=hammingweight(n)+logint(n,2)-1 \\ Charles R Greathouse IV, Dec 29 2016

def a(n):
    if n==1:
        return 0
    return a(n//2)+1+n%2
for i in range(1,60):
    print(a(i), end=", ")
# Pablo Hueso Merino, Oct 28 2020

a(n) = A056792(n) - 1 = A056791(n) - 2.
a(n) = floor(log_2(n)) + (number of 1's in binary representation of n) - 1. - Corrected (- 1 at end) by Daniel Forgues, Aug 01 2012
a(2^n) = n, a(2^n-1) = 2*(n-1), and for n >= 2, log_2(n) <= a(n) <= 2*log_2(n) - 1. - Robert FERREOL, Oct 01 2014
Let u(1) = 1, u(2*n) = u(n)+1, u(2*n+1) = u(2*n)+1; then a(1) = 0 and a(n) = u(n-1). - Benoit Cloitre, Dec 19 2002
G.f.: -2/(1-x) + (1/(1-x)) * Sum_{k>=0} (2*x^2^k + x^2^(k+1))/(1+x^2^k). - Ralf Stephan, Aug 15 2003
From {0}, apply the substitution rule (n -> n+1, n+2) repeatedly, giving {{0}, {1, 2}, {2, 3, 3, 4}, {3, 4, 4, 5, 4, 5, 5, 6}, ...} and concatenate. - Daniel Forgues, Jul 31 2012
For n > 1: a(n) = A007953(A007931(n-1)). - Reinhard Zumkeller, Oct 26 2012
a(n) >= A003313(n). - Charles R Greathouse IV, Jan 03 2018
a(n) = a(floor(n/2)) + 1 + (n mod 2) for n > 1. - Pablo Hueso Merino, Oct 28 2020
a(n+1) = max_{1<=i<=n} (H(i) + H(n-i)) where H(n) denotes the Hamming weight of n (A000120(n)). See Lemma 8 in Gruber/Holzer 2021 article. - Hermann Gruber, Jun 26 2024

A061313 Minimal number of steps to get from 1 to n by (a) subtracting 1 or (b) multiplying by 2.

Original entry on oeis.org

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

Offset: 1

Henry Bottomley, Jun 06 2001

Also number of steps to get from n to 1 by process of adding 1 if odd, or dividing by 2 if even.
It is straightforward to prove that the number n appears F(n) times in this sequence, where F(n) is the n-th Fibonacci number (A000045). - Gary Gordon, May 31 2019
Conjecture: a(n)+2 is the sum of the terms of the Hirzebruch (negative) continued fraction for the Stern-Brocot tree fraction A007305(n)/A007306(n). - Andrey Zabolotskiy, Apr 17 2020

			a(2) = 1 since 2 = 1*2, a(3) = 3 since 3 = 1*2*2-1, a(11) = 6 since 11 = (1*2*2-1)*2*2-1.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Index to sequences related to the complexity of n

Cf. A056792, A006577, A029837, A000045.

Cf. A007305, A007306, A008687.

a061313 n = fst $ until ((== 1) . snd) (\(u, v) -> (u + 1, f v)) (0, n)
   where f n = if r == 0 then n' else n + 1  where (n', r) = divMod n 2
-- Reinhard Zumkeller, Sep 05 2015

f[n_] := Block[{c = 0, m = n}, While[m != 1, If[ EvenQ[m], While[ EvenQ[m], m = m/2; c++ ], m++; c++ ]]; Return[c]]; Table[f[n], {n, 1, 100}]

a(n)=if(n<2,0,s=n; c=1; while((s+s%2)/(2-s%2)>1,s=(s+s%2)/(2-s%2); c++); c)

xpcount(n) = { p = 1; for(x=1,n, p1 = x; ct=0; while(p1>1, if(p1%2==0,p1/=2; ct++,p1 = p1*p+1; ct++) ); print1(ct, ", ") ) }

a(n) = if(n--,2*(logint(n,2)+1)) - hammingweight(n); \\ Kevin Ryde, Oct 21 2021

a(2n) = a(n)+1; a(2n+1) = a(n+1)+2; a(1) = 0.
Is Sum_{k=1..n} a(k) asymptotic to C*n*log(n) where 3 > C > 2? - Benoit Cloitre, Aug 31 2002
G.f.: x/(1-x) * Sum_{k>=0} (x^2^k + x^2^(k+1)/(1+x^2^k)). - Ralf Stephan, Jun 14 2003
a(n) = A080791(n-1) + A029837(n). - Ralf Stephan, Jun 14 2003
a(n) = 2*A023416(n-1) + A000120(n-1) = A023416(A062880(n)) = A023416(A000695(n)) + 1. - Ralf Stephan, Jul 16 2003
a(n) = A119477(n) - 1. - Philippe Deléham, Nov 03 2008

A056791 Weight of binary expansion of n + length of binary expansion of n.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane, Sep 01 2000

			12 = 1100 in binary, so a(12)=2+4=6.

Michael De Vlieger, Table of n, a(n) for n = 0..16384
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Index to sequences related to the complexity of n

Equals A056792 + 1.
Equals A014701 + 2.
Cf. A061313, A037861.

Table[If[n==0,1,s=IntegerDigits[n,2];Total@s+Length@s],{n,0,100}] (* Giorgos Kalogeropoulos, Sep 13 2021 *)

a(n) = if (n==0, 1, my(b=binary(n)); vecsum(b) + #b); \\ Michel Marcus, Sep 13 2021

def a(n): b = bin(n)[2:]; return b.count('1') + len(b)
print([a(n) for n in range(87)]) # Michael S. Branicky, Sep 13 2021

a(n) = a((n - n mod 2) / (2 - n mod 2)) + 1 for n>0, a(0)=1. - Reinhard Zumkeller, Jul 29 2002

a(2n) = a(n)+1, a(2n+1) = a(n)+2. G.f.: 1 + 1/(1-x) * sum(k>=0, (2t+t^2)/(1+t), t=x^2^k). For n>0, a(n) = 2*A000120(n) + A080791(n) = A000120(n) + A029837(n). - Ralf Stephan, Jun 14 2003

More terms from James Sellers, Sep 06 2000 and from David W. Wilson, Sep 07 2000

A061282 Minimal number of steps to get from 0 to n by (a) adding 1 or (b) multiplying by 3. A stopping problem: begin with n and at each stage if a multiple of 3 divide by 3, otherwise subtract 1.

Original entry on oeis.org

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

Offset: 0

Henry Bottomley, Jun 06 2001

n > 0 occurs A001590(n+2) times in this sequence. - Peter Kagey, Jul 19 2015

a(n) gives the number of iterations of A260316 to reach 0. - Peter Kagey, Jul 22 2015

			a(25)=7 since 25=((0+1+1)*3+1+1)*3+1.

Alois P. Heinz, Table of n, a(n) for n = 0..10000
Index to sequences related to the complexity of n

Cf. A001590, A007089, A053735, A056792, A062153, A260316.

Analogous sequences with a different multiplier k: A056792 (k=2), A260112 (k=4).

c i = if i `mod` 3 == 0 then i `div` 3 else i - 1
b 0 foldCount = foldCount
b sheetCount foldCount = b (c sheetCount) (foldCount + 1)
a061282 n = b n 0 -- Peter Kagey, Sep 02 2015

a:= n-> (l-> nops(l)+add(i, i=l)-1)(convert(n, base, 3)):
seq(a(n), n=0..105);  # Alois P. Heinz, Jul 16 2015

a(n)=sumdigits(n,3)+#digits(n,3)-1 \\ Charles R Greathouse IV, Jul 16 2015

a(n) = A062153(n) + A053735(n) = (number of base 3 digits of n) + (sum of base 3 digits of n)-1. a(3n) = a(n)+1, a(3n+1) = a(n)+2, a(3n+2) = a(n)+3; a(0)=0, a(1)=1, a(2)=2.

A256944 Squares which are not the sums of two consecutive nonsquares.

Original entry on oeis.org

0, 1, 4, 9, 16, 36, 49, 64, 100, 144, 196, 256, 289, 324, 400, 484, 576, 676, 784, 900, 1024, 1156, 1296, 1444, 1600, 1681, 1764, 1936, 2116, 2304, 2500, 2704, 2916, 3136, 3364, 3600, 3844, 4096, 4356, 4624, 4900, 5184, 5476, 5776, 6084, 6400, 6724, 7056, 7396, 7744, 8100, 8464

Offset: 1

Juri-Stepan Gerasimov, Apr 25 2015

The union of A008843, A055792, and A016742. [Corrected by Charles R Greathouse IV, May 07 2015]

Consists of the squares of all even numbers and odd numbers in A078057 = (1, 3, 7, 17, 41, 99, ...), see also A001333 = abs(A123335). See A257282 for the square roots and A257292 for their complement in the nonnegative integers A001477. - M. F. Hasler, May 08 2015

			0, 1, 4, 9, 16, 36, are in this sequence because first 14 sums of two consecutive nonsquares are 5, 8, 11, 13, 15, 18, 21, 23, 25, 27, 29, 32, 35, 37.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A000037, A000290, A008843, A016742, A056792, A257282.

lim = 15000; s = Plus @@@ (Partition[#, 2, 1] & @ Complement[Range@ lim, Range[Floor@ Sqrt[lim]]^2]); Select[Range@ Floor[Sqrt[lim]]^2, !MemberQ[s, #] &] (* Michael De Vlieger, Apr 29 2015 *)
lst=Partition[Select[Range[0,10^6],!IntegerQ[Sqrt[#]]&],2,1]/.{a_,b_}->  a+b;a256944=Complement[Table[n^2,{n,0,Sqrt[Last[lst]]}],lst] (* timing improved by Ivan N. Ianakiev, Apr 30 2015 *)
Union[#, Range[0, Max@ #, 2]] &@ Numerator[Convergents[Sqrt@ 2, 6]]^2 (* Michael De Vlieger, Aug 06 2016, after Harvey P. Dale at A001333 *)

is(n)=issquare(n) && (n%2==0 || issquare(n\2) || issquare(n\2+1)) \\ Charles R Greathouse IV, May 07 2015

a(n) ~ 4n^2. - Charles R Greathouse IV, May 07 2015

a(n) = A257282(n)^2. - M. F. Hasler, May 08 2015

A260112 Minimal number of steps to get from 0 to n by (a) adding 1 or (b) multiplying by 4.

Original entry on oeis.org

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

Offset: 0

Peter Kagey, Jul 16 2015

a(n) = (Weight of quaternary expansion of n) + (length of quaternary expansion of n) - 1.

			For a(308) = 9, the nine steps are: 308 => 77 => 76 => 19 => 18 => 17 => 16 => 4 => 1 => 0.

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

Analogous sequences with a different multiplier k: A056792 (k=2), A061282 (k=3).

Cf. A053737, A110591, A007090: base 4 sequences.

c i = if i `mod` 4 == 0 then i `div` 4 else i - 1
b 0 foldCount = foldCount
b sheetCount foldCount = b (c sheetCount) (foldCount + 1)
a260112 n = b n 0 -- Peter Kagey, Sep 02 2015

a:= n-> (l-> nops(l)+add(i, i=l)-1)(convert(n, base, 4)):
seq(a(n), n=0..105);  # Alois P. Heinz, Jul 16 2015

a(n)=sumdigits(n,4)+#digits(n,4)-1 \\ Charles R Greathouse IV, Jul 16 2015

def a(n); n.to_s(4).length + n.to_s(4).split('').map(&:to_i).reduce(:+) - 1 end

a(n) = A053737(n) + A110591(n) - 1. - Michel Marcus, Jul 17 2015

cp's OEIS Frontend

A052955 a(2n) = 2*2^n - 1, a(2n+1) = 3*2^n - 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

Perl

Python

Sage

Formula

Extensions

A232559 Sequence (or tree) generated by these rules: 1 is in S, and if x is in S, then x + 1 and 2*x are in S, and duplicates are deleted as they occur.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A014701 Number of multiplications to compute n-th power by the Chandah-sutra method.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A061313 Minimal number of steps to get from 1 to n by (a) subtracting 1 or (b) multiplying by 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

PARI

Formula

A056791 Weight of binary expansion of n + length of binary expansion of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A061282 Minimal number of steps to get from 0 to n by (a) adding 1 or (b) multiplying by 3. A stopping problem: begin with n and at each stage if a multiple of 3 divide by 3, otherwise subtract 1.

Views

A052955 a(2n) = 22^n - 1, a(2n+1) = 32^n - 1.