A209229 -id:A209229 - cp's OEIS frontend

A000079 Powers of 2: a(n) = 2^n.

1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592

Offset: 0

N. J. A. Sloane

2^0 = 1 is the only odd power of 2.
Number of subsets of an n-set.
There are 2^(n-1) compositions (ordered partitions) of n (see for example Riordan). This is the unlabeled analog of the preferential labelings sequence A000670.
This is also the number of weakly unimodal permutations of 1..n + 1, that is, permutations with exactly one local maximum. E.g., a(4) = 16: 12345, 12354, 12453, 12543, 13452, 13542, 14532 and 15432 and their reversals. - Jon Perry, Jul 27 2003 [Proof: see next line! See also A087783.]
Proof: n must appear somewhere and there are 2^(n-1) possible choices for the subset that precedes it. These must appear in increasing order and the rest must follow n in decreasing order. QED. - N. J. A. Sloane, Oct 26 2003
a(n+1) is the smallest number that is not the sum of any number of (distinct) earlier terms.
Same as Pisot sequences E(1, 2), L(1, 2), P(1, 2), T(1, 2). See A008776 for definitions of Pisot sequences.
With initial 1 omitted, same as Pisot sequences E(2, 4), L(2, 4), P(2, 4), T(2, 4). - David W. Wilson
Not the sum of two or more consecutive numbers. - Lekraj Beedassy, May 14 2004
Least deficient or near-perfect numbers (i.e., n such that sigma(n) = A000203(n) = 2n - 1). - Lekraj Beedassy, Jun 03 2004. [Comment from Max Alekseyev, Jan 26 2005: All the powers of 2 are least deficient numbers but it is not known if there exists a least deficient number that is not a power of 2.]
Almost-perfect numbers referred to as least deficient or slightly defective (Singh 1997) numbers. Does "near-perfect numbers" refer to both almost-perfect numbers (sigma(n) = 2n - 1) and quasi-perfect numbers (sigma(n) = 2n + 1)? There are no known quasi-perfect or least abundant or slightly excessive (Singh 1997) numbers.
The sum of the numbers in the n-th row of Pascal's triangle; the sum of the coefficients of x in the expansion of (x+1)^n.
The Collatz conjecture (the hailstone sequence will eventually reach the number 1, regardless of which positive integer is chosen initially) may be restated as (the hailstone sequence will eventually reach a power of 2, regardless of which positive integer is chosen initially).
The only hailstone sequence which doesn't rebound (except "on the ground"). - Alexandre Wajnberg, Jan 29 2005
With p(n) as the number of integer partitions of n, p(i) is the number of parts of the i-th partition of n, d(i) is the number of different parts of the i-th partition of n, m(i,j) is the multiplicity of the j-th part of the i-th partition of n, one has: a(n) = Sum_{i = 1..p(n)} (p(i)! / (Product_{j=1..d(i)} m(i,j)!)). - Thomas Wieder, May 18 2005
The number of binary relations on an n-element set that are both symmetric and antisymmetric. Also the number of binary relations on an n-element set that are symmetric, antisymmetric and transitive.
The first differences are the sequence itself. - Alexandre Wajnberg and Eric Angelini, Sep 07 2005
a(n) is the largest number with shortest addition chain involving n additions. - David W. Wilson, Apr 23 2006
Beginning with a(1) = 0, numbers not equal to the sum of previous distinct natural numbers. - Giovanni Teofilatto, Aug 06 2006
For n >= 1, a(n) is equal to the number of functions f:{1, 2, ..., n} -> {1, 2} such that for a fixed x in {1, 2, ..., n} and a fixed y in {1, 2} we have f(x) != y. - Aleksandar M. Janjic and Milan Janjic, Mar 27 2007
Let P(A) be the power set of an n-element set A. Then a(n) is the number of pairs of elements {x,y} of P(A) for which x = y. - Ross La Haye, Jan 09 2008
a(n) is the number of permutations on [n+1] such that every initial segment is an interval of integers. Example: a(3) counts 1234, 2134, 2314, 2341, 3214, 3241, 3421, 4321. The map "p -> ascents of p" is a bijection from these permutations to subsets of [n]. An ascent of a permutation p is a position i such that p(i) < p(i+1). The permutations shown map to 123, 23, 13, 12, 3, 2, 1 and the empty set respectively. - David Callan, Jul 25 2008
2^(n-1) is the largest number having n divisors (in the sense of A077569); A005179(n) is the smallest. - T. D. Noe, Sep 02 2008
a(n) appears to match the number of divisors of the modified primorials (excluding 2, 3 and 5). Very limited range examined, PARI example shown. - Bill McEachen, Oct 29 2008
Successive k such that phi(k)/k = 1/2, where phi is Euler's totient function. - Artur Jasinski, Nov 07 2008
A classical transform consists (for general a(n)) in swapping a(2n) and a(2n+1); examples for Jacobsthal A001045 and successive differences: A092808, A094359, A140505. a(n) = A000079 leads to 2, 1, 8, 4, 32, 16, ... = A135520. - Paul Curtz, Jan 05 2009
This is also the (L)-sieve transform of {2, 4, 6, 8, ..., 2n, ...} = A005843. (See A152009 for the definition of the (L)-sieve transform.) - John W. Layman, Jan 23 2009
a(n) = a(n-1)-th even natural number (A005843) for n > 1. - Jaroslav Krizek, Apr 25 2009
For n >= 0, a(n) is the number of leaves in a complete binary tree of height n. For n > 0, a(n) is the number of nodes in an n-cube. - K.V.Iyer, May 04 2009
Permutations of n+1 elements where no element is more than one position right of its original place. For example, there are 4 such permutations of three elements: 123, 132, 213, and 312. The 8 such permutations of four elements are 1234, 1243, 1324, 1423, 2134, 2143, 3124, and 4123. - Joerg Arndt, Jun 24 2009
Catalan transform of A099087. - R. J. Mathar, Jun 29 2009
a(n) written in base 2: 1,10,100,1000,10000,..., i.e., (n+1) times 1, n times 0 (A011557(n)). - Jaroslav Krizek, Aug 02 2009
Or, phi(n) is equal to the number of perfect partitions of n. - Juri-Stepan Gerasimov, Oct 10 2009
These are the 2-smooth numbers, positive integers with no prime factors greater than 2. - Michael B. Porter, Oct 04 2009
A064614(a(n)) = A000244(n) and A064614(m) < A000244(n) for m < a(n). - Reinhard Zumkeller, Feb 08 2010
a(n) is the largest number m such that the number of steps of iterations of {r - (largest divisor d < r)} needed to reach 1 starting at r = m is equal to n. Example (a(5) = 32): 32 - 16 = 16; 16 - 8 = 8; 8 - 4 = 4; 4 - 2 = 2; 2 - 1 = 1; number 32 has 5 steps and is the largest such number. See A105017, A064097, A175125. - Jaroslav Krizek, Feb 15 2010
a(n) is the smallest proper multiple of a(n-1). - Dominick Cancilla, Aug 09 2010
The powers-of-2 triangle T(n, k), n >= 0 and 0 <= k <= n, begins with: {1}; {2, 4}; {8, 16, 32}; {64, 128, 256, 512}; ... . The first left hand diagonal T(n, 0) = A006125(n + 1), the first right hand diagonal T(n, n) = A036442(n + 1) and the center diagonal T(2*n, n) = A053765(n + 1). Some triangle sums, see A180662, are: Row1(n) = A122743(n), Row2(n) = A181174(n), Fi1(n) = A181175(n), Fi2(2*n) = A181175(2*n) and Fi2(2*n + 1) = 2*A181175(2*n + 1). - Johannes W. Meijer, Oct 10 2010
Records in the number of prime factors. - Juri-Stepan Gerasimov, Mar 12 2011
Row sums of A152538. - Gary W. Adamson, Dec 10 2008
A078719(a(n)) = 1; A006667(a(n)) = 0. - Reinhard Zumkeller, Oct 08 2011
The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n>=1, a(n) equals the number of 2-colored compositions of n such that no adjacent parts have the same color. - Milan Janjic, Nov 17 2011
Equals A001405 convolved with its right-shifted variant: (1 + 2x + 4x^2 + ...) = (1 + x + 2x^2 + 3x^3 + 6x^4 + 10x^5 + ...) * (1 + x + x^2 + 2x^3 + 3x^4 + 6x^5 + ...). - Gary W. Adamson, Nov 23 2011
The number of odd-sized subsets of an n+1-set. For example, there are 2^3 odd-sized subsets of {1, 2, 3, 4}, namely {1}, {2}, {3}, {4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, and {2, 3, 4}. Also, note that 2^n = Sum_{k=1..floor((n+1)/2)} C(n+1, 2k-1). - Dennis P. Walsh, Dec 15 2011
a(n) is the number of 1's in any row of Pascal's triangle (mod 2) whose row number has exactly n 1's in its binary expansion (see A007318 and A047999). (The result of putting together A001316 and A000120.) - Marcus Jaiclin, Jan 31 2012
A204455(k) = 1 if and only if k is in this sequence. - Wolfdieter Lang, Feb 04 2012
For n>=1 apparently the number of distinct finite languages over a unary alphabet, whose minimum regular expression has alphabetic width n (verified up to n=17), see the Gruber/Lee/Shallit link. - Hermann Gruber, May 09 2012
First differences of A000225. - Omar E. Pol, Feb 19 2013
This is the lexicographically earliest sequence which contains no arithmetic progression of length 3. - Daniel E. Frohardt, Apr 03 2013
a(n-2) is the number of bipartitions of {1..n} (i.e., set partitions into two parts) such that 1 and 2 are not in the same subset. - Jon Perry, May 19 2013
Numbers n such that the n-th cyclotomic polynomial has a root mod 2; numbers n such that the n-th cyclotomic polynomial has an even number of odd coefficients. - Eric M. Schmidt, Jul 31 2013
More is known now about non-power-of-2 "Almost Perfect Numbers" as described in Dagal. - Jonathan Vos Post, Sep 01 2013
Number of symmetric Ferrers diagrams that fit into an n X n box. - Graham H. Hawkes, Oct 18 2013
Numbers n such that sigma(2n) = 2n + sigma(n). - Jahangeer Kholdi, Nov 23 2013
a(1), ..., a(floor(n/2)) are all values of permanent on set of square (0,1)-matrices of order n>=2 with row and column sums 2. - Vladimir Shevelev, Nov 26 2013
Numbers whose base-2 expansion has exactly one bit set to 1, and thus has base-2 sum of digits equal to one. - Stanislav Sykora, Nov 29 2013
A072219(a(n)) = 1. - Reinhard Zumkeller, Feb 20 2014
a(n) is the largest number k such that (k^n-2)/(k-2) is an integer (for n > 1); (k^a(n)+1)/(k+1) is never an integer (for k > 1 and n > 0). - Derek Orr, May 22 2014
If x = A083420(n), y = a(n+1) and z = A087289(n), then x^2 + 2*y^2 = z^2. - Vincenzo Librandi, Jun 09 2014
The mini-sequence b(n) = least number k > 0 such that 2^k ends in n identical digits is given by {1, 18, 39}. The repeating digits are {2, 4, 8} respectively. Note that these are consecutive powers of 2 (2^1, 2^2, 2^3), and these are the only powers of 2 (2^k, k > 0) that are only one digit. Further, this sequence is finite. The number of n-digit endings for a power of 2 with n or more digits id 4*5^(n-1). Thus, for b(4) to exist, one only needs to check exponents up to 4*5^3 = 500. Since b(4) does not exist, it is clear that no other number will exist. - Derek Orr, Jun 14 2014
The least number k > 0 such that 2^k ends in n consecutive decreasing digits is a 3-number sequence given by {1, 5, 25}. The consecutive decreasing digits are {2, 32, 432}. There are 100 different 3-digit endings for 2^k. There are no k-values such that 2^k ends in '987', '876', '765', '654', '543', '321', or '210'. The k-values for which 2^k ends in '432' are given by 25 mod 100. For k = 25 + 100*x, the digit immediately before the run of '432' is {4, 6, 8, 0, 2, 4, 6, 8, 0, 2, ...} for x = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...}, respectively. Thus, we see the digit before '432' will never be a 5. So, this sequence is complete. - Derek Orr, Jul 03 2014
a(n) is the number of permutations of length n avoiding both 231 and 321 in the classical sense which are breadth-first search reading words of increasing unary-binary trees. For more details, see the entry for permutations avoiding 231 at A245898. - Manda Riehl, Aug 05 2014
Numbers n such that sigma(n) = sigma(2n) - phi(4n). - Farideh Firoozbakht, Aug 14 2014
This is a B_2 sequence: for i < j, differences a(j) - a(i) are all distinct. Here 2*a(n) < a(n+1) + 1, so a(n) - a(0) < a(n+1) - a(n). - Thomas Ordowski, Sep 23 2014
a(n) counts n-walks (closed) on the graph G(1-vertex; 1-loop, 1-loop). - David Neil McGrath, Dec 11 2014
a(n-1) counts walks (closed) on the graph G(1-vertex; 1-loop, 2-loop, 3-loop, 4-loop, ...). - David Neil McGrath, Jan 01 2015
b(0) = 4; b(n+1) is the smallest number not in the sequence such that b(n+1) - Prod_{i=0..n} b(i) divides b(n+1) - Sum_{i=0..n} b(i). Then b(n) = a(n) for n > 2. - Derek Orr, Jan 15 2015
a(n) counts the permutations of length n+2 whose first element is 2 such that the permutation has exactly one descent. - Ran Pan, Apr 17 2015
a(0)-a(30) appear, with a(26)-a(30) in error, in tablet M 08613 (see CDLI link) from the Old Babylonian period (c. 1900-1600 BC). - Charles R Greathouse IV, Sep 03 2015
Subsequence of A028982 (the squares or twice squares sequence). - Timothy L. Tiffin, Jul 18 2016
A000120(a(n)) = 1. A000265(a(n)) = 1. A000593(a(n)) = 1. - Juri-Stepan Gerasimov, Aug 16 2016
Number of monotone maps f : [0..n] -> [0..n] which are order-increasing (i <= f(i)) and idempotent (f(f(i)) = f(i)). In other words, monads on the n-th ordinal (seen as a posetal category). Any monad f determines a subset of [0..n] that contains n, by considering its set of monad algebras = fixed points { i | f(i) = i }. Conversely, any subset S of [0..n] containing n determines a monad on [0..n], by the function i |-> min { j | i <= j, j in S }. - Noam Zeilberger, Dec 11 2016
Consider n points lying on a circle. Then for n>=2 a(n-2) gives the number of ways to connect two adjacent points with nonintersecting chords. - Anton Zakharov, Dec 31 2016
Satisfies Benford's law [Diaconis, 1977; Berger-Hill, 2017] - N. J. A. Sloane, Feb 07 2017
Also the number of independent vertex sets and vertex covers in the n-empty graph. - Eric W. Weisstein, Sep 21 2017
Also the number of maximum cliques in the n-halved cube graph for n > 4. - Eric W. Weisstein, Dec 04 2017
Number of pairs of compositions of n corresponding to a seaweed algebra of index n-1. - Nick Mayers, Jun 25 2018
The multiplicative group of integers modulo a(n) is cyclic if and only if n = 0, 1, 2. For n >= 3, it is a product of two cyclic groups. - Jianing Song, Jun 27 2018
k^n is the determinant of n X n matrix M_(i, j) = binomial(k + i + j - 2, j) - binomial(i+j-2, j), in this case k=2. - Tony Foster III, May 12 2019
Solutions to the equation Phi(2n + 2*Phi(2n)) = 2n. - M. Farrokhi D. G., Jan 03 2020
a(n-1) is the number of subsets of {1,2,...,n} which have an element that is the size of the set. For example, for n = 4, a(3) = 8 and the subsets are {1}, {1,2}, {2,3}, {2,4}, {1,2,3}, {1,3,4}, {2,3,4}, {1,2,3,4}. - Enrique Navarrete, Nov 21 2020
a(n) is the number of self-inverse (n+1)-order permutations with 231-avoiding. E.g., a(3) = 8: [1234, 1243, 1324, 1432, 2134, 2143, 3214, 4321]. - Yuchun Ji, Feb 26 2021
For any fixed k > 0, a(n) is the number of ways to tile a strip of length n+1 with tiles of length 1, 2, ... k, where the tile of length k can be black or white, with the restriction that the first tile cannot be black. - Greg Dresden and Bora Bursalı, Aug 31 2023

			There are 2^3 = 8 subsets of a 3-element set {1,2,3}, namely { -, 1, 2, 3, 12, 13, 23, 123 }.

Milton Abramowitz and Irene A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 1016.
Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem, Mathematics and Computer Education Journal, Vol. 31, No. 1, pp. 24-28, Winter 1997.
John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See pp. 73, 84.
Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §4.5 Logarithms and §8.1 Terminology, pp. 150, 264.
Paul J. Nahin, An Imaginary Tale: The Story of sqrt(-1), Princeton University Press, Princeton, NJ. 1998, pp. 69-70.
Alfred S. Posamentier, Math Charmers, Tantalizing Tidbits for the Mind, Prometheus Books, NY, 2003, page 273.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 124.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
V. E. Tarakanov, Combinatorial problems on binary matrices, Combin. Analysis, MSU, 5 (1980), 4-15. (Russian)
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 141.
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 55.

N. J. A. Sloane, Table of n, 2^n for n = 0..1000
Milton Abramowitz and Irene A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Juan S. Auli and Sergi Elizalde, Wilf equivalences between vincular patterns in inversion sequences, arXiv:2003.11533 [math.CO], 2020.
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
Jonathan Beagley and Lara Pudwell, Colorful Tilings and Permutations, Journal of Integer Sequences, Vol. 24 (2021), Article 21.10.4.
Arno Berger and Theodore P. Hill, What is Benford's Law?, Notices, Amer. Math. Soc., 64:2 (2017), 132-134.
Tobias Boege and Thomas Kahle, Construction Methods for Gaussoids, arXiv:1902.11260 [math.CO], 2019.
Anicius Manlius Severinus Boethius, De arithmetica, Book 1, section 9.
Henry Bottomley, Illustration of initial terms
Douglas Butler, Powers of Two up to 2^222
Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Peter J. Cameron, Notes on Counting, Peter Cameron's Blog, 15/05/2017.
CDLI, M 08613.
Giulio Cerbai, Anders Claesson, and Luca Ferrari, Stack sorting with restricted stacks, arXiv:1907.08142 [cs.DS], 2019.
V. Coll, M. Hyatt, C. Magnant, and H. Wang, Meander graphs and Frobenius seaweed Lie algebras II, Journal of Generalized Lie Theory and Applications 9 (1) (2015) 227.
M. Coons and H. Winning, Powers of Two Modulo Powers of Three, J. Int. Seq. 18 (2015) # 15.6.1.
Keneth Adrian P. Dagal and Jose Arnaldo B. Dris, A Criterion for Almost Perfect Numbers in Terms of the Abundancy Index, arXiv:1308.6767v1 [math.NT], Aug 14 2013.
V. Dergachev and A. Kirillov, Index of Lie algebras of seaweed type, J. Lie Theory 10 (2) (2000) 331-343.
Persi Diaconis, The distribution of leading digits and uniform distribution mod 1, Ann. Probability, 5, 1977, 72--81.
Kenneth Edwards and Michael A. Allen, New combinatorial interpretations of the Fibonacci numbers squared, golden rectangle numbers, and Jacobsthal numbers using two types of tile, J. Int. Seq. 24 (2021) Article 21.3.8.
David Eppstein, Making Change in 2048, arXiv:1804.07396 [cs.DM], 2018.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 18
Joël Gay and Vincent Pilaud, The weak order on Weyl posets, arXiv:1804.06572 [math.CO], 2018.
Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors of oligomorphic permutation groups, J. Integer Seqs., Vol. 6, 2003.
Hermann Gruber, Jonathan Lee and Jeffrey Shallit, Enumerating regular expressions and their languages, arXiv:1204.4982v1 [cs.FL], 2012.
R. K. Guy, Letter to N. J. A. Sloane
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 6
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 68
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 72
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 267
Marcus Jaiclin, et al. Pascal's Triangle, Mod 2,3,5
Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
P. A. MacMahon, Memoir on the Theory of the Compositions of Numbers, Phil. Trans. Royal Soc. London A, 184 (1893), 835-901.
Victor Meally, Comparison of several sequences given in Motzkin's paper "Sorting numbers for cylinders...", letter to N. J. A. Sloane, N. D.
Augustine O. Munagi, Integer Compositions and Higher-Order Conjugation, J. Int. Seq., Vol. 21 (2018), Article 18.8.5.
R. Ondrejka, Exact values of 2^n, n=1(1)4000, Math. Comp., 23 (1969), 456.
Permutation Pattern Avoidance Library (PermPAL), Av(012_021)
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
Robert Price, Comments on A000079 concerning Elementary Cellular Automata, Feb 26 2016.
Shingo Saito, Tatsushi Tanaka, and Noriko Wakabayashi, Combinatorial Remarks on the Cyclic Sum Formula for Multiple Zeta Values, J. Int. Seq. 14 (2011) # 11.2.4, Table 1.
Michael Z. Spivey and Laura L. Steil, The k-Binomial Transforms and the Hankel Transform, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.1.
J. Tanton, A Dozen Questions about the Powers of Two, Math Horizons, Vol. 8, pp. 5-10, September 2001.
G. Villemin's Almanac of Numbers, Puissances de 2
Sage Weil, 1058 powers of two
Eric Weisstein's World of Mathematics, Abundance
Eric Weisstein's World of Mathematics, Binomial Sums
Eric Weisstein's World of Mathematics, Binomial Transform
Eric Weisstein's World of Mathematics, Hailstone Number (Collatz Problem)
Eric Weisstein's World of Mathematics, Composition
Eric Weisstein's World of Mathematics, Elementary Cellular Automaton
Eric Weisstein's World of Mathematics, Empty Graph
Eric Weisstein's World of Mathematics, Erf
Eric Weisstein's World of Mathematics, Fractional Part
Eric Weisstein's World of Mathematics, Halved Cube Graph
Eric Weisstein's World of Mathematics, Hypercube
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, Least Deficient Number
Eric Weisstein's World of Mathematics, Maximum Clique
Eric Weisstein's World of Mathematics, PowerFractional Parts
Eric Weisstein's World of Mathematics, Subset
Eric Weisstein's World of Mathematics, Vertex Cover
Wikipedia, Almost perfect number
S. Wolfram, A New Kind of Science
Index entries for sequences related to binary expansion of n
Index to Elementary Cellular Automata
Index entries for sequences related to cellular automata
Index entries for "core" sequences
Index to divisibility sequences
Index entries for related partition-counting sequences
Index entries for linear recurrences with constant coefficients, signature (2).
Index entries for sequences related to Benford's law

Cf. A000225, A038754, A133464, A140730, A037124, A001787, A001788, A001789, A003472, A054849, A002409, A054851, A140325, A140354, A000041, A152537, A001405, A007318, A000120, A000265, A000593, A001227, A077020, A077021.
This is the Hankel transform (see A001906 for the definition) of A000984, A002426, A026375, A026387, A026569, A026585, A026671 and A032351. - John W. Layman, Jul 31 2000
Euler transform of A001037, A209406 (multisets), inverse binomial transform of A000244, binomial transform of A000012.
Complement of A057716.
Boustrophedon transforms: A000734, A000752.
Range of values of A006519, A007875, A011782, A030001, A034444, A037445, A053644, and A054243.
Cf. A018900, A014311, A014312, A014313, A023688, A023689, A023690, A023691 (sum of 2, ..., 9 distinct powers of 2).
Cf. A090129.
The following are parallel families: A000079 (2^n), A004094 (2^n reversed), A028909 (2^n sorted up), A028910 (2^n sorted down), A036447 (double and reverse), A057615 (double and sort up), A263451 (double and sort down); A000244 (3^n), A004167 (3^n reversed), A321540 (3^n sorted up), A321539 (3^n sorted down), A163632 (triple and reverse), A321542 (triple and sort up), A321541 (triple and sort down).

a000079 = (2 ^)
a000079_list = iterate (* 2) 1
-- Reinhard Zumkeller, Jan 22 2014, Mar 05 2012, Dec 29 2011

[2^n: n in [0..40]]; // Vincenzo Librandi, Feb 17 2014

[n le 2 select n else 5*Self(n-1)-6*Self(n-2): n in [1..40]]; // Vincenzo Librandi, Feb 17 2014

A000079 := n->2^n; [ seq(2^n,n=0..50) ];
isA000079 := proc(n)
    local fs;
    fs := numtheory[factorset](n) ;
    if n = 1 then
        true ;
    elif nops(fs) <> 1 then
        false;
    elif op(1,fs) = 2 then
        true;
    else
        false ;
    end if;
end proc: # R. J. Mathar, Jan 09 2017

Table[2^n, {n, 0, 50}]
2^Range[0, 50] (* Wesley Ivan Hurt, Jun 14 2014 *)
LinearRecurrence[{2}, {2}, {0, 20}] (* Eric W. Weisstein, Sep 21 2017 *)
CoefficientList[Series[1/(1 - 2 x), {x, 0, 20}], x] (* Eric W. Weisstein, Sep 21 2017 *)
NestList[2# &, 1, 40] (* Harvey P. Dale, Oct 07 2019 *)

A000079(n):=2^n$ makelist(A000079(n),n,0,30); /* Martin Ettl, Nov 05 2012 */

A000079(n)=2^n \\ Edited by M. F. Hasler, Aug 27 2014

unimodal(n)=local(x,d,um,umc); umc=0; for (c=0,n!-1, x=numtoperm(n,c); d=0; um=1; for (j=2,n,if (x[j]x[j-1] && d==1,um=0); if (um==0,break)); if (um==1,print(x)); umc+=um); umc

def a(n): return 1<Michael S. Branicky, Jul 28 2022

def is_powerof2(n) -> bool: return n and (n & (n - 1)) == 0  # Peter Luschny, Apr 10 2025

(List.fill(20)(2: BigInt)).scanLeft(1: BigInt)( * ) // Alonso del Arte, Jan 16 2020

(define (A000079 n) (expt 2 n)) ;; Antti Karttunen, Mar 21 2017

a(n) = 2^n.
a(0) = 1; a(n) = 2*a(n-1).
G.f.: 1/(1 - 2*x).
E.g.f.: exp(2*x).
a(n)= Sum_{k = 0..n} binomial(n, k).
a(n) is the number of occurrences of n in A000523. a(n) = A001045(n) + A001045(n+1). a(n) = 1 + Sum_{k = 0..(n - 1)} a(k). The Hankel transform of this sequence gives A000007 = [1, 0, 0, 0, 0, 0, ...]. - Philippe Deléham, Feb 25 2004
n such that phi(n) = n/2, for n > 1, where phi is Euler's totient (A000010). - Lekraj Beedassy, Sep 07 2004
a(n + 1) = a(n) XOR 3*a(n) where XOR is the binary exclusive OR operator. - Philippe Deléham, Jun 19 2005
a(n) = StirlingS2(n + 1, 2) + 1. - Ross La Haye, Jan 09 2008
a(n+2) = 6a(n+1) - 8a(n), n = 1, 2, 3, ... with a(1) = 1, a(2) = 2. - Yosu Yurramendi, Aug 06 2008
a(n) = ka(n-1) + (4 - 2k)a(n-2) for any integer k and n > 1, with a(0) = 1, a(1) = 2. - Jaume Oliver Lafont, Dec 05 2008
a(n) = Sum_{l_1 = 0..n + 1} Sum_{l_2 = 0..n}...Sum_{l_i = 0..n - i}...Sum_{l_n = 0..1} delta(l_1, l_2, ..., l_i, ..., l_n) where delta(l_1, l_2, ..., l_i, ..., l_n) = 0 if any l_i <= l_(i+1) and l_(i+1) != 0 and delta(l_1, l_2, ..., l_i, ..., l_n) = 1 otherwise. - Thomas Wieder, Feb 25 2009
a(0) = 1, a(1) = 2; a(n) = a(n-1)^2/a(n-2), n >= 2. - Jaume Oliver Lafont, Sep 22 2009
a(n) = A173786(n, n)/2 = A173787(n + 1, n). - Reinhard Zumkeller, Feb 28 2010
If p[i] = i - 1 and if A is the Hessenberg matrix of order n defined by: A[i, j] = p[j - i + 1], (i <= j), A[i, j] = -1, (i = j + 1), and A[i, j] = 0 otherwise. Then, for n >= 1, a(n-1) = det A. - Milan Janjic, May 02 2010
If p[i] = Fibonacci(i-2) and if A is the Hessenberg matrix of order n defined by: A[i, j] = p[j - i + 1], (i <= j), A[i, j] = -1, (i = j + 1), and A[i, j] = 0 otherwise. Then, for n >= 2, a(n-2) = det A. - Milan Janjic, May 08 2010
The sum of reciprocals, 1/1 + 1/2 + 1/4 + 1/8 + ... + 1/(2^n) + ... = 2. - Mohammad K. Azarian, Dec 29 2010
a(n) = 2*A001045(n) + A078008(n) = 3*A001045(n) + (-1)^n. - Paul Barry, Feb 20 2003
a(n) = A118654(n, 2).
a(n) = A140740(n+1, 1).
a(n) = A131577(n) + A011782(n) = A024495(n) + A131708(n) + A024493(n) = A000749(n) + A038503(n) + A038504(n) + A038505(n) = A139761(n) + A139748(n) + A139714(n) + A133476(n) + A139398(n). - Paul Curtz, Jul 25 2011
a(n) = row sums of A007318. - Susanne Wienand, Oct 21 2011
a(n) = Hypergeometric([-n], [], -1). - Peter Luschny, Nov 01 2011
G.f.: A(x) = B(x)/x, B(x) satisfies B(B(x)) = x/(1 - x)^2. - Vladimir Kruchinin, Nov 10 2011
a(n) = Sum_{k = 0..n} A201730(n, k)*(-1)^k. - Philippe Deléham, Dec 06 2011
2^n = Sum_{k = 1..floor((n+1)/2)} C(n+1, 2k-1). - Dennis P. Walsh, Dec 15 2011
A209229(a(n)) = 1. - Reinhard Zumkeller, Mar 07 2012
A001227(a(n)) = 1. - Reinhard Zumkeller, May 01 2012
Sum_{n >= 1} mobius(n)/a(n) = 0.1020113348178103647430363939318... - R. J. Mathar, Aug 12 2012
E.g.f.: 1 + 2*x/(U(0) - x) where U(k) = 6*k + 1 + x^2/(6*k+3 + x^2/(6*k + 5 + x^2/U(k+1) )); (continued fraction, 3-step). - Sergei N. Gladkovskii, Dec 04 2012
a(n) = det(|s(i+2,j)|, 1 <= i,j <= n), where s(n,k) are Stirling numbers of the first kind. - Mircea Merca, Apr 04 2013
a(n) = det(|ps(i+1,j)|, 1 <= i,j <= n), where ps(n,k) are Legendre-Stirling numbers of the first kind (A129467). - Mircea Merca, Apr 06 2013
G.f.: W(0), where W(k) = 1 + 2*x*(k+1)/(1 - 2*x*(k+1)/( 2*x*(k+2) + 1/W(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 28 2013
a(n-1) = Sum_{t_1 + 2*t_2 + ... + n*t_n = n} multinomial(t_1 + t_2 + ... + t_n; t_1, t_2, ..., t_n). - Mircea Merca, Dec 06 2013
Construct the power matrix T(n,j) = [A^*j]*[S^*(j-1)] where A(n)=(1,1,1,...) and S(n)=(0,1,0,0,...) (where * is convolution operation). Then a(n-1) = Sum_{j=1..n} T(n,j). - David Neil McGrath, Jan 01 2015
a(n) = A000005(A002110(n)). - Ivan N. Ianakiev, May 23 2016
From Ilya Gutkovskiy, Jul 18 2016: (Start)
Exponential convolution of A000012 with themselves.
a(n) = Sum_{k=0..n} A011782(k).
Sum_{n>=0} a(n)/n! = exp(2) = A072334.
Sum_{n>=0} (-1)^n*a(n)/n! = exp(-2) = A092553. (End)
G.f.: (r(x) * r(x^2) * r(x^4) * r(x^8) * ...) where r(x) = A090129(x) = (1 + 2x + 2x^2 + 4x^3 + 8x^4 + ...). - Gary W. Adamson, Sep 13 2016
a(n) = A000045(n + 1) + A000045(n) + Sum_{k = 0..n - 2} A000045(k + 1)*2^(n - 2 - k). - Melvin Peralta, Dec 22 2017
a(n) = 7*A077020(n)^2 + A077021(n)^2, n>=3. - Ralf Steiner, Aug 08 2021
a(n)= n + 1 + Sum_{k=3..n+1} (2*k-5)*J(n+2-k), where Jacobsthal number J(n) = A001045(n). - Michael A. Allen, Jan 12 2022
Integral_{x=0..Pi} cos(x)^n*cos(n*x) dx = Pi/a(n) (see Nahin, pp. 69-70). - Stefano Spezia, May 17 2023

Clarified a comment T. D. Noe, Aug 30 2009
Edited by Daniel Forgues, May 12 2010
Incorrect comment deleted by Matthew Vandermast, May 17 2014
Comment corrected to match offset by Geoffrey Critzer, Nov 28 2014

A001511 The ruler function: exponent of the highest power of 2 dividing 2n. Equivalently, the 2-adic valuation of 2n.

Original entry on oeis.org

1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1

Offset: 1

N. J. A. Sloane

Number of 2's dividing 2*n.
a(n) is equivalently the exponent of the smallest power of 2 which does not divide n. - David James Sycamore, Oct 02 2023
a(n) - 1 is the number of trailing zeros in the binary expansion of n.
If you are counting in binary and the least significant bit is numbered 1, the next bit is 2, etc., a(n) is the bit that is incremented when increasing from n-1 to n. - Jud McCranie, Apr 26 2004
Number of steps to reach an integer starting with (n+1)/2 and using the map x -> x*ceiling(x) (cf. A073524).
a(n) is the number of the disk to be moved at the n-th step of the optimal solution to Towers of Hanoi problem (comment from Andreas M. Hinz).
Shows which bit to flip when creating the binary reflected Gray code (bits are numbered from the right, offset is 1). This is essentially equivalent to Hinz's comment. - Adam Kertesz, Jul 28 2001
a(n) is the Hamming distance between n and n-1 (in binary). This is equivalent to Kertesz's comments above. - Tak-Shing Chan (chan12(AT)alumni.usc.edu), Feb 25 2003
Let S(0) = {1}, S(n) = {S(n-1), S(n-1)-{x}, x+1} where x = last term of S(n-1); sequence gives S(infinity). - Benoit Cloitre, Jun 14 2003
The sum of all terms up to and including the first occurrence of m is 2^m-1. - Donald Sampson (marsquo(AT)hotmail.com), Dec 01 2003
m appears every 2^m terms starting with the 2^(m-1)th term. - Donald Sampson (marsquo(AT)hotmail.com), Dec 08 2003
Sequence read mod 4 gives A092412. - Philippe Deléham, Mar 28 2004
If q = 2n/2^A001511(n) and if b(m) is defined by b(0)=q-1 and b(m)=2*b(m-1)+1, then 2n = b(A001511(n)) + 1. - Gerald McGarvey, Dec 18 2004
Repeating pattern ABACABADABACABAE ... - Jeremy Gardiner, Jan 16 2005
Relation to C(n) = Collatz function iteration using only odd steps: a(n) is the number of right bits set in binary representation of A004767(n) (numbers of the form 4*m+3). So for m=A004767(n) it follows that there are exactly a(n) recursive steps where mBetween every two instances of any positive integer m there are exactly m distinct values (1 through m-1 and one value greater than m). - Franklin T. Adams-Watters, Sep 18 2006
Number of divisors of n of the form 2^k. - Giovanni Teofilatto, Jul 25 2007
Every prefix up to (but not including) the first occurrence of some k >= 2 is a palindrome. - Gary W. Adamson, Sep 24 2008
1 interleaved with (2 interleaved with (3 interleaved with ( ... ))). - Eric D. Burgess (ericdb(AT)gmail.com), Oct 17 2009
A054525 (Möbius transform) * A001511 = A036987 = A047999^(-1) * A001511. - Gary W. Adamson, Oct 26 2009
Equals A051731 * A036987, (inverse Möbius transform of the Fredholm-Rueppel sequence) = A047999 * A036987. - Gary W. Adamson, Oct 26 2009
Cf. A173238, showing links between generalized ruler functions and A000041. - Gary W. Adamson, Feb 14 2010
Given A000041, P(x) = A(x)/A(x^2) with P(x) = (1 + x + 2x^2 + 3x^3 + 5x^4 + 7x^5 + ...), A(x) = (1 + x + 3x^2 + 4x^3 + 10x^4 + 13x^5 + ...), A(x^2) = (1 + x^2 + 3x^4 + 4x^6 + 10x^8 + ...), where A092119 = (1, 1, 3, 4, 10, ...) = Euler transform of the ruler sequence, A001511. - Gary W. Adamson, Feb 11 2010
Subtracting 1 from every term and deleting any 0's yields the same sequence, A001511. - Ben Branman, Dec 28 2011
In the listing of the compositions of n as lists in lexicographic order, a(k) is the last part of composition(k) for all k <= 2^(n-1) and all n, see example. - Joerg Arndt, Nov 12 2012
According to Hinz, et al. (see links), this sequence was studied by Louis Gros in his 1872 pamphlet "Théorie du Baguenodier" and has therefore been called the Gros sequence.
First n terms comprise least squarefree word of length n using positive integers, where "squarefree" means that the word contains no consecutive identical subwords; e.g., 1 contains no square; 11 contains a square but 12 does not; 121 contains no square; both 1211 and 1212 have squares but 1213 does not; etc. - Clark Kimberling, Sep 05 2013
Length of 0-run starting from 2 (10, 100, 110, 1000, 1010, ...), or length of 1-run starting from 1 (1, 11, 101, 111, 1001, 1011, ...) of every second number, from right to left in binary representation. - Armands Strazds, Apr 13 2017
a(n) is also the frequency of the largest part in the integer partition having viabin number n. The viabin number of an integer partition is defined in the following way. Consider the southeast border of the Ferrers board of the integer partition and consider the binary number obtained by replacing each east step with 1 and each north step, except the last one, with 0. The corresponding decimal form is, by definition, the viabin number of the given integer partition. "Viabin" is coined from "via binary". For example, consider the integer partition [2,2,2,1]. The southeast border of its Ferrers board yields 10100, leading to the viabin number 20. - Emeric Deutsch, Jul 24 2017
As A000005(n) equals the number of even divisors of 2n and A001227(n) = A001227(2n), the formula A001511(n) = A000005(n)/A001227(n) might be read as "The number of even divisors of 2n is always divisible by the number of odd divisors of 2n" (where number of divisors means sum of zeroth powers of divisors). Conjecture: For any nonnegative integer k, the sum of the k-th powers of even divisors of n is always divisible by the sum of the k-th powers of odd divisors of n. - Ivan N. Ianakiev, Jul 06 2019
From Benoit Cloitre, Jul 14 2022: (Start)
To construct the sequence, start from 1's separated by a place 1,,1,,1,,1,,1,,1,,1,,1,,1,,1,,1,,1,,1,,1,...
Then put the 2's in every other remaining place
  1,2,1,,1,2,1,,1,2,1,,1,2,1,,1,2,1,,1,2,1,,1,2,1,...
Then the 3's in every other remaining place
  1,2,1,3,1,2,1,,1,2,1,3,1,2,1,,1,2,1,3,1,2,1,,1,2,1,...
Then the 4's in every other remaining place
  1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,,1,2,1,3,1,2,1,4,1,2,1,...
By iterating this process, we get the ruler function 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,... (End)
a(n) is the least positive integer k for which there does not exist i+j=n and a(i)=a(j)=k (cf. A322523). - Rémy Sigrist and Jianing Song, Aug 23 2022
a(n) is the smallest positive integer that does not occur in the coincidences of the sequence so far a(1..n-1) and its reverse. - Neal Gersh Tolunsky, Jan 18 2023
The geometric mean of this sequence approaches the Somos constant (A112302). - Jwalin Bhatt, Jan 31 2025

			For example, 2^1|2, 2^2|4, 2^1|6, 2^3|8, 2^1|10, 2^2|12, ... giving the initial terms 1, 2, 1, 3, 1, 2, ...
From _Omar E. Pol_, Jun 12 2009: (Start)
Triangle begins:
1;
2,1;
3,1,2,1;
4,1,2,1,3,1,2,1;
5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1;
6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1;
7,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6,1,2,1,3,...
(End)
S(0) = {} S(1) = 1 S(2) = 1, 2, 1 S(3) = 1, 2, 1, 3, 1, 2, 1 S(4) = 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1. - Yann David (yann_david(AT)hotmail.com), Mar 21 2010
From _Joerg Arndt_, Nov 12 2012: (Start)
The 16 compositions of 5 as lists in lexicographic order:
[ n]  a(n)  composition
[ 1]  [ 1]  [ 1 1 1 1 1 ]
[ 2]  [ 2]  [ 1 1 1 2 ]
[ 3]  [ 1]  [ 1 1 2 1 ]
[ 4]  [ 3]  [ 1 1 3 ]
[ 5]  [ 1]  [ 1 2 1 1 ]
[ 6]  [ 2]  [ 1 2 2 ]
[ 7]  [ 1]  [ 1 3 1 ]
[ 8]  [ 4]  [ 1 4 ]
[ 9]  [ 1]  [ 2 1 1 1 ]
[10]  [ 2]  [ 2 1 2 ]
[11]  [ 1]  [ 2 2 1 ]
[12]  [ 3]  [ 2 3 ]
[13]  [ 1]  [ 3 1 1 ]
[14]  [ 2]  [ 3 2 ]
[15]  [ 1]  [ 4 1 ]
[16]  [ 5]  [ 5 ]
a(n) is the last part in each list.
(End)
From _Omar E. Pol_, Aug 20 2013: (Start)
Also written as a triangle in which the right border gives A000027 and row lengths give A011782 and row sums give A000079 the sequence begins:
1;
2;
1,3;
1,2,1,4;
1,2,1,3,1,2,1,5;
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6;
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,7;
(End)
G.f. = x + 2*x^2 + x^3 + 3*x^4 + x^5 + 2*x^6 + x^7 + 4*x^8 + x^9 + 2*x^10 + ...

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003.
E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Academic Press, NY, 2 vols., 2nd ed., 2001-2003; see Dim- and Dim+ on p. 98; Dividing Rulers, on pp. 436-437; The Ruler Game, pp. 469-470; Ruler Fours, Fives, ... Fifteens on p. 470.
L. Gros, Théorie du Baguenodier, Aimé Vingtrinier, Lyon, 1872.
R. K. Guy, Unsolved Problems in Number Theory, Springer, 1st edition, 1981. See section E22.
A. M. Hinz, The Tower of Hanoi, in Algebras and combinatorics (Hong Kong, 1997), 277-289, Springer, Singapore, 1999.
D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.1.3, Problem 41, p. 589.
Andrew Schloss, "Towers of Hanoi" composition, in The Digital Domain. Elektra/Asylum Records 9 60303-2, 1983. Works by Jaffe (Finale to "Silicon Valley Breakdown"), McNabb ("Love in the Asylum"), Schloss ("Towers of Hanoi"), Mattox ("Shaman"), Rush, Moorer ("Lions are Growing") and others.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 1..10000
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
Joerg Arndt, Matters Computational (The Fxtbook), p. 9, pp. 733-734
Joerg Arndt, Subset-lex: did we miss an order?, arXiv:1405.6503 [math.CO], 2014.
B. Baker Swart, R. Florez, D. Narayan, and G. Rudolph Extrema Property of the k-Ranking of Directed Paths and Cycles, AKCE International Journal of Graphs and Combinatorics, 13 (2016) 38-53.
J. Britton, Tower of Hanoi Solution
Yann Bugeaud and Guo-Niu Han, A combinatorial proof of the non-vanishing of Hankel determinants of the Thue-Morse sequence, Electronic Journal of Combinatorics 21(3) (2014), #P3.26. See G(z) in (1.1).
Antonin Callard, Léo Paviet Salomon, and Pascal Vanier, Computability of extender sets in multidimensional subshifts, arXiv:2401.07549 [cs.DM], 2024.
Imanuel Chen and Michael Z. Spivey, Integral Generalized Binomial Coefficients of Multiplicative Functions, Preprint 2015; Summer Research Paper 238, Univ. Puget Sound.
Vassili Daiev, Greatest divisors of even integers: Problem 636, Math. Mag., 40 (1967), 164-165.
P. Flajolet, J.-C. Raoult, and J. Vuillemin, The number of registers required for evaluating arithmetic expressions, Theoret. Comput. Sci. 9 (1979), no. 1, 99-125.
R. Florez and D. Narayan Maximizing the number of edges in optimal k-rankings, AKCE International Journal of Graphs and Combinatorics, 12.1 (2015) 1-8.
Rigoberto Flórez, Robinson A. Higuita, and Antara Mukherjee, The Star of David and Other Patterns in Hosoya Polynomial Triangles, J. Int. Seq., Vol. 21 (2018), Article 18.4.6, also arXiv:1706.04247 [math.CO], 2017.
Madeleine Goertz and Aaron Williams, The Quaternary Gray Code and How It Can Be Used to Solve Ziggurat and Other Ziggu Puzzles, arXiv:2411.19291 [math.CO], 2024. See pp. 1, 2, 12, 24.
Fernando Q. Gouvêa, p-Adic Numbers, Springer-Verlag, 1993; see p. 23.
A. M. Hinz, S. Klavžar, U. Milutinović, and C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See 'The Gros Sequence', page 60. Book's website
Norbert Hungerbühler and Ernst Specker, A generalization of the Smarandache Function to several variables, INTEGERS 6 (2006) #A23. [See final section.]
Douglas E. Iannucci and Urban Larsson, Game values of arithmetic functions, arXiv:2101.07608 [math.NT], 2021. Section 1.1.2. p. 5.
Jonas Kaiser, On the relationship between the Collatz conjecture and Mersenne prime numbers, arXiv preprint arXiv:1608.00862 [math.GM], 2016.
J. C. Lagarias and N. J. A. Sloane, Approximate squaring (pdf, ps), Experimental Math., 13 (2004), 113-128.
S. Legendre and P. Paclet, On the Permutations Generated by Cyclic Shift , J. Int. Seq. 14 (2011) # 11.3.2.
Subhayan Roy Moulik and Sergii Strelchuk, DQC1-hardness of estimating correlation functions, arXiv:2411.05208 [quant-ph], 2024. See p. 8.
Juan Carlos Nuño and Francisco J. Muñoz, On the ubiquity of the ruler sequence, arXiv:2009.14629 [math.HO], 2020.
Michael Naylor, Abacaba-Dabacaba [updated by _Jeremy Gardiner_, Sep 11 2015]
Juan Carlos Nuño and Francisco J. Muñoz, The Ruler Sequence Revisited: A Dynamic Perspective, Mathematics (2024) Vol. 12, No. 5, 742.
Simon Plouffe, On the values of the functions ... [zeta and Gamma] ..., arXiv preprint arXiv:1310.7195 [math.NT], 2013.
Joseph Rosenbaum, Elementary Problem E319, American Mathematical Monthly, volume 45, number 10, December 1938, pages 694-696. (The A indices in P at equations 1 and 2.)
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Dinesh Thakur, Gauss sums for function fields, J. Number Theory, Volume 37, Issue 2, February 1991, Pages 242-252.
Dinesh S. Thakur, Continued fraction for the exponential for F_q[T], Journal of Number Theory, 41.2 (1992): 150-155. See page 153.
Dinesh S. Thakur, Patterns of Continued Fractions for the Analogues of e and Related Numbers in the Function Field Case, Journal of Number Theory, 66.1 (1997): 129-147. See p. 130.
Eric Weisstein's World of Mathematics, Binary Carry Sequence, Ruler Function, and Towers of Hanoi
Index entries for "core" sequences
Index entries for sequences related to binary expansion of n
Index entries for sequences that are fixed points of mappings
Index entries for sequences related to Towers of Hanoi

Column 1 of table A050600.
Sequence read mod 2 gives A035263.
Sequence is bisection of A007814, A050603, A050604, A067029, A089309.
This is Guy Steele's sequence GS(4, 2) (see A135416).
Cf. A005187 (partial sums), A085058 (bisection), A112302 (geometric mean), A171977 (2^a(n)).
Cf. A000005, A000041, A000079, A003188, A003278, A003602, A007949, A018238, A047999, A051731, A054525, A054852, A065176, A082850, A089080, A092119, A117303, A129360, A130093, A173238, A181988, A220466.
Cf. A287896, A002487, A209229 (Mobius trans.), A092673 (Dirichlet inv.).
Cf. generalized ruler functions for k=3,4,5: A051064, A115362, A055457.

a001511 n = length $ takeWhile ((== 0) . (mod n)) a000079_list
-- Reinhard Zumkeller, Sep 27 2011

a001511 n | odd n = 1 | otherwise = 1 + a001511 (n `div` 2)
-- Walt Rorie-Baety, Mar 22 2013

nmax=5;r=1;for n=2:nmax;r=[r n r];end % Adriano Caroli, Feb 26 2016

[Valuation(2*n,2): n in [1..105]]; // Bruno Berselli, Nov 23 2015

A001511 := n->2-wt(n)+wt(n-1); # where wt is defined in A000120
# This is the binary logarithm of the denominator of (256^n-1)B_{8n}/n, in Maple parlance a := n -> log[2](denom((256^n-1)*bernoulli(8*n)/n)). - Peter Luschny, May 31 2009
A001511 := n -> padic[ordp](2*n,2): seq(A001511(n), n=1..105);  # Peter Luschny, Nov 26 2010
a:= n-> ilog2((Bits[Xor](2*n, 2*n-1)+1)/2): seq(a(n), n=1..50);  # Gary Detlefs, Dec 13 2018

Array[ If[ Mod[ #, 2] == 0, FactorInteger[ # ][[1, 2]], 0] &, 105] + 1 (* or *)
Nest[ Flatten[ # /. a_Integer -> {1, a + 1}] &, {1}, 7] (* Robert G. Wilson v, Mar 04 2005 *)
IntegerExponent[2*n, 2] (* Alexander R. Povolotsky, Aug 19 2011 *)
myHammingDistance[n_, m_] := Module[{g = Max[m, n], h = Min[m, n]}, b1 = IntegerDigits[g, 2]; b2 = IntegerDigits[h, 2, Length[b1]]; HammingDistance[b1, b2]] (* Vladimir Shevelev A206853 *) Table[ myHammingDistance[n, n - 1], {n, 111}] (* Robert G. Wilson v, Apr 05 2012 *)
Table[Position[Reverse[IntegerDigits[n,2]],1,1,1],{n,110}]//Flatten (* Harvey P. Dale, Aug 18 2017 *)

a(n) = sum(k=0,floor(log(n)/log(2)),floor(n/2^k)-floor((n-1)/2^k)) /* Ralf Stephan */

a(n)=if(n%2,1,factor(n)[1,2]+1) /* Jon Perry, Jun 06 2004 */

{a(n) = if( n, valuation(n, 2) + 1, 0)}; /* Michael Somos, Sep 30 2006 */

{a(n)=if(n==1,1,polcoeff(x-sum(k=1, n-1, a(k)*x^k*(1-x^k)*(1-x+x*O(x^n))), n))} /* Paul D. Hanna, Jun 22 2007 */

def a(n): return bin(n)[2:][::-1].index("1") + 1 # Indranil Ghosh, May 11 2017

A001511 = lambda n: (n&-n).bit_length() # M. F. Hasler, Apr 09 2020

def A001511(n): return (~n & n-1).bit_length()+1 # Chai Wah Wu, Jul 01 2022

[valuation(2*n,2) for n in (1..105)]  # Bruno Berselli, Nov 23 2015

(define (A001511 n) (let loop ((n n) (e 1)) (if (odd? n) e (loop (/ n 2) (+ 1 e))))) ;; Antti Karttunen, Oct 06 2017

a(n) = A007814(n) + 1 = A007814(2*n).
a(2*n+1) = 1; a(2*n) = 1 + a(n). - Philippe Deléham, Dec 08 2003
a(n) = 2 - A000120(n) + A000120(n-1), n >= 1. - Daniele Parisse
a(n) = 1 + log_2(abs(A003188(n) - A003188(n-1))).
Multiplicative with a(p^e) = e+1 if p = 2; 1 if p > 2. - David W. Wilson, Aug 01 2001
For any real x > 1/2: lim_{N->infinity} (1/N)*Sum_{n=1..N} x^(-a(n)) = 1/(2*x-1); also lim_{N->infinity} (1/N)*Sum_{n=1..N} 1/a(n) = log(2). - Benoit Cloitre, Nov 16 2001
s(n) = Sum_{k=1..n} a(k) is asymptotic to 2*n since s(n) = 2*n - A000120(n). - Benoit Cloitre, Aug 31 2002
For any n >= 0, for any m >= 1, a(2^m*n + 2^(m-1)) = m. - Benoit Cloitre, Nov 24 2002
a(n) = Sum_{d divides n and d is odd} mu(d)*tau(n/d). - Vladeta Jovovic, Dec 04 2002
G.f.: A(x) = Sum_{k>=0} x^(2^k)/(1-x^(2^k)). - Ralf Stephan, Dec 24 2002
a(1) = 1; for n > 1, a(n) = a(n-1) + (-1)^n*a(floor(n/2)). - Vladeta Jovovic, Apr 25 2003
A fixed point of the mapping 1->12; 2->13; 3->14; 4->15; 5->16; ... . - Philippe Deléham, Dec 13 2003
Product_{k>0} (1+x^k)^a(k) is g.f. for A000041(). - Vladeta Jovovic, Mar 26 2004
G.f. A(x) satisfies A(x) = A(x^2) + x/(1-x). - Franklin T. Adams-Watters, Feb 09 2006
a(A118413(n,k)) = A002260(n,k); = a(A118416(n,k)) = A002024(n,k); a(A014480(n)) = A003602(A014480(n)). - Reinhard Zumkeller, Apr 27 2006
Ordinal transform of A003602. - Franklin T. Adams-Watters, Aug 28 2006 (The ordinal transform of a sequence b_0, b_1, b_2, ... is the sequence a_0, a_1, a_2, ... where a_n is the number of times b_n has occurred in {b_0 ... b_n}.)
Could be extended to n <= 0 using a(-n) = a(n), a(0) = 0, a(2*n) = a(n)+1 unless n=0. - Michael Somos, Sep 30 2006
A094267(2*n) = A050603(2*n) = A050603(2*n + 1) = a(n). - Michael Somos, Sep 30 2006
Sequence = A129360 * A000005 = M*V, where M = an infinite lower triangular matrix and V = d(n) as a vector: [1, 2, 2, 3, 2, 4, ...]. - Gary W. Adamson, Apr 15 2007
Row sums of triangle A130093. - Gary W. Adamson, May 13 2007
Dirichlet g.f.: zeta(s)*2^s/(2^s-1). - Ralf Stephan, Jun 17 2007
a(n) = -Sum_{d divides n} mu(2*d)*tau(n/d). - Benoit Cloitre, Jun 21 2007
G.f.: x/(1-x) = Sum_{n>=1} a(n)*x^n*( 1 - x^n ). - Paul D. Hanna, Jun 22 2007
2*n = 2^a(n)* A000265(n). - Eric Desbiaux, May 14 2009 [corrected by Alejandro Erickson, Apr 17 2012]
Multiplicative with a(2^k) = k + 1, a(p^k) = 1 for any odd prime p. - Franklin T. Adams-Watters, Jun 09 2009
With S(n): 2^n - 1 first elements of the sequence then S(0) = {} (empty list) and if n > 0, S(n) = S(n-1), n, S(n-1). - Yann David (yann_david(AT)hotmail.com), Mar 21 2010
a(n) = log_2(A046161(n)/A046161(n-1)). - Johannes W. Meijer, Nov 04 2012
a((2*n-1)*2^p) = p+1, p >= 0 and n >= 1. - Johannes W. Meijer, Feb 05 2013
a(n+1) = 1 + Sum_{j=0..ceiling(log_2(n+1))} (j * (1 - abs(sign((n mod 2^(j + 1)) - 2^j + 1)))). - Enrico Borba, Oct 01 2015
Conjecture: a(n) = A181988(n)/A003602(n). - L. Edson Jeffery, Nov 21 2015
a(n) = log_2(A006519(n)) + 1. - Doug Bell, Jun 02 2017
Inverse Moebius transform of A209229. - Andrew Howroyd, Aug 04 2018
a(n) = 1 + (A183063(n)/A001227(n)). - Omar E. Pol, Nov 06 2018 (after Franklin T. Adams-Watters)
a(n) = log_2((Xor(2*n,2*n-1)+1)/2). - Gary Detlefs, Dec 13 2018
(2^(a(n)-1)-1)*(n mod 4) = 2*floor(((n+1) mod 4)/3). - Gary Detlefs, Dec 14 2018
a(n) = A000005(n)/A001227(n). - Ivan N. Ianakiev, Jul 05 2019
a(n) = Sum_{j=1..r} (j/2^j)*(Product_{k=1..j} (1 - (-1)^floor( (n+2^(j-1))/2^(k-1) ))), for n < a predefined 2^r. - Adriano Caroli, Sep 30 2019

Name edited following suggestion by David James Sycamore, Oct 05 2023

A029837 Binary order of n: log_2(n) rounded up to next integer.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane

Or, ceiling(log_2(n)).
Worst-case cost of binary search.
Equal to number of binary digits in n unless n is a power of 2 when it is one less.
Thus a(n) gives the length of the binary representation of n - 1 (n >= 2), which is also A070939(n - 1).
Let x(0) = n > 1 and x(k + 1) = x(k) - floor(x(k)/2), then a(n) is the smallest integer such that x(a(n)) = 1. - Benoit Cloitre, Aug 29 2002
Also number of division steps when going from n to 1 by process of adding 1 if odd, or dividing by 2 if even. - Cino Hilliard, Mar 25 2003
Number of ways to write n as (x + 2^y), x >= 0. Number of ways to write n + 1 as 2^x + 3^y (cf. A004050). - Benoit Cloitre, Mar 29 2003
The minimum number of cuts for dividing an object into n (possibly unequal) pieces. - Karl Ove Hufthammer (karl(AT)huftis.org), Mar 29 2010
Partial sums of A209229; number of powers of 2 not greater than n. - Reinhard Zumkeller, Mar 07 2012

			a(1) = 0, since log_2(1) = 0.
a(2) = 1, since log_2(2) = 1.
a(3) = 2, since log_2(3) = 1.58...
a(n) = 7 for n = 65, 66, ..., 127, 128.
G.f. = x^2 + 2*x^3 + 2*x^4 + 3*x^5 + 3*x^6 + 3*x^7 + 3*x^8 + 4*x^9 + ... - _Michael Somos_, Jun 02 2019

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989, p. 70.
G. J. E. Rawlins, Compared to What? An Introduction to the Analysis of Algorithms, W. H. Freeman, 1992; see pp. 108, 118.

T. D. Noe, Table of n, a(n) for n = 1..10000
Cino Hilliard, The x+1 conjecture [broken link]
Lionel Levine, Fractal sequences and restricted Nim, arXiv:math/0409408 [math.CO], 2004.
Eric Weisstein's World of Mathematics, Bit Length.
Index entries for sequences related to binary expansion of n

Cf. A000523, A070939, A000193, A000195, A004233, A113473, A053644.
Partial sums of A036987.
Used for several definitions: A029827, A036378-A036390. Partial sums: A001855.

a029837 n = a029837_list !! (n-1)
a029837_list = scanl1 (+) a209229_list
-- Reinhard Zumkeller, Mar 07 2012
(Common Lisp) (defun A029837 (n) (integer-length (1- n))) ; James Spahlinger, Oct 15 2012

[Ceiling(Log(2, n)): n in [1..100]]; // Vincenzo Librandi, Jun 14 2019

a:= n-> (p-> p+`if`(2^pAlois P. Heinz, Mar 18 2013

a[n_] := Ceiling[Log[2, n]]; Array[a, 105] (* Robert G. Wilson v, Dec 09 2005 *)
Table[IntegerLength[n - 1, 2], {n, 1, 105}] (* Peter Luschny, Dec 02 2017 *)
a[n_] := If[n < 1, 0, BitLength[n - 1]]; (* Michael Somos, Jul 10 2018 *)
Join[{0}, IntegerLength[Range[130], 2]] (* Vincenzo Librandi, Jun 14 2019 *)

{a(n) = if( n<1, 0, ceil(log(n) / log(2)))};

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

{a(n) = if( n<2, 0, exponent(n-1)+1)}; /* Michael Somos, Jul 10 2018 */

def A029837(n):
    s = bin(n)[2:]
    return len(s) - (1 if s.count('1') == 1 else 0) # Chai Wah Wu, Jul 09 2020

def A029837(n): return (n-1).bit_length() # Chai Wah Wu, Jun 30 2022

(1 to 80).map(n => Math.ceil(Math.log(n)/Math.log(2)).toInt) // Alonso del Arte, Feb 19 2020

a(n) = ceiling(log_2(n)).
a(1) = 0; for n > 1, a(2n) = a(n) + 1, a(2n + 1) = a(n) + 1. Alternatively, a(1) = 0; for n > 1, a(n) = a(ceiling(n/2)) + 1. [corrected by Ilya Gutkovskiy, Mar 21 2020]
a(n) = k such that n^(1/k - 1) > 2 > n^(1/k), or the least value of k for which floor n^(1/k) = 1. a(n) = k for all n such that 2^(k - 1) < n < 2^k. - Amarnath Murthy, May 06 2001
G.f.: x/(1 - x) * Sum_{k >= 0} x^2^k. - Ralf Stephan, Apr 13 2002
A062383(n-1) = 2^a(n). - Johannes W. Meijer, Jul 06 2009
a(n+1) = -Sum_{k = 1..n} mu(2*k)*floor(n/k). - Benoit Cloitre, Oct 21 2009
a(n+1) = A113473(n). - Michael Somos, Jun 02 2019

Additional comments from Daniele Parisse

More terms from Michael Somos, Aug 02 2002

A050376 "Fermi-Dirac primes": numbers of the form p^(2^k) where p is prime and k >= 0.

Original entry on oeis.org

2, 3, 4, 5, 7, 9, 11, 13, 16, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 79, 81, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 149, 151, 157, 163, 167, 169, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241

Offset: 1

Christian G. Bower, Nov 15 1999

Every number n is a product of a unique subset of these numbers. This is sometimes called the Fermi-Dirac factorization of n (see A182979). Proof: In the prime factorization n = Product_{j>=1} p(j)^e(j) expand every exponent e(j) as binary number and pick the terms of this sequence corresponding to the positions of the ones in binary (it is clear that both n and n^2 have the same number of factors in this sequence, and that each factor appears with exponent 1 or 0).
Or, a(1) = 2; for n>1, a(n) = smallest number which cannot be obtained as the product of previous terms. This is evident from the unique factorization theorem and the fact that every number can be expressed as the sum of powers of 2. - Amarnath Murthy, Jan 09 2002
Except for the first term, same as A084400. - David Wasserman, Dec 22 2004
The least number having 2^n divisors (=A037992(n)) is the product of the first n terms of this sequence according to Ramanujan.
According to the Bose-Einstein distribution of particles, an unlimited number of particles may occupy the same state. On the other hand, according to the Fermi-Dirac distribution, no two particles can occupy the same state (by the Pauli exclusion principle). Unique factorizations of the positive integers by primes (A000040) and over terms of A050376 one can compare with two these distributions in physics of particles. In the correspondence with this, the factorizations over primes one can call "Bose-Einstein factorizations", while the factorizations over distinct terms of A050376 one can call "Fermi-Dirac factorizations". - Vladimir Shevelev, Apr 16 2010
The numbers of the form p^(2^k), where p is prime and k >= 0, might thus be called the "Fermi-Dirac primes", while the classic primes might be called the "Bose-Einstein primes". - Daniel Forgues, Feb 11 2011
In the theory of infinitary divisors, the most natural name of the terms is "infinitary primes" or "i-primes". Indeed, n is in the sequence, if and only if it has only two infinitary divisors. Since 1 and n are always infinitary divisors of n>1, an i-prime has no other infinitary divisors. - Vladimir Shevelev, Feb 28 2011
{a(n)} is the minimal set including all primes and closed with respect to squaring. In connection with this, note that n and n^2 have the same number of factors in their Fermi-Dirac representations. - Vladimir Shevelev, Mar 16 2012
In connection with this sequence, call an integer compact if the factors in its Fermi-Dirac factorization are pairwise coprime. The density of such integers equals (6/Pi^2)*Product_{prime p} (1+(Sum_{i>=1} p^(-(2^i-1))/(p+1))) = 0.872497... It is interesting that there exist only 7 compact factorials listed in A169661. - Vladimir Shevelev, Mar 17 2012
The first k terms of the sequence solve the following optimization problem:
Let x_1, x_2,..., x_k be integers with the restrictions: 2<=x_1A064547(Product{i=1..k} x_i) >= k.  Let the goal function be Product_{i=1..k} x_i. Then the minimal value of the goal function is Product_{i=1..k} a(i). - Vladimir Shevelev, Apr 01 2012
From Joerg Arndt, Mar 11 2013: (Start)
Similarly to the first comment, for the sequence "Numbers of the form p^(3^k) or p^(2*3^k) where p is prime and k >= 0" one obtains a factorization into distinct factors by using the ternary expansion of the exponents (here n and n^3 have the same number of such factors).
The generalization to base r would use "Numbers of the form p^(r^k), p^(2*r^k), p^(3*r^k), ..., p^((r-1)*r^k) where p is prime and k >= 0" (here n and n^r have the same number of (distinct) factors).  (End)
The first appearance of this sequence as a multiplicative basis in number theory with some new notions, formulas and theorems may have been in my 1981 paper (see the Abramovich reference). - Vladimir Shevelev, Apr 27 2014
Numbers n for which A064547(n) = 1. - Antti Karttunen, Feb 10 2016
Lexicographically earliest sequence of distinct nonnegative integers such that no term is a product of 2 or more distinct terms. Removing the distinctness requirement, the sequence becomes A000040 (the prime numbers); and the equivalent sequence where the product is of 2 distinct terms is A026416 (without its initial term, 1). - Peter Munn, Mar 05 2019
The sequence was independently developed as a multiplicative number system in 1985-1986 (and first published in 1995, see the Uhlmann reference) using a proof method involving representations of positive integers as sums of powers of 2. This approach offers an arguably simpler and more flexible means for analyzing the sequence. - Jeffrey K. Uhlmann, Nov 09 2022

			Prime powers which are not terms of this sequence:
  8 = 2^3 = 2^(1+2), 27 = 3^3 = 3^(1+2), 32 = 2^5 = 2^(1+4),
  64 = 2^6 = 2^(2+4), 125 = 5^3 = 5^(1+2), 128 = 2^7 = 2^(1+2+4)
"Fermi-Dirac factorizations":
  6 = 2*3, 8 = 2*4, 24 = 2*3*4, 27 = 3*9, 32 = 2*16, 64 = 4*16,
  108 = 3*4*9, 120 = 2*3*4*5, 121 = 121, 125 = 5*25, 128 = 2*4*16.

V. S. Abramovich, On an analog of the Euler function, Proceeding of the North-Caucasus Center of the Academy of Sciences of the USSR (Rostov na Donu) (1981) No. 2, 13-17 (Russian; MR0632989(83a:10003)).
S. Ramanujan, Highly Composite Numbers, Collected Papers of Srinivasa Ramanujan, p. 125, Ed. G. H. Hardy et al., AMS Chelsea 2000.
V. S. Shevelev, Multiplicative functions in the Fermi-Dirac arithmetic, Izvestia Vuzov of the North-Caucasus region, Nature sciences 4 (1996), 28-43 (in Russian; MR 2000f: 11097, pp. 3912-3913).
J. K. Uhlmann, Dynamic map building and localization: new theoretical foundations, Doctoral Dissertation, University of Oxford, Appendix 16, 1995.

T. D. Noe and Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Steven R. Finch, Unitarism and Infinitarism, February 25, 2004. [Cached copy, with permission of the author]
Simon Litsyn and Vladimir Shevelev, On factorization of integers with restrictions on the exponent, INTEGERS: Electronic Journal of Combinatorial Number Theory, 7 (2007), #A33, 1-36.
OEIS Wiki, "Fermi-Dirac representation" of n.
Vladimir Shevelev, Compact integers and factorials, Acta Arith. 126 (2007), no.3, 195-236.
J. K. Uhlmann, Appendix 16, Doctoral Dissertation, University of Oxford, page 243, 1995.

Cf. A000040 (primes, is a subsequence), A026416, A026477, A037992 (partial products), A050377-A050380, A052330, A064547, A066724, A084400, A176699, A182979.
Cf. A268388 (complement without 1).
Cf. A124010, subsequence of A000028, A000961, A213925, A223490.
Cf. A228520, A186945 (Fermi-Dirac analog of Ramanujan primes, A104272, and Labos primes, A080359).
Cf. also A268385, A268391, A268392.

a050376 n = a050376_list !! (n-1)
a050376_list = filter ((== 1) . a209229 . a100995) [1..]
-- Reinhard Zumkeller, Mar 19 2013

isA050376 := proc(n)
    local f,e;
    f := ifactors(n)[2] ;
    if nops(f) = 1 then
        e := op(2,op(1,f)) ;
        if isA000079(e) then
            true;
        else
            false;
        end if;
    else
        false;
    end if;
end proc:
A050376 := proc(n)
    option remember ;
    local a;
    if n = 1 then
        2 ;
    else
        for a from procname(n-1)+1 do
            if isA050376(a) then
                return a;
            end if;
        end do:
    end if;
end proc: # R. J. Mathar, May 26 2017

nn = 300; t = {}; k = 1; While[lim = nn^(1/k); lim > 2,  t = Join[t, Prime[Range[PrimePi[lim]]]^k]; k = 2 k]; t = Union[t] (* T. D. Noe, Apr 05 2012 *)

{a(n)= local(m, c, k, p); if(n<=1, 2*(n==1), n--; c=0; m=2; while( cMichael Somos, Apr 15 2005; edited by Michel Marcus, Aug 07 2021

lst(lim)=my(v=primes(primepi(lim)),t); forprime(p=2,sqrt(lim),t=p; while((t=t^2)<=lim,v=concat(v,t))); vecsort(v) \\ Charles R Greathouse IV, Apr 10 2012

is_A050376(n)=2^#binary(n=isprimepower(n))==n*2 \\ M. F. Hasler, Apr 08 2015

ispow2(n)=n && n>>valuation(n,2)==1
is(n)=ispow2(isprimepower(n)) \\ Charles R Greathouse IV, Sep 18 2015

isok(n)={my(e=isprimepower(n)); e && !bitand(e,e-1)} \\ Andrew Howroyd, Oct 16 2024

from sympy import isprime, perfect_power
def ok(n):
  if isprime(n): return True
  answer = perfect_power(n)
  if not answer: return False
  b, e = answer
  if not isprime(b): return False
  while e%2 == 0: e //= 2
  return e == 1
def aupto(limit):
  alst, m = [], 1
  for m in range(1, limit+1):
    if ok(m): alst.append(m)
  return alst
print(aupto(241)) # Michael S. Branicky, Feb 03 2021

from sympy import primepi, integer_nthroot
def A050376(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return n+x-sum(primepi(integer_nthroot(x,1<Chai Wah Wu, Feb 18-19 2025

(define A050376 (MATCHING-POS 1 1 (lambda (n) (= 1 (A064547 n)))))
;; Requires also my IntSeq-library. - Antti Karttunen, Feb 09 2016

From Vladimir Shevelev, Mar 16 2012: (Start)
Product_{i>=1} a(i)^k_i = n!, where k_i = floor(n/a(i)) - floor(n/a(i)^2) + floor(n/a(i)^3) - floor(n/a(i)^4) + ...
Denote by A(x) the number of terms not exceeding x.
Then A(x) = pi(x) + pi(x^(1/2)) + pi(x^(1/4)) + pi(x^(1/8)) + ...
Conversely, pi(x) = A(x) - A(sqrt(x)). For example, pi(37) = A(37) - A(6) = 16-4 = 12. (End)
A209229(A100995(a(n))) = 1. - Reinhard Zumkeller, Mar 19 2013
From Vladimir Shevelev, Aug 31 2013: (Start)
A Fermi-Dirac analog of Euler product: Zeta(s) = Product_{k>=1} (1+a(k)^(-s)), for s > 1.
In particular, Product_{k>=1} (1+a(k)^(-2)) = Pi^2/6. (End)
a(n) = A268385(A268392(n)). [By their definitions.] - Antti Karttunen, Feb 10 2016
A000040 union A001248 union A030514 union A179645 union A030635 union .... - R. J. Mathar, May 26 2017

Edited by Charles R Greathouse IV, Mar 17 2010

More examples from Daniel Forgues, Feb 09 2011

A163511 a(0)=1. a(n) = p(A000120(n)) * Product_{m=1..A000120(n)} p(m)^A163510(n,m), where p(m) is the m-th prime.

Original entry on oeis.org

1, 2, 4, 3, 8, 9, 6, 5, 16, 27, 18, 25, 12, 15, 10, 7, 32, 81, 54, 125, 36, 75, 50, 49, 24, 45, 30, 35, 20, 21, 14, 11, 64, 243, 162, 625, 108, 375, 250, 343, 72, 225, 150, 245, 100, 147, 98, 121, 48, 135, 90, 175, 60, 105, 70, 77, 40, 63, 42, 55, 28, 33, 22, 13, 128

Offset: 0

Leroy Quet, Jul 29 2009

This is a permutation of the positive integers.
From Antti Karttunen, Jun 20 2014: (Start)
Note the indexing: the domain starts from 0, while the range excludes zero, thus this is neither a bijection on the set of nonnegative integers nor on the set of positive natural numbers, but a bijection from the former set to the latter.
Apart from that discrepancy, this could be viewed as yet another "entanglement permutation" where the two complementary pairs to be interwoven together are even and odd numbers (A005843/A005408) which are entangled with the complementary pair even numbers (taken straight) and odd numbers in the order they appear in A003961: (A005843/A003961). See also A246375 which has almost the same recurrence.
Note how the even bisection halved gives the same sequence back. (For a(0)=1, take ceiling of 1/2).
(End)
From Antti Karttunen, Dec 30 2017: (Start)
This irregular table can be represented as a binary tree. Each child to the left is obtained by doubling the parent, and each child to the right is obtained by applying A003961 to the parent:
                                     1
                                     |
                  ...................2...................
                 4                                       3
       8......../ \........9                   6......../ \........5
      / \                 / \                 / \                 / \
     /   \               /   \               /   \               /   \
    /     \             /     \             /     \             /     \
  16       27         18       25         12       15         10       7
32  81   54  125    36  75   50  49     24  45   30  35     20  21   14 11
etc.
Sequence A005940 is obtained by scanning the same tree level by level in mirror image fashion. Also in binary trees A253563 and A253565 the terms on level of the tree are some permutation of the terms present on the level n of this tree. A252464(n) gives the distance of n from 1 in all these trees, and A252463 gives the parent of the node containing n.
A252737(n) gives the sum and A252738(n) the product of terms on row n (where 1 is on row 0, 1 on row 1, 3 and 4 on row 2, etc.). A252745(n) gives the number of nodes on level n whose left child is smaller than the right child, and A252744(n) is an indicator function for those nodes.
(End)
Note that the idea behind maps like this (and the mirror image A005940) admits also using alternative orderings of primes, not just standard magnitude-wise ordering (A000040). For example, A332214 is a similar sequence but with primes rearranged as in A332211, and A332817 is obtained when primes are rearranged as in A108546. - Antti Karttunen, Mar 11 2020
From Lorenzo Sauras Altuzarra, Nov 28 2020: (Start)
This sequence is generated from A228351 by applying the following procedure: 1) eliminate the compositions that end in one unless the first one, 2) subtract one unit from every component, 3) replace every tuple [t_1, ..., t_r] by Product_{k=1..r} A000040(k)^(t_k) (see the examples).
Is it true that a(n) = A337909(n+1) if and only if a(n+1) is not a term of A161992?
Does this permutation have any other cycle apart from (1), (2) and (6, 9, 16, 7)? (End)
From Antti Karttunen, Jul 25 2023: (Start)
(In the above question, it is assumed that the starting offset would be 1 instead of 0).
Questions:
Does a(n) = 1+A054429(n) hold only when n is of the form 2^k times 1, 3 or 7, i.e., one of the terms of A029748?
It seems that A007283 gives all fixed points of map n -> a(n), like A335431 seems to give all fixed points of map n -> A332214(n). Is there a general rule for mappings like these that the fixed points (if they exist) must be of the form 2^k times a certain kind of prime, i.e., that any odd composite (times 2^k) can certainly be excluded? See also note in A029747.
(End)
If the conjecture given in A364297 holds, then it implies the above conjecture about A007283. See also A364963. - Antti Karttunen, Sep 06 2023
Conjecture: a(n^k) is never of the form x^k, for any integers n > 0, k > 1, x >= 1. This holds at least for squares, cubes, seventh and eleventh powers (see A365808, A365801, A366287 and A366391). - Antti Karttunen, Sep 24 2023, Oct 10 2023.
See A365805 for why the above holds for any n^k, with k > 1. - Antti Karttunen, Nov 23 2023

			For n=3, whose binary representation is "11", we have A000120(3)=2, with A163510(3,1) = A163510(3,2) = 0, thus a(3) = p(2) * p(1)^0 * p(2)^0 = 3*1*1 = 3.
For n=9, "1001" in binary, we have A000120(9)=2, with A163510(9,1) = 0 and A163510(9,2) = 2, thus a(9) = p(2) * p(1)^0 * p(2)^2 = 3*1*9 = 27.
For n=10, "1010" in binary, we have A000120(10)=2, with A163510(10,1) = 1 and A163510(10,2) = 1, thus a(10) = p(2) * p(1)^1 * p(2)^1 = 3*2*3 = 18.
For n=15, "1111" in binary, we have A000120(15)=4, with A163510(15,1) = A163510(15,2) = A163510(15,3) = A163510(15,4) = 0, thus a(15) = p(4) * p(1)^0 * p(2)^0 * p(3)^0 * p(4)^0 = 7*1*1*1*1 = 7.
[1], [2], [1,1], [3], [1,2], [2,1] ... -> [1], [2], [3], [1,2], ... -> [0], [1], [2], [0,1], ... -> 2^0, 2^1, 2^2, 2^0*3^1, ... = 1, 2, 4, 3, ... - _Lorenzo Sauras Altuzarra_, Nov 28 2020

Inverse: A243071.
Cf. A000040, A000120, A000225, A000788, A003961, A007814, A054429, A055396, A064216, A135523, A161992, A163510, A245605, A245612, A246375, A246378, A246681, A161511, A228351, A243499, A243503, A243504, A269854, A280873, A285727, A290251, A293437, A337909.
Cf. A007283 (known positions where a(n)=n), A029747, A029748, A364255 [= gcd(n,a(n))], A364258 [= a(n)-n], A364287 (where a(n) < n), A364292 (where a(n) <= n), A364494 (where n|a(n)), A364496 (where a(n)|n), A364963, A364297.
Cf. A365808 (positions of squares), A365801 (of cubes), A365802 (of fifth powers), A365805 [= A052409(a(n))], A366287, A366391.
Cf. A005940, A332214, A332817, A366275 (variants).

f[n_] := Reverse@ Map[Ceiling[(Length@ # - 1)/2] &, DeleteCases[Split@ Join[Riffle[IntegerDigits[n, 2], 0], {0}], {k__} /; k == 1]]; {1}~Join~
Table[Function[t, Prime[t] Product[Prime[m]^(f[n][[m]]), {m, t}]][DigitCount[n, 2, 1]], {n, 120}] (* Michael De Vlieger, Jul 25 2016 *)

from sympy import prime
def A163511(n):
    if n:
        k, c, m = n, 0, 1
        while k:
            c += 1
            m *= prime(c)**(s:=(~k&k-1).bit_length())
            k >>= s+1
        return m*prime(c)
    return 1 # Chai Wah Wu, Jul 17 2023

For n >= 1, a(2n) is even, a(2n+1) is odd. a(2^k) = 2^(k+1), for all k >= 0.
From Antti Karttunen, Jun 20 2014: (Start)
a(0) = 1, a(1) = 2, a(2n) = 2*a(n), a(2n+1) = A003961(a(n)).
As a more general observation about the parity, we have:
For n >= 1, A007814(a(n)) = A135523(n) = A007814(n) + A209229(n). [This permutation preserves the 2-adic valuation of n, except when n is a power of two, in which cases that value is incremented by one.]
For n >= 1, A055396(a(n)) = A091090(n) = A007814(n+1) + 1 - A036987(n).
For n >= 1, a(A000225(n)) = A000040(n).
(End)
From Antti Karttunen, Oct 11 2014: (Start)
As a composition of related permutations:
a(n) = A005940(1+A054429(n)).
a(n) = A064216(A245612(n))
a(n) = A246681(A246378(n)).
Also, for all n >= 0, it holds that:
A161511(n) = A243503(a(n)).
A243499(n) = A243504(a(n)).
(End)
More linking identities from Antti Karttunen, Dec 30 2017: (Start)
A046523(a(n)) = A278531(n). [See also A286531.]
A278224(a(n)) = A285713(n). [Another filter-sequence.]
A048675(a(n)) = A135529(n) seems to hold for n >= 1.
A250245(a(n)) = A252755(n).
A252742(a(n)) = A252744(n).
A245611(a(n)) = A253891(n).
A249824(a(n)) = A275716(n).
A292263(a(n)) = A292264(n). [A292944(n) + A292264(n) = n.]
--
A292383(a(n)) = A292274(n).
A292385(a(n)) = A292271(n). [A292271(n) +  A292274(n) = n.]
--
A292941(a(n)) = A292942(n).
A292943(a(n)) = A292944(n).
A292945(a(n)) = A292946(n). [A292942(n) + A292944(n) + A292946(n) = n.]
--
A292253(a(n)) = A292254(n).
A292255(a(n)) = A292256(n). [A292944(n) + A292254(n) + A292256(n) = n.]
--
A279339(a(n)) = A279342(n).
a(A071574(n)) = A269847(n).
a(A279341(n)) = A279338(n).
a(A252756(n)) = A250246(n).
(1+A008836(a(n)))/2 = A059448(n).
(End)
From Antti Karttunen, Jul 26 2023: (Start)
For all n >= 0, a(A007283(n)) = A007283(n).
A001222(a(n)) = A290251(n).
(End)

More terms computed and examples added by Antti Karttunen, Jun 20 2014

A036987 Fredholm-Rueppel sequence.

Original entry on oeis.org

1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 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, 1, 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, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 0

N. J. A. Sloane

Binary representation of the Kempner-Mahler number Sum_{k>=0} 1/2^(2^k) = A007404.
Also a(n) = A(n) mod 2 where A is any of A001700, A005573, A007854, A026641, A049027, A064063, A064088, A064090, A064092, A064325, A064327, A064329, A064331, A064613, A076026, A105523, A123273, A126694, A126930, A126931, A126982, A126983, A126987, A127016, A127053, A127358, A127360, A127361, A127363. - Philippe Deléham, May 26 2007
a(n) = (product of digits of n; n in binary notation) mod 2. This sequence is a transformation of the Thue-Morse sequence (A010060), since there exists a function f such that f(sum of digits of n) = (product of digits of n). - Ctibor O. Zizka, Feb 12 2008
a(n-1), n >= 1, the characteristic sequence for powers of 2, A000079, is the unique solution of the following formal product and formal power series identity: Product_{j>=1} (1 + a(j-1)*x^j) = 1 + Sum_{k>=1} x^k = 1/(1-x). The product is therefore Product_{l>=1} (1 + x^(2^l)). Proof. Compare coefficients of x^n and use the binary representation of n. Uniqueness follows from the recurrence relation given for the general case under A147542. - Wolfdieter Lang, Mar 05 2009
a(n) is also the number of orbits of length n for the map x -> 1-cx^2 on [-1,1] at the Feigenbaum critical value c=1.401155... . - Thomas Ward, Apr 08 2009
A054525 (Mobius transform) * A001511 = A036987 = A047999^(-1) * A001511 = the inverse of Sierpiński's gasket * the ruler sequence. - Gary W. Adamson, Oct 26 2009 [Of course this is only vaguely correct depending on how the fuzzy indexing in these formulas is made concrete. - R. J. Mathar, Jun 20 2014]
Characteristic function of A000225. - Reinhard Zumkeller, Mar 06 2012
Also parity of the Catalan numbers A000108. - Omar E. Pol, Jan 17 2012
For n >= 2, also the largest exponent k >= 0 such that n^k in binary notation does not contain both 0 and 1. Unlike for the decimal version of this sequence, A062518, where the terms are only conjectural, for this sequence the values of a(n) can be proved to be the characteristic function of A000225, as follows: n^k will contain both 0 and 1 unless n^k = 2^r-1 for some r. But this is a special case of Catalan's equation x^p = y^q-1, which was proved by Preda Mihăilescu to have no nontrivial solution except 2^3 = 3^2 - 1. - Christopher J. Smyth, Aug 22 2014
Image, under the coding a,b -> 1; c -> 0, of the fixed point, starting with a, of the morphism a -> ab, b -> cb, c -> cc. - Jeffrey Shallit, May 14 2016
Number of nonisomorphic Boolean algebras of order n+1. - Jianing Song, Jan 23 2020

			G.f. = 1 + x + x^3 + x^7 + x^15 + x^31 + x^63 + x^127 + x^255 + x^511 + ...
a(7) = 1 since 7 = 2^3 - 1, while a(10) = 0 since 10 is not of the form 2^k - 1 for any integer k.

Antti Karttunen, Table of n, a(n) for n = 0..65537
D. Bailey et al., On the binary expansions of algebraic numbers, Journal de Théorie des Nombres de Bordeaux 16 (2004), 487-518.
Paul Barry, Some observations on the Rueppel sequence and associated Hankel determinants, arXiv:2005.04066 [math.CO], 2020.
Paul Barry, Conjectures and results on some generalized Rueppel sequences, arXiv:2107.00442 [math.CO], 2021.
Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors of oligomorphic permutation groups, J. Integer Seqs., Vol. 6, 2003.
Mats Granvik, Mathematica program for computing Fredholm Rueppel sequences
D. Kohel, S. Ling and C. Xing, Explicit Sequence Expansions, in Sequences and their Applications, C. Ding, T. Helleseth, and H. Niederreiter, eds., Proceedings of SETA'98 (Singapore, 1998), 308-317, 1999.
Preda Mihăilescu, Primary Cyclotomic Units and a Proof of Catalan's Conjecture, J. Reine angew. Math. 572 (2004): 167-195. doi:10.1515/crll.2004.048. MR 2076124.
H. Niederreiter and M. Vielhaber, Tree Complexity and a Doubly Exponential Gap between Structured and Random Sequences, J. Complexity, 12 (1996), 187-198.
Apisit Pakapongpun and Thomas Ward, Functorial orbit counting, Journal of Integer Sequences, 12 (2009) Article 09.2.4. [From _Thomas Ward_, Apr 08 2009]
Eric Rowland and Reem Yassawi, Profinite automata, arXiv:1403.7659 [math.DS], 2014. See p. 8.
E. Sheppard, net.math post (1985)
Stephen Wolfram, [Page 1092] A New Kind of Science | Online.
Index entries for characteristic functions

Cf. A007404, A043545, A062518, A078885, A078585, A078886, A078887, A078888, A078889, A078890.
The first row of A073346. Occurs for first time in A073202 as row 6 (and again as row 8).
Congruent to any of the sequences A000108, A007460, A007461, A007463, A007464, A061922, A068068 reduced modulo 2. Characteristic function of A000225.
If interpreted with offset=1 instead of 0 (i.e., a(1)=1, a(2)=1, a(3)=0, a(4)=1, ...) then this is the characteristic function of 2^n (A000079) and as such occurs as the first row of A073265. Also, in that case the INVERT transform will produce A023359.
This is Guy Steele's sequence GS(1, 3), also GS(3, 1) (see A135416).
Cf. A054525, A047999. - Gary W. Adamson, Oct 26 2009
Cf. A043529, A127802.

a036987 n = ibp (n+1) where
   ibp 1 = 1
   ibp n = if r > 0 then 0 else ibp n' where (n',r) = divMod n 2
a036987_list = 1 : f [0,1] where f (x:y:xs) = y : f (x:xs ++ [x,x+y])
-- Same list generator function as for a091090_list, cf. A091090.
-- Reinhard Zumkeller, May 19 2015, Apr 13 2013, Mar 13 2013

A036987:= n-> `if`(2^ilog2(n+1) = n+1, 1, 0):
seq(A036987(n), n=0..128);

RealDigits[ N[ Sum[1/10^(2^n), {n, 0, Infinity}], 110]][[1]]
(* Recurrence: *)
t[n_, 1] = 1; t[1, k_] = 1;
t[n_, k_] := t[n, k] =
  If[n < k, If[n > 1 && k > 1, -Sum[t[k - i, n], {i, 1, n - 1}], 0],
   If[n > 1 && k > 1, Sum[t[n - i, k], {i, 1, k - 1}], 0]];
Table[t[n, k], {k, n, n}, {n, 104}]
(* Mats Granvik, Jun 03 2011 *)
mb2d[n_]:=1 - Module[{n2 = IntegerDigits[n, 2]}, Max[n2] - Min[n2]]; Array[mb2d, 120, 0] (* Vincenzo Librandi, Jul 19 2019 *)
Table[PadRight[{1},2^k,0],{k,0,7}]//Flatten (* Harvey P. Dale, Apr 23 2022 *)

{a(n) =( n++) == 2^valuation(n, 2)}; /* Michael Somos, Aug 25 2003 */

a(n) = !bitand(n, n+1); \\ Ruud H.G. van Tol, Apr 05 2023

from sympy import catalan
def a(n): return catalan(n)%2 # Indranil Ghosh, May 25 2017

def A036987(n): return int(not(n&(n+1))) # Chai Wah Wu, Jul 06 2022

1 followed by a string of 2^k - 1 0's. Also a(n)=1 iff n = 2^m - 1.
a(n) = a(floor(n/2)) * (n mod 2) for n>0 with a(0)=1. - Reinhard Zumkeller, Aug 02 2002 [Corrected by Mikhail Kurkov, Jul 16 2019]
Sum_{n>=0} 1/10^(2^n) = 0.110100010000000100000000000000010...
1 if n=0, floor(log_2(n+1)) - floor(log_2(n)) otherwise. G.f.: (1/x) * Sum_{k>=0} x^(2^k) = Sum_{k>=0} x^(2^k-1). - Ralf Stephan, Apr 28 2003
a(n) = 1 - A043545(n). - Michael Somos, Aug 25 2003
a(n) = -Sum_{d|n+1} mu(2*d). - Benoit Cloitre, Oct 24 2003
Dirichlet g.f. for right-shifted sequence: 2^(-s)/(1-2^(-s)).
a(n) = A000108(n) mod 2 = A001405(n) mod 2. - Paul Barry, Nov 22 2004
a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n,k)*Sum_{j=0..k} binomial(k, 2^j-1). - Paul Barry, Jun 01 2006
A000523(n+1) = Sum_{k=1..n} a(k). - Mitch Harris, Jul 22 2011
a(n) = A209229(n+1). - Reinhard Zumkeller, Mar 07 2012
a(n) = Sum_{k=1..n} A191898(n,k)*cos(Pi*(n-1)*(k-1))/n; (conjecture). - Mats Granvik, Mar 04 2013
a(n) = A000035(A000108(n)). - Omar E. Pol, Aug 06 2013
a(n) = 1 iff n=2^k-1 for some k, 0 otherwise. - M. F. Hasler, Jun 20 2014
a(n) = ceiling(log_2(n+2)) - ceiling(log_2(n+1)). - Gionata Neri, Sep 06 2015
From John M. Campbell, Jul 21 2016: (Start)
a(n) = (A000168(n-1) mod 2).
a(n) = (A000531(n+1) mod 2).
a(n) = (A000699(n+1) mod 2).
a(n) = (A000891(n) mod 2).
a(n) = (A000913(n-1) mod 2), for n>1.
a(n) = (A000917(n-1) mod 2), for n>0.
a(n) = (A001142(n) mod 2).
a(n) = (A001246(n) mod 2).
a(n) = (A001246(n) mod 4).
a(n) = (A002057(n-2) mod 2), for n>1.
a(n) = (A002430(n+1) mod 2). (End)
a(n) = 2 - A043529(n). - Antti Karttunen, Nov 19 2017
a(n) = floor(1+log(n+1)/log(2)) - floor(log(2n+1)/log(2)). - Adriano Caroli, Sep 22 2019
This is also the decimal expansion of -Sum_{k>=1} mu(2*k)/(10^k - 1), where mu is the Möbius function (A008683). - Amiram Eldar, Jul 12 2020

Edited by M. F. Hasler, Jun 20 2014

A225546 Tek's flip: Write n as the product of distinct factors of the form prime(i)^(2^(j-1)) with i and j integers, and replace each such factor with prime(j)^(2^(i-1)).

Original entry on oeis.org

1, 2, 4, 3, 16, 8, 256, 6, 9, 32, 65536, 12, 4294967296, 512, 64, 5, 18446744073709551616, 18, 340282366920938463463374607431768211456, 48, 1024, 131072, 115792089237316195423570985008687907853269984665640564039457584007913129639936, 24, 81, 8589934592, 36, 768

Offset: 1

Paul Tek, May 10 2013

This is a multiplicative self-inverse permutation of the integers.
A225547 gives the fixed points.
From Antti Karttunen and Peter Munn, Feb 02 2020: (Start)
This sequence operates on the Fermi-Dirac factors of a number. As arranged in array form, in A329050, this sequence reflects these factors about the main diagonal of the array, substituting A329050[j,i] for A329050[i,j], and this results in many relationships including significant homomorphisms.
This sequence provides a relationship between the operations of squaring and prime shift (A003961) because each successive column of the A329050 array is the square of the previous column, and each successive row is the prime shift of the previous row.
A329050 gives examples of how significant sets of numbers can be formed by choosing their factors in relation to rows and/or columns. This sequence therefore maps equivalent derived sets by exchanging rows and columns. Thus odd numbers are exchanged for squares, squarefree numbers for powers of 2 etc.
Alternative construction: For n > 1, form a vector v of length A299090(n), where each element v[i] for i=1..A299090(n) is a product of those distinct prime factors p(i) of n whose exponent e(i) has the bit (i-1) "on", or 1 (as an empty product) if no such exponents are present. a(n) is then Product_{i=1..A299090(n)} A000040(i)^A048675(v[i]). Note that because each element of vector v is squarefree, it means that each exponent A048675(v[i]) present in the product is a "submask" (not all necessarily proper) of the binary string A087207(n).
This permutation effects the following mappings:
A000035(a(n)) = A010052(n), A010052(a(n)) = A000035(n). [Odd numbers <-> Squares]
A008966(a(n)) = A209229(n), A209229(a(n)) = A008966(n). [Squarefree numbers <-> Powers of 2]
(End)
From Antti Karttunen, Jul 08 2020: (Start)
Moreover, we see also that this sequence maps between A016825 (Numbers of the form 4k+2) and A001105 (2*squares) as well as between A008586 (Multiples of 4) and A028983 (Numbers with even sum of the divisors).
(End)

			  7744  = prime(1)^2^(2-1)*prime(1)^2^(3-1)*prime(5)^2^(2-1).
a(7744) = prime(2)^2^(1-1)*prime(3)^2^(1-1)*prime(2)^2^(5-1) = 645700815.

Cf. A225547 (fixed points) and the subsequences listed there.
Transposes A329050, A329332.
An automorphism of positive integers under the binary operations A059895, A059896, A059897, A306697, A329329.
An automorphism of A059897 subgroups: A000379, A003159, A016754, A122132.
Permutes lists where membership is determined by number of Fermi-Dirac factors: A000028, A050376, A176525, A268388.
Also permutes: A036554, A059404, A066427, A066428, A072774, A331593.
Sequences f that satisfy f(a(n)) = f(n): A048675, A064179, A064547, A097248, A302777, A331592.
Pairs of sequences (f,g) that satisfy a(f(n)) = g(a(n)): (A000265,A008833), (A000290,A003961), (A005843,A334747), (A006519,A007913), (A008586,A334748).
Pairs of sequences (f,g) that satisfy a(f(n)) = g(n), possibly with offset change: (A000040,A001146), (A000079,A019565).
Pairs of sequences (f,g) that satisfy f(a(n)) = g(n), possibly with offset change: (A000035, A010052), (A008966, A209229), (A007814, A248663), (A061395, A299090), (A087207, A267116), (A225569, A227291).
Cf. A331287 [= gcd(a(n),n)].
Cf. A331288 [= min(a(n),n)], see also A331301.
Cf. A331309 [= A000005(a(n)), number of divisors].
Cf. A331590 [= a(a(n)*a(n))].
Cf. A331591 [= A001221(a(n)), number of distinct prime factors], see also A331593.
Cf. A331740 [= A001222(a(n)), number of prime factors with multiplicity].
Cf. A331733 [= A000203(a(n)), sum of divisors].
Cf. A331734 [= A033879(a(n)), deficiency].
Cf. A331735 [= A009194(a(n))].
Cf. A331736 [= A000265(a(n)) = a(A008833(n)), largest odd divisor].
Cf. A335914 [= A038040(a(n))].
A self-inverse isomorphism between pairs of A059897 subgroups: (A000079,A005117), (A000244,A062503), (A000290\{0},A005408), (A000302,A056911), (A000351,A113849 U {1}), (A000400,A062838), (A001651,A252895), (A003586,A046100), (A007310,A000583), (A011557,A113850 U {1}), (A028982,A042968), (A053165,A065331), (A262675,A268390).
A bijection between pairs of sets: (A001248,A011764), (A007283,A133466), (A016825, A001105), (A008586, A028983).
Cf. also A336321, A336322 (compositions with another involution, A122111).

Array[If[# == 1, 1, Times @@ Flatten@ Map[Function[{p, e}, Map[Prime[Log2@ # + 1]^(2^(PrimePi@ p - 1)) &, DeleteCases[NumberExpand[e, 2], 0]]] @@ # &, FactorInteger[#]]] &, 28] (* Michael De Vlieger, Jan 21 2020 *)

A019565(n) = factorback(vecextract(primes(logint(n+!n, 2)+1), n));
a(n) = {my(f=factor(n)); for (i=1, #f~, my(p=f[i,1]); f[i,1] = A019565(f[i,2]); f[i,2] = 2^(primepi(p)-1);); factorback(f);} \\ Michel Marcus, Nov 29 2019

A048675(n) = { my(f = factor(n)); sum(k=1, #f~, f[k, 2]*2^primepi(f[k, 1]))/2; };
A225546(n) = if(1==n,1,my(f=factor(n),u=#binary(vecmax(f[, 2])),prods=vector(u,x,1),m=1,e); for(i=1,u,for(k=1,#f~, if(bitand(f[k,2],m),prods[i] *= f[k,1])); m<<=1); prod(i=1,u,prime(i)^A048675(prods[i]))); \\ Antti Karttunen, Feb 02 2020

from math import prod
from sympy import prime, primepi, factorint
def A225546(n): return prod(prod(prime(i) for i, v in enumerate(bin(e)[:1:-1],1) if v == '1')**(1<Chai Wah Wu, Mar 17 2023

Multiplicative, with a(prime(i)^j) = A019565(j)^A000079(i-1).
a(prime(i)) = 2^(2^(i-1)).
From Antti Karttunen and Peter Munn, Feb 06 2020: (Start)
a(A329050(n,k)) = A329050(k,n).
a(A329332(n,k)) = A329332(k,n).
Equivalently, a(A019565(n)^k) = A019565(k)^n. If n = 1, this gives a(2^k) = A019565(k).
a(A059897(n,k)) = A059897(a(n), a(k)).
The previous formula implies a(n*k) = a(n) * a(k) if A059895(n,k) = 1.
a(A000040(n)) = A001146(n-1); a(A001146(n)) = A000040(n+1).
a(A000290(a(n))) = A003961(n); a(A003961(a(n))) = A000290(n) = n^2.
a(A000265(a(n))) = A008833(n); a(A008833(a(n))) = A000265(n).
a(A006519(a(n))) = A007913(n); a(A007913(a(n))) = A006519(n).
A007814(a(n)) = A248663(n); A248663(a(n)) = A007814(n).
A048675(a(n)) = A048675(n) and A048675(a(2^k * n)) = A048675(2^k * a(n)) = k + A048675(a(n)).
(End)
From Antti Karttunen and Peter Munn, Jul 08 2020: (Start)
For all n >= 1, a(2n) = A334747(a(n)).
In particular, for n = A003159(m), m >= 1, a(2n) = 2*a(n). [Note that A003159 includes all odd numbers]
(End)

Name edited by Peter Munn, Feb 14 2020

"Tek's flip" prepended to the name by Antti Karttunen, Jul 08 2020

A243071 Permutation of nonnegative integers: a(1) = 0, a(2) = 1, a(2n) = 2a(n), a(2n+1) = 1 + 2a(A064989(2n+1)).

Original entry on oeis.org

0, 1, 3, 2, 7, 6, 15, 4, 5, 14, 31, 12, 63, 30, 13, 8, 127, 10, 255, 28, 29, 62, 511, 24, 11, 126, 9, 60, 1023, 26, 2047, 16, 61, 254, 27, 20, 4095, 510, 125, 56, 8191, 58, 16383, 124, 25, 1022, 32767, 48, 23, 22, 253, 252, 65535, 18, 59, 120, 509, 2046, 131071

Offset: 1

Antti Karttunen, Jun 20 2014

nonn

Note the indexing: the domain starts from 1, while the range includes also zero.

See also the comments at A163511, which is the inverse permutation to this one.

Antti Karttunen, Table of n, a(n) for n = 1..1024
Index entries for sequences that are permutations of the natural numbers

Inverse: A163511.
Cf. A000040, A000225, A007814, A054429, A064989, A064216, A122111, A209229, A245611 (= (a(2n-1)-1)/2, for n > 1), A245612, A292383, A292385, A297171 (Möbius transform).
Cf. A007283 (known positions where a(n)=n), A364256 [= gcd(n,a(n))], A364288 [= n-a(n)], A364289 [where a(n)>=n], A364290 [where a(n)A364291 [where a(n)<=n], A364497 [where n|a(n)].
Cf. A156552 (variant with inverted binary code), A253566, A332215, A332811, A334859 (other variants).

A064989(n) = {my(f); f = factor(n); if((n>1 && f[1,1]==2), f[1,2] = 0); for (i=1, #f~, f[i,1] = precprime(f[i,1]-1)); factorback(f)};
A243071(n) = if(n<=2, n-1, if(!(n%2), 2*A243071(n/2), 1+(2*A243071(A064989(n))))); \\ Antti Karttunen, Jul 18 2020

A243071(n) = if(n<=2, n-1, my(f=factor(n), p, p2=1, res=0); for(i=1, #f~, p = 1 << (primepi(f[i, 1]) - 1); res += (p*p2*(2^(f[i, 2]) - 1)); p2 <<= f[i, 2]); ((3<<#binary(res\2))-res-1)); \\ (Combining programs given in A156552 and A054429) - Antti Karttunen, Jul 28 2023

from functools import reduce
from sympy import factorint, prevprime
from operator import mul
def a064989(n):
    f = factorint(n)
    return 1 if n==1 else reduce(mul, (1 if i==2 else prevprime(i)**f[i] for i in f))
def a(n): return n - 1 if n<3 else 2*a(n//2) if n%2==0 else 1 + 2*a(a064989(n))
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Jun 15 2017

;; With memoizing definec-macro from Antti Karttunen's IntSeq-library.
(definec (A243071 n) (cond ((<= n 2) (- n 1)) ((even? n) (* 2 (A243071 (/ n 2)))) (else (+ 1 (* 2 (A243071 (A064989 n)))))))

a(1) = 0, a(2) = 1, a(2n) = 2*a(n), a(2n+1) = 1 + 2*a(A064989(2n+1)).
For n >= 1, a(A000040(n)) = A000225(n).
For n >= 1, a(2n+1) = 1 + 2*a(A064216(n+1)).
From Antti Karttunen, Jul 18 2020: (Start)
a(n) = A245611(A048673(n)).
a(n) = A253566(A122111(n)).
a(n) = A334859(A225546(n)).
For n >= 2, a(n) = A054429(A156552(n)).
a(n) = A292383(n) + A292385(n) = A292383(n) OR A292385(n).
For n > 1, A007814(a(n)) = A007814(n) - A209229(n). [This map  preserves the 2-adic valuation of n, except when n is a power of two, in which cases it is decremented by one.]
(End)

A329697 a(n) is the number of iterations needed to reach a power of 2 starting at n and using the map k -> k-(k/p), where p is the largest prime factor of k.

Original entry on oeis.org

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

Offset: 1

Ali Sada and Robert G. Wilson v, Feb 28 2020

From Antti Karttunen, Apr 07 2020: (Start)
Also the least number of iterations of nondeterministic map k -> k-(k/p) needed to reach a power of 2, when any prime factor p of k can be used. The minimal length path to the nearest power of 2 (= 2^A064415(n)) is realized whenever one uses any of the A005087(k) distinct odd prime factors of the current k, at any step of the process. For example, this could be done by iterating with the map k -> k-(k/A078701(k)), i.e., by using the least odd prime factor of k (instead of the largest prime).
Proof: Viewing the prime factorization of changing k as a multiset ("bag") of primes, we see that liquefying any odd prime p with step p -> (p-1) brings at least one more 2 to the bag, while applying p -> (p-1) to any 2 just removes it from the bag, but gives nothing back. Thus the largest (and thus also the nearest) power of 2 is reached by eliminating - step by step - all odd primes from the bag, but none of 2's, and it doesn't matter in which order this is done.
The above implies also that the sequence is totally additive, which also follows because both A064097 and A064415 are. That A064097(n) = A329697(n) + A054725(n) for all n > 1 can be also seen by comparing the initial conditions and the recursion formulas of these three sequences.
For any n, A333787(n) is either the nearest power of 2 reached (= 2^A064415(n)), or occurs on some of the paths from n to there.
(End)
A003401 gives the numbers k where a(k) = A005087(k). See also A336477. - Antti Karttunen, Mar 16 2021

			The trajectory of 15 is {12, 8}, taking 2 iterations to reach 8 = 2^3. So a(15) is 2.
From _Antti Karttunen_, Apr 07 2020: (Start)
Considering all possible paths from 15 to 1 nondeterministic map k -> k-(k/p), where p can be any prime factor of k, we obtain the following graph:
        15
       / \
      /   \
    10     12
    / \   / \
   /   \ /   \
  5     8     6
   \__  |  __/|
      \_|_/   |
        4     3
         \   /
          \ /
           2
           |
           1.
It can be seen that there's also alternative route to 8 via 10 (with 10 = 15-(15/3), where 3 is not the largest prime factor of 15), but it's not any shorter than the route via 12.
(End)

Antti Karttunen, Table of n, a(n) for n = 1..65537
Michael De Vlieger, Annotated fan style binary tree labeling the index n, with a color code where black represents a(n) = 0, red a(n) = 1, and magenta the largest value in a(n) for n = 1..16383.

Cf. A000265, A003401, A005087, A052126, A053575, A054725, A064097, A064415, A078701, A087436, A147545, A171462, A209229, A333123, A333787, A333790, A334107, A334109, A335875, A334204, A335880, A335881, A336396, A336466, A336469 [= a(phi(n))], A336928 [= a(sigma(n))], A336470, A336477, A339970.
Cf. A000079, A334101, A334102, A334103, A334104, A334105, A334106 for positions of 0 .. 6 in this sequence, and also array A334100.
Cf. A334099 (a right inverse, positions of the first occurrence of each n).
Cf. A334091 (first differences), A335429 (partial sums).
Cf. also A331410 (analogous sequence when using the map k -> k + k/p), A334861, A335877 (their sums and differences), see also A335878 and A335884, A335885.

a[n_] := Length@ NestWhileList[# - #/FactorInteger[#][[-1, 1]] &, n, # != 2^IntegerExponent[#, 2] &] -1; Array[a, 100]

A329697(n) = if(!bitand(n,n-1),0,1+A329697(n-(n/vecmax(factor(n)[, 1])))); \\ Antti Karttunen, Apr 07 2020

up_to = 2^24;
A329697list(up_to) = { my(v=vector(up_to)); v[1] = 0; for(n=2, up_to, v[n] = if(!bitand(n,n-1),0,1+vecmin(apply(p -> v[n-n/p], factor(n)[, 1]~)))); (v); };
v329697 = A329697list(up_to);
A329697(n) = v329697[n]; \\ Antti Karttunen, Apr 07 2020

A329697(n) = if(n<=2,0, if(isprime(n), A329697(n-1)+1, my(f=factor(n)); (apply(A329697, f[, 1])~ * f[, 2]))); \\ Antti Karttunen, Apr 19 2020

From Antti Karttunen, Apr 07-19 2020: (Start)
a(1) = a(2) = 0; and for n > 2, a(p) = 1 + a(p-1) if p is an odd prime and a(n*m) = a(n) + a(m) if m,n > 1. [This is otherwise equal to the definition of A064097, except here we have a different initial condition, with a(2) = 0].
a(2n) = a(A000265(n)) = a(n).
a(p) = 1+a(p-1), for all odd primes p.
If A209229(n) == 1 [when n is a power of 2], a(n) = 0,
  otherwise a(n) = 1 + a(n-A052126(n)) = 1 + a(A171462(n)).
Equivalently, for non-powers of 2, a(n) = 1 + a(n-(n/A078701(n))),
or equivalently, for non-powers of 2, a(n) = 1 + Min a(n - n/p), for p prime and dividing n.
a(n) = A064097(n) - A064415(n), or equally, a(n) = A064097(n) - A054725(n), for n > 1.
a(A019434(n)) = 1, a(A334092(n)) = 2, a(A334093(n)) = 3, etc. for all applicable n.
For all n >= 0, a(A334099(n)) = a(A000244(n)) = a(A000351(n)) = a(A001026(n)) = a(257^n) = a(65537^n) = n.
a(A122111(n)) = A334107(n), a(A225546(n)) = A334109(n).
(End)
From Antti Karttunen, Mar 16 2021: (Start)
a(n) = a(A336466(n)) + A087436(n) = A336396(n) + A087436(n).
a(A053575(n)) = A336469(n) = a(n) - A005087(n).
a(A147545(n)) = A000120(A147545(n)) - 1.
(End)

Showing 1-10 of 191 results. Next

cp's OEIS Frontend

A135523 a(n) = A007814(n) + A209229(n).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Python

Formula

A000079 Powers of 2: a(n) = 2^n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Magma

Maple

Mathematica

Maxima

PARI

PARI

Python

Python

Scala

Scheme

Formula

Extensions

A001511 The ruler function: exponent of the highest power of 2 dividing 2n. Equivalently, the 2-adic valuation of 2n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Haskell

MATLAB

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Python

Python

Sage

Scheme

Formula

Extensions

A029837 Binary order of n: log_2(n) rounded up to next integer.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI