A014701 -id:A014701 - cp's OEIS frontend

A007931 Numbers that contain only 1's and 2's. Nonempty binary strings of length n in lexicographic order.

1, 2, 11, 12, 21, 22, 111, 112, 121, 122, 211, 212, 221, 222, 1111, 1112, 1121, 1122, 1211, 1212, 1221, 1222, 2111, 2112, 2121, 2122, 2211, 2212, 2221, 2222, 11111, 11112, 11121, 11122, 11211, 11212, 11221, 11222, 12111, 12112, 12121, 12122

Offset: 1

R. Muller

Numbers written in the dyadic system [Smullyan, Stillwell]. - N. J. A. Sloane, Feb 13 2019
Logic-binary sequence: prefix it by the empty word to have all binary words on the alphabet {1,2}.
The least binary word of length k is a(2^k - 1).
See Mathematica program for logic-binary sequence using (0,1) in place of (1,2); the sequence starts with 0,1,00,01,10. - Clark Kimberling, Feb 09 2012
A007953(a(n)) = A014701(n+1); A007954(a(n)) = A048896(n). - Reinhard Zumkeller, Oct 26 2012
a(n) is n written in base 2 where zeros are not allowed but twos are. The two distinct digits used are 1, 2 instead of 0, 1. To obtain this sequence from the "canonical" base 2 sequence with zeros allowed, just replace any 0 with a 2 and then subtract one from the group of digits situated on the left: (10-->2; 100-->12; 110-->22; 1000-->112; 1010-->122). - Robin Garcia, Jan 31 2014
For numbers made of only two different digits, see also A007088 (digits 0 & 1), A032810 (digits 2 & 3), A032834 (digits 3 & 4), A256290 (digits 4 & 5), A256291 (digits 5 & 6), A256292 (digits 6 & 7), A256340(digits 7 & 8), A256341 (digits 8 & 9), and A032804-A032816 (in other bases). Numbers with exactly two distinct (but unspecified) digits in base 10 are listed in A031955, for other bases in A031948-A031954. - M. F. Hasler, Apr 04 2015
The variant with digits {0, 1} instead of {1, 2} is obtained by deleting all initial digits in sequence A007088 (numbers written in base 2). - M. F. Hasler, Nov 03 2020

			Positive numbers may not start with 0 in the OEIS, otherwise this sequence would have been written as: 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, 00000, 00001, 00010, 00011, 00100, 00101, 00110, 00111, 01000, 01001, 01010, 01011, ...
From _Hieronymus Fischer_, Jun 06 2012: (Start)
a(10)   = 122.
a(100)  = 211212.
a(10^3) = 222212112.
a(10^4) = 1122211121112.
a(10^5) = 2111122121211112.
a(10^6) = 2221211112112111112.
a(10^7) = 11221112112122121111112.
a(10^8) = 12222212122221111211111112.
a(10^9) = 22122211221212211212111111112. (End)

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 2. - From N. J. A. Sloane, Jul 26 2012
K. Atanassov, On the 97th, 98th and the 99th Smarandache Problems, Notes on Number Theory and Discrete Mathematics, Sophia, Bulgaria, Vol. 5 (1999), No. 3, 89-93.
R. M. Smullyan, Theory of Formal Systems, Princeton, 1961.
John Stillwell, Reverse Mathematics, Princeton, 2018. See p. 90.

Hieronymus Fischer, Table of n, a(n) for n = 1..10000 (terms up to 2^10-2 from T. D. Noe, corrected by Sean A. Irvine, April 18 2019)
K. Atanassov, On Some of Smarandache's Problems, American Research Press, 1999, 16-21.
EMIS, Mirror site for Southwest Journal of Pure and Applied Mathematics
R. R. Forslund, A logical alternative to the existing positional number system, Southwest Journal of Pure and Applied Mathematics, Vol. 1, 1995.
R. R. Forslund, Positive Integer Pages
James E. Foster, A Number System without a Zero-Symbol, Mathematics Magazine, Vol. 21, No. 1. (1947), pp. 39-41.
F. Smarandache, Only Problems, Not Solutions!.
Index entries for 10-automatic sequences.

Cf. A007932 (digits 1-3), A059893, A045670, A052382 (digits 1-9), A059939, A059941, A059943, A032924, A084544, A084545, A046034 (prime digits 2,3,5,7), A089581, A084984 (no prime digits); A001742, A001743, A001744: loops; A202267 (digits 0, 1 and primes), A202268 (digits 1,4,6,8,9), A014261 (odd digits), A014263 (even digits).
Cf. A007088 (digits 0 & 1), A032810 (digits 2 & 3), A032834 (digits 3 & 4), A256290 (digits 4 & 5), A256291 (digits 5 & 6), A256292 (digits 6 & 7), A256340 (digits 7 & 8), A256341 (digits 8 & 9), and A032804-A032816 (in other bases).
Cf. A020450 (primes).

a007931 n = f (n + 1) where
   f x = if x < 2 then 0 else (10 * f x') + m + 1
     where (x', m) = divMod x 2
-- Reinhard Zumkeller, Oct 26 2012

[n: n in [1..100000] | Set(Intseq(n)) subset {1,2}]; // Vincenzo Librandi, Aug 19 2016

# Maple program to produce the sequence:
a:= proc(n) local m, r, d; m, r:= n, 0;
      while m>0 do d:= irem(m, 2, 'm');
        if d=0 then d:=2; m:= m-1 fi;
        r:= d, r
      od; parse(cat(r))/10
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Aug 26 2016
# Maple program to invert this sequence: given a(n), it returns n. - N. J. A. Sloane, Jul 09 2012
invert7931:=proc(u)
local t1,t2,i;
t1:=convert(u,base,10);
[seq(t1[i]-1,i=1..nops(t1))];
[op(%),1];
t2:=convert(%,base,2,10);
add(t2[i]*10^(i-1),i=1..nops(t2))-1;
end;

f[n_] := FromDigits[Rest@IntegerDigits[n + 1, 2] + 1]; Array[f, 42] (* Robert G. Wilson v Sep 14 2006 *)
(* Next, A007931 using (0,1) instead of (1,2) *)
d[n_] := FromDigits[Rest@IntegerDigits[n + 1, 2] + 1]; Array[FromCharacterCode[ToCharacterCode[ToString[d[#]]] - 1] &, 100] (* Peter J. C. Moses, at request of Clark Kimberling, Feb 09 2012 *)
Flatten[Table[FromDigits/@Tuples[{1,2},n],{n,5}]] (* Harvey P. Dale, Sep 13 2014 *)

apply( {A007931(n)=fromdigits([d+1|d<-binary(n+1)[^1]])}, [1..44]) \\ M. F. Hasler, Nov 03 2020, replacing older code from Mar 26 2015

/* inverse function */ apply( {A007931_inv(N)=fromdigits([d-1|d<-digits(N)],2)+2<M. F. Hasler, Nov 09 2020

def a(n): return int(bin(n+1)[3:].replace('1', '2').replace('0', '1'))
print([a(n) for n in range(1, 45)]) # Michael S. Branicky, May 13 2021

def A007931(n): return int(s:=bin(n+1)[3:])+(10**(len(s))-1)//9 # Chai Wah Wu, Jun 13 2025

To get a(n), write n+1 in base 2, remove initial 1, add 1 to all remaining digits: e.g., eleven (11) in base 2 is 1011; remove initial 1 and add 1 to remaining digits: a(10)=122. - Clark Kimberling, Mar 11 2003
Conversely, given a(n), to get n: subtract 1 from all digits, prefix with an initial 1, convert this binary number to base 10, subtract 1. E.g., a(6)=22 -> 11 -> 111 -> 7 -> 6. - N. J. A. Sloane, Jul 09 2012
a(n) = A053645(n+1)+A002275(A000523(n)) = a(n-2^b(n))+10^b(n) where b(n) = A059939(n) = floor(log_2(n+1)-1). - Henry Bottomley, Feb 14 2001
From Hieronymus Fischer, Jun 06 2012 and Jun 08 2012: (Start)
The formulas are designed to calculate base-10 numbers only using the digits 1 and 2.
a(n) = Sum_{j=0..m-1} (1 + b(j) mod 2)*10^j, where m = floor(log_2(n+1)), b(j) = floor((n+1-2^m)/(2^j)).
Special values:
a(k*(2^n-1)) = k*(10^n-1)/9, k= 1,2.
a(3*2^n-2) = (11*10^n-2)/9 = 10^n+2*(10^n-1)/9.
a(2^n-2) = 2*(10^(n-1)-1)/9, n>1.
Inequalities:
a(n) <= (10^log_2(n+1)-1)/9, equality holds for n=2^k-1, k>0.
a(n) > (2/10)*(10^log_2(n+1)-1)/9.
Lower and upper limits:
lim inf a(n)/10^log_2(n) = 1/45, for n --> infinity.
lim sup a(n)/10^log_2(n) = 1/9, for n --> infinity.
G.f.: g(x) = (1/(x(1-x)))*sum_{j=0..infinity} 10^j* x^(2*2^j)*(1 + 2 x^2^j)/(1 + x^2^j).
Also: g(x) = (1/(1-x))*(h_(2,0)(x) + h_(2,1)(x) - 2*h_(2,2)(x)), where h_(2,k)(x) = sum_{j>=0} 10^j*x^(2^(j+1)-1)*x^(k*2^j)/(1-x^2^(j+1)).
Also: g(x) = (1/(1-x)) sum_{j>=0} (1 - 3(x^2^j)^2 + 2(x^2^j)^3)*x^2^j*f_j(x)/(1-x^2^j), where f_j(x) = 10^j*x^(2^j-1)/(1-(x^2^j)^2). The f_j obey the recurrence f_0(x) = 1/(1-x^2), f_(j+1)(x) = 10x*f_j(x^2). (End)

Some crossrefs added by Hieronymus Fischer, Jun 06 2012

Edited by M. F. Hasler, Mar 26 2015

A003313 Length of shortest addition chain for n.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane

Equivalently, minimal number of multiplications required to compute the n-th power.

			For n < 149 and for many higher values of n, a(n) is the depth of n in a tree whose first 6 levels are shown below. The path from the root of the tree to n gives an optimal addition chain. (See Knuth, Vol. 2, Sect. 4.6.3, Fig. 14 and Ex. 5.)
                  1
                  |
                  2
                 / \
                /   \
               /     \
              /       \
             /         \
            3           4
           / \           \
          /   \           \
         /     \           \
        /       \           \
       5         6           8
      / \        |         /   \
     /   \       |        /     \
    7    10      12      9       16
   /    /  \    /  \    /  \    /  \
  14   11  20  15  24  13  17  18  32
E.g., a(15) = 5 and an optimal chain for 15 is 1, 2, 3, 6, 12, 15.
It is not possible to extend the tree to include the optimal addition chains for all n. For example, the chains for 43, 77, and 149 are incompatible. See the link to Achim Flammenkamp's web page on addition chains.

Hatem M. Bahig, Mohamed H. El-Zahar, and Ken Nakamula, Some results for some conjectures in addition chains, in Combinatorics, computability and logic, pp. 47-54, Springer Ser. Discrete Math. Theor. Comput. Sci., Springer, London, 2001.
D. Bleichenbacher and A. Flammenkamp, An Efficient Algorithm for Computing Shortest Addition Chains, Preprint, 1997.
A. Flammenkamp, Drei Beitraege zur diskreten Mathematik: Additionsketten, No-Three-in-Line-Problem, Sociable Numbers, Diplomarbeit, Bielefeld 1991.
S. B. Gashkov and V. V. Kochergin, On addition chains of vectors, gate circuits and the complexity of computations of powers [translation of Metody Diskret. Anal. No. 52 (1992), 22-40, 119-120; 1265027], Siberian Adv. Math. 4 (1994), 1-16.
A. A. Gioia and M. V. Subbarao, The Scholz-Brauer problem in addition chains, II, in Proceedings of the Eighth Manitoba Conference on Numerical Mathematics and Computing (Univ. Manitoba, Winnipeg, Man., 1978), pp. 251-274, Congress. Numer., XXII, Utilitas Math., Winnipeg, Man., 1979.
D. E. Knuth, The Art of Computer Programming, vol. 2, Seminumerical Algorithms, 2nd ed., Fig. 14 on page 403; 3rd edition, 1998, p. 465.
D. E. Knuth, website, further updates to Vol. 2 of TAOCP.
Michael O. Rabin and Shmuel Winograd, "Fast evaluation of polynomials by rational preparation." Communications on Pure and Applied Mathematics 25.4 (1972): 433-458. See Table p. 455.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

D. W. Wilson and Antoine Mathys, Table of n, a(n) for n = 1..100000 (10001 terms from D. W. Wilson)
F. Bergeron, J. Berstel, S. Brlek, and C. Duboc, Addition chains using continued fractions, J. Algorithms 10 (1989), 403-412.
Wawrzyniec Bieniawski, Piotr Masierak, Andrzej Tomski, and Szymon Łukaszyk, Assembly Theory - Formalizing Assembly Spaces and Discovering Patterns and Bounds, Preprints.org (2025).
Daniel Bleichenbacher, Efficiency and Security of Cryptosystems based on Number Theory. PhD Thesis, Diss. ETH No. 11404, Zürich 1996. See p. 61.
Alfred Brauer, On addition chains Bull. Amer. Math. Soc. 45, (1939). 736-739.
John M. Campbell, A binary version of the Mahler-Popken complexity function, arXiv:2403.20073 [math.NT], 2024. See pp. 3-4. See also Integers (2024) Vol. 24, Art. No. A94. See pp. 3, 10.
Peter Downey, Benton Leong, and Ravi Sethi, Computing sequences with addition chains SIAM J. Comput. 10 (1981), 638-646.
M. Elia and F. Neri, A note on addition chains and some related conjectures, (Naples/Positano, 1988), pp. 166-181 of R. M. Capocelli, ed., Sequences, Springer-Verlag, NY 1990.
Christian Elsholtz et al., Upper bound on length of addition chain, Math Overflow, Sep 18 2015.
P. Erdős, Remarks on number theory. III. On addition chains, Acta Arith. 6 1960 77-81.
Achim Flammenkamp, Shortest addition chains
A. A. Gioia, M. V. Subbarao, and M. Sugunamma, The Scholz-Brauer problem in addition chains, Duke Math. J. 29 1962 481-487.
Anastasiya Gorodilova, Sergey Agievich, Claude Carlet, Evgeny Gorkunov, Valeriya Idrisova, Nikolay Kolomeec, Alexandr Kutsenko, Svetla Nikova, Alexey Oblaukhov, Stjepan Picek, Bart Preneel, Vincent Rijmen, Natalia Tokareva, Problems and solutions of the Fourth International Students' Olympiad in Cryptography NSUCRYPTO, arXiv:1806.02059 [cs.CR], 2018.
R. L. Graham, A. C.-C. Yao, and F. F. Yao, Addition chains with multiplicative cost Discrete Math. 23 (1978), 115-119.
D. Knuth, Letter to N. J. A. Sloane, date unknown
D. E. Knuth, See the achain-all program
D. P. McCarthy, Effect of improved multiplication efficiency on exponentiation algorithms derived from addition chains Math. Comp. 46 (1986), 603-608.
Alec Mihailovs, Notes on using Flammenkamp's tables
Jorge Olivos, On vectorial addition chains J. Algorithms 2 (1981), 13-21.
Hugo Pfoertner, Addition chains
Kari Ragnarsson and Bridget Eileen Tenner, Obtainable Sizes of Topologies on Finite Sets, arXiv:0802.2550 [math.CO], 2008-2009; Journal of Combinatorial Theory, Series A 117 (2010) 138-151.
Arnold Schönhage, A lower bound for the length of addition chains Theor. Comput. Sci. 1 (1975), 1-12.
Edward G. Thurber, The Scholz-Brauer problem on addition chains Pacific J. Math. 49 (1973), 229-242.
Edward G. Thurber, On addition chains l(mn)<=l(n)-b and lower bounds for c(r) Duke Math. J. 40 (1973), 907-913.
Edward G. Thurber, Addition chains and solutions of l(2n)=l(n) and l(2^n-1)=n+l(n)-1, Discrete Math., Vol. 16 (1976), 279-289.
Edward G. Thurber, Addition chains-an erratic sequence Discrete Math. 122 (1993), 287-305.
Edward G. Thurber, Efficient generation of minimal length addition chains, SIAM J. Comput. 28 (1999), 1247-1263.
W. R. Utz, A note on the Scholz-Brauer problem in addition chains, Proc. Amer. Math. Soc. 4, (1953). 462-463.
Emanuel Vegh, A note on addition chains, J. Combinatorial Theory Ser. A 19 (1975), 117-118.
Eric Weisstein's World of Mathematics, Addition Chain.
Eric Weisstein's World of Mathematics, Scholz Conjecture.
C. T. Whyburn, A note on addition chains Proc. Amer. Math. Soc. 16 1965 1134.
Index to sequences related to the complexity of n

Cf. A003064, A003065, A005766, A014701, A079300, A230528.

a(n*m) <= a(n)+a(m). In particular, a(n^k) <= k * a(n). - Max Alekseyev, Jul 22 2005
For all n >= 2, a(n) <= (4/3)*floor(log_2 n) + 2. - Jonathan Vos Post, Oct 08 2008
From Achim Flammenkamp, Oct 26 2016: (Start)
a(n) <= 9/log_2(71) log_2(n), for all n.
It is conjectured by D. E. Knuth, K. Stolarsky et al. that for all n: floor(log_2(n)) + ceiling(log_2(v(n))) <= a(n). (End)
a(n) <= A014701(n). - Charles R Greathouse IV, Jan 03 2018
From Szymon Lukaszyk, Apr 05 2024: (Start)
For n = 2^s, a(n)=s;
for n = 2^s + 2^m, m in [0..s-1] (A048645), a(n)=s+1;
for n = 2^s + 3*2^m, m in [0..s-2] (A072823), a(n)=s+2;
for n = 2^s + 7*2^(s-3), s>2 (A072823), a(n)=s+2.(End)

More terms from Jud McCranie, Nov 01 2001

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

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

Original entry on oeis.org

0, 1, 2, 3, 3, 4, 4, 5, 4, 5, 5, 6, 5, 6, 6, 7, 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, 7, 8, 8, 9, 8, 9, 9, 10, 8, 9, 9, 10, 9, 10, 10, 11, 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

Offset: 0

N. J. A. Sloane, Sep 01 2000

A stopping problem: begin with n and at each stage if even divide by 2 or if odd subtract 1. That is, iterate A029578 while nonzero.
From Peter Kagey, Jul 16 2015: (Start)
The number of appearances of n in this sequence is identically A000045(n). Proof:
By application of the formula,
  "a(0) = 0, a(2*n+1) = a(2*n) + 1 and a(2*n) = a(n) + 1",
it can be seen that:
  {i: a(i) = n} = {2*i: a(i) = n-1, n>0} U {2*i+1: a(i) = n-2, n>1}.
Because the two sets on the left hand side share no elements:
  |{i: a(i) = n}| = |{i: a(i) = n-1, n>0}| + |{i: a(i) = n-2, n>1}|
Notice that
  |{i : a(i) = 1}| = |{1}| = 1 = A000045(1) and
  |{i : a(i) = 2}| = |{2}| = 1 = A000045(2).
Therefore the number of appearances of n in this sequence is A000045(n). (End)

			12 = 1100 in binary, so a(12)=2+4-1=5.

Charles R Greathouse IV, Table of n, a(n) for n = 0..10000
Hugo Pfoertner, Addition chains
Index to sequences related to the complexity of n

Equals A056791 - 1. The least inverse (indices of record values) of A056792 is A052955 prepended with 0. See also A014701, A115954, A056796, A056817.
Cf. A000120, A070939, A007088: base 2 sequences.
Analogous sequences with a different multiplier k: A061282 (k=3), A260112 (k=4).

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

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

f[ n_Integer ] := (c = 0; k = n; While[ k != 0, If[ EvenQ[ k ], k /= 2, k-- ]; c++ ]; c); Table[ f[ n ], {n, 0, 100} ]
f[n_] := Floor@ Log2@ n + DigitCount[n, 2, 1]; Array[f, 100] (* Robert G. Wilson v, Jul 31 2012 *)

a(n)=if(n<1,0,n-valuation(n!*sum(i=1,n,1/i),2))

PARI
```
a(n)=if(n<1,0,1+a(if(n%2,n-1,n/2)))
```

a(n)=if(n<1,0,n=binary(n);sum(i=1,#n,n[i])+#n-1) \\ Charles R Greathouse IV, Apr 11 2012

a(0) = 0, a(2*n+1) = a(2*n) + 1 and a(2*n) = a(n) + 1.
a(n) = n-valuation(A000254(n), 2) for n>0. - Benoit Cloitre, Mar 09 2004
a(n) = A000120(n) + A070939(n) - 1. - Michel Marcus, Jul 17 2015
a(n) = (weight of binary expansion of n) + (length of binary expansion of n) - 1.

More terms from James Sellers, Sep 06 2000

More terms from David W. Wilson, Sep 07 2000

A173419 Length of shortest computation yielding n using addition, subtraction and multiplication (starting from 1).

Original entry on oeis.org

0, 1, 2, 2, 3, 3, 4, 3, 3, 4, 4, 4, 5, 4, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 4, 5, 4, 5, 5, 5, 5, 4, 5, 5, 5, 4, 5, 5, 5, 5, 6, 5, 6, 6, 5, 6, 6, 5, 5, 5, 6, 6, 6, 5, 6, 5, 6, 6, 6, 5, 6, 5, 5, 4, 5, 5, 6, 5, 6, 6, 6, 5, 6, 6, 5, 6, 6, 5, 5, 5, 4, 5, 5, 5, 6, 6, 6, 6, 6, 5, 6, 6, 6, 6, 6, 5, 6, 6, 5, 5, 6, 6, 6, 6, 6, 6, 6, 5

Offset: 1

Charles R Greathouse IV, Feb 17 2010, Apr 22 2010

Let x_0 = 1 and x_m = n, with each x_k = x_i + x_j, x_k = x_i * x_j, or x_k = x_i - x_j for some 0 <= i,j < k. a(n) is the least such m.
Shub & Smale ask if there is a c such that a(n!) <= (log n)^c for all n.
If for any sequence of nonzero integers (m_i) there is no constant c such that a(n! * m_n) <= (log n)^c, then "the Hilbert Nullstellensatz is intractable, and consequently the algebraic version of 'NP != P' is true" (Shub & Smale).
Conjecture: if n is prime then a(n) >= a(n-1). The conjecture is true for n < 1800. - Dmitry Kamenetsky, Dec 26 2019

			For n = 9, one sequence is (1, 1 + 1 = 2, 1 + 2 = 3, 3 * 3 = 9). Since no shorter sequence is possible, a(9) = 3.
For n = 96, one sequence is (1, 1 + 1 = 2, 2 + 2 = 4, 2 + 4 = 6, 4*4 = 16, 6*16 = 96); no shorter is possible so a(96) = 5.

R. K. Guy, Unsolved Problems Number Theory, Sect. F26.

Alois P. Heinz, Table of n, a(n) for n = 1..1800
Peter Borwein and Joe Hobart, The extraordinary power of division in straight line programs, American Mathematical Monthly 119:7 (2012), pp. 584-592.
F. Cucker, M. Shub, and S. Smale, Separation of Complexity classes in Koiran's weak model, Theoretical Computer Science 133:1 (1994), pp. 3-14.
W. DeMelo and B. F. Svaiter, The cost of computing integers, Proc. Amer. Math. Soc. 124 (1996), pp. 1377-1378.
P. Koiran, Valiant's model and the cost of computing integers, Comput. Complex. 13 (2004), pp. 131-146.
Carlos Gustavo T. de A. Moreira, On asymptotic estimates for arithmetic cost functions, Proceedings of the American Mathematical Society 125:2 (1997), pp. 347-353.
Richard J. Mathar, Extended list of chain examples
Michael Shub and Steve Smale, On the intractability of Hilbert's Nullstellensatz and an algebraic version of "NP = P", Duke Mathematical Journal 81:1 (1995), pp. 47-54.
Al Zimmermann's Programming Contests, Factorials
Index to sequences related to the complexity of n

Records are essentially A141414.

Cf. A003313 (shortest chain using just addition), A005245 (number of 1s using just addition and multiplication), A217032(n):=A173419(n!).

g:= f->seq(f union {t}, t={seq(seq({i+j, i-j, i*j}[], j=f), i=f)} minus f):
F:= proc(n) F(n):= map(g, F(n-1)) end: F(0):= {{1}}:
S:= proc(n) S(n):= map(x->x[], F(n)) end:
a:= proc(n) local k; for k from 0 while not(n in S(k)) do od; k end:
seq(a(n), n=1..110);  # Alois P. Heinz, Sep 24 2012

a(n) <= 2 log_2(n).
a(n) >= log_2(log_2(n)) + 1.
a(n) >= log_2(n)/log_2(log_2(n)) for almost all n, as proved by Moreira (improving DeMelo & Svaiter).
a(n) <= A005245(n) <= A003313(n) <= A014701(n) <= 2*A000523(n). - Charles R Greathouse IV, Feb 07 2022

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

x :> x/3 if x == 0 mod 3, x :> x - x mod 3 otherwise. This sequence gives the number of steps needed to reach 0 or 1.

In base 3, number of 0's + (number of other digits - 1) * 2 + (1 if leading digit is 2).

If each intermediate product of the first j of the fractions, for all j < a(n), is also restricted to be an integer, the resulting sequence is A117497. The first n for which a shorter product can be obtained by allowing intermediate non-integer products is 43 = 2/1 * 2/1 * 2/1 * 2/1 * 2/1 * 4/3 * 129/128, a product of 7 fractions, where A117497(43) = 8.

cp's OEIS Frontend

A371894 Integers k such that the number of multiplications to compute the k-th power by the Chandah-sutra method (A014701) is larger than the length of the shortest addition chain for k (A003313).

Views

Author

Keywords

Comments

Links

Crossrefs

A232615 Variant of the Chandra-sutra (A014701) using 3 instead of 2, and a mod argument using residues 1 and 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

JavaScript

A007931 Numbers that contain only 1's and 2's. Nonempty binary strings of length n in lexicographic order.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Python

Formula

Extensions

A003313 Length of shortest addition chain for n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Formula

Extensions

A173419 Length of shortest computation yielding n using addition, subtraction and multiplication (starting from 1).