cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Previous Showing 11-20 of 120 results. Next

A363417 a(n) = Sum_{j=0..2^n - 1} b(j) for n >= 0 where b(n) = (A023416(n) + 1)*b(A053645(n)) + [A036987(n) = 0]*b(A266341(n)) for n > 0 with b(0) = 1.

Original entry on oeis.org

1, 2, 6, 23, 106, 566, 3415, 22872, 167796, 1334596, 11414192, 104270906, 1011793389, 10379989930, 112134625986, 1271209859403, 15077083642150, 186588381229340, 2403775013224000, 32168379148440968, 446341838086450308, 6410107231501731012, 95136428354649665256
Offset: 0

Views

Author

Mikhail Kurkov, Jun 11 2023 [verification needed]

Keywords

Comments

Note that [A036987(n) = 0]*b(A266341(n)) is the same as max((1 - T(n, j))*b(A053645(n) + 2^j*(1 - T(n, j))) | 0 <= j <= A000523(n)) where T(n, k) = floor(n/2^k) mod 2.
In fact b(n) is a generalization of A347205 just as A329369 is a generalization of A341392.

Crossrefs

Cf. A000523, A023416, A036987, A053645, A266341.
Similar recurrences: A284005, A329369, A341392, A347205.

Programs

  • PARI
    A063250(n)=my(L=logint(n, 2), A=0); for(i=0, L, my(B=n\2^(L-i)+1); A++; A-=logint(B, 2)==valuation(B, 2)); A
upto(n)=my(v, v1); v=vector(2^n, i, 0); v[1]=1; v1=vector(n+1, i, 0); v1[1]=1; for(i=1, #v-1, my(L=logint(i, 2), A=i - 2^L, B=A063250(i)); v[i+1]=(L - hammingweight(i) + 2)*v[A+1] + if(B>0, v[A + 2^(B-1) + 1])); for(i=1, n, v1[i+1]=v1[i] + sum(j=2^(i-1)+1, 2^i, v[j])); v1

A000225 a(n) = 2^n - 1. (Sometimes called Mersenne numbers, although that name is usually reserved for A001348.)

Original entry on oeis.org

0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823, 2147483647, 4294967295, 8589934591
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

This is the Gaussian binomial coefficient [n,1] for q=2.
Number of rank-1 matroids over S_n.
Numbers k such that the k-th central binomial coefficient is odd: A001405(k) mod 2 = 1. - Labos Elemer, Mar 12 2003
This gives the (zero-based) positions of odd terms in the following convolution sequences: A000108, A007460, A007461, A007463, A007464, A061922.
Also solutions (with minimum number of moves) for the problem of Benares Temple, i.e., three diamond needles with n discs ordered by decreasing size on the first needle to place in the same order on the third one, without ever moving more than one disc at a time and without ever placing one disc at the top of a smaller one. - Xavier Acloque, Oct 18 2003
a(0) = 0, a(1) = 1; a(n) = smallest number such that a(n)-a(m) == 0 (mod (n-m+1)), for all m. - Amarnath Murthy, Oct 23 2003
Binomial transform of [1, 1/2, 1/3, ...] = [1/1, 3/2, 7/3, ...]; (2^n - 1)/n, n=1,2,3, ... - Gary W. Adamson, Apr 28 2005
Numbers whose binary representation is 111...1. E.g., the 7th term is (2^7) - 1 = 127 = 1111111 (in base 2). - Alexandre Wajnberg, Jun 08 2005
Number of nonempty subsets of a set with n elements. - Michael Somos, Sep 03 2006
For n >= 2, a(n) is the least Fibonacci n-step number that is not a power of 2. - Rick L. Shepherd, Nov 19 2007
Let P(A) be the power set of an n-element set A. Then a(n+1) = the number of pairs of elements {x,y} of P(A) for which x and y are disjoint and for which either x is a subset of y or y is a subset of x. - Ross La Haye, Jan 10 2008
A simpler way to state this is that it is the number of pairs (x,y) where at least one of x and y is the empty set. - Franklin T. Adams-Watters, Oct 28 2011
2^n-1 is the sum of the elements in a Pascal triangle of depth n. - Brian Lewis (bsl04(AT)uark.edu), Feb 26 2008
Sequence generalized: a(n) = (A^n -1)/(A-1), n >= 1, A integer >= 2. This sequence has A=2; A003462 has A=3; A002450 has A=4; A003463 has A=5; A003464 has A=6; A023000 has A=7; A023001 has A=8; A002452 has A=9; A002275 has A=10; A016123 has A=11; A016125 has A=12; A091030 has A=13; A135519 has A=14; A135518 has A=15; A131865 has A=16; A091045 has A=17; A064108 has A=20. - Ctibor O. Zizka, Mar 03 2008
a(n) is also a Mersenne prime A000668 when n is a prime number in A000043. - Omar E. Pol, Aug 31 2008
a(n) is also a Mersenne number A001348 when n is prime. - Omar E. Pol, Sep 05 2008
With offset 1, = row sums of triangle A144081; and INVERT transform of A009545 starting with offset 1; where A009545 = expansion of sin(x)*exp(x). - Gary W. Adamson, Sep 10 2008
Numbers n such that A000120(n)/A070939(n) = 1. - Ctibor O. Zizka, Oct 15 2008
For n > 0, sequence is equal to partial sums of A000079; a(n) = A000203(A000079(n-1)). - Lekraj Beedassy, May 02 2009
Starting with offset 1 = the Jacobsthal sequence, A001045, (1, 1, 3, 5, 11, 21, ...) convolved with (1, 2, 2, 2, ...). - Gary W. Adamson, May 23 2009
Numbers n such that n=2*phi(n+1)-1. - Farideh Firoozbakht, Jul 23 2009
a(n) = (a(n-1)+1)-th odd numbers = A005408(a(n-1)) for n >= 1. - Jaroslav Krizek, Sep 11 2009
Partial sums of a(n) for n >= 0 are A000295(n+1). Partial sums of a(n) for n >= 1 are A000295(n+1) and A130103(n+1). a(n) = A006127(n) - (n+1). - Jaroslav Krizek, Oct 16 2009
If n is even a(n) mod 3 = 0. This follows from the congruences 2^(2k) - 1 ~ 2*2*...*2 - 1 ~ 4*4*...*4 - 1 ~ 1*1*...*1 - 1 ~ 0 (mod 3). (Note that 2*2*...*2 has an even number of terms.) - Washington Bomfim, Oct 31 2009
Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=2,(i>1), A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n >= 1, a(n)=det(A). - Milan Janjic, Jan 26 2010
This is the sequence A(0,1;1,2;2) = A(0,1;3,-2;0) of the family of sequences [a,b:c,d:k] considered by G. Detlefs, and treated as A(a,b;c,d;k) in the W. Lang link given below. - Wolfdieter Lang, Oct 18 2010
a(n) = S(n+1,2), a Stirling number of the second kind. See the example below. - Dennis P. Walsh, Mar 29 2011
Entries of row a(n) in Pascal's triangle are all odd, while entries of row a(n)-1 have alternating parities of the form odd, even, odd, even, ..., odd.
Define the bar operation as an operation on signed permutations that flips the sign of each entry. Then a(n+1) is the number of signed permutations of length 2n that are equal to the bar of their reverse-complements and avoid the set of patterns {(-2,-1), (-1,+2), (+2,+1)}. (See the Hardt and Troyka reference.) - Justin M. Troyka, Aug 13 2011
A159780(a(n)) = n and A159780(m) < n for m < a(n). - Reinhard Zumkeller, Oct 21 2011
This sequence is also the number of proper subsets of a set with n elements. - Mohammad K. Azarian, Oct 27 2011
a(n) is the number k such that the number of iterations of the map k -> (3k +1)/2 == 1 (mod 2) until reaching (3k +1)/2 == 0 (mod 2) equals n. (see the Collatz problem). - Michel Lagneau, Jan 18 2012
For integers a, b, denote by a<+>b the least c >= a such that Hd(a,c) = b (note that, generally speaking, a<+>b differs from b<+>a). Then a(n+1)=a(n)<+>1. Thus this sequence is the Hamming analog of nonnegative integers. - Vladimir Shevelev, Feb 13 2012
Pisano period lengths: 1, 1, 2, 1, 4, 2, 3, 1, 6, 4, 10, 2, 12, 3, 4, 1, 8, 6, 18, 4, ... apparently A007733. - R. J. Mathar, Aug 10 2012
Start with n. Each n generates a sublist {n-1,n-2,...,1}. Each element of each sublist also generates a sublist. Take the sum of all. E.g., 3->{2,1} and 2->{1}, so a(3)=3+2+1+1=7. - Jon Perry, Sep 02 2012
This is the Lucas U(P=3,Q=2) sequence. - R. J. Mathar, Oct 24 2012
The Mersenne numbers >= 7 are all Brazilian numbers, as repunits in base two. See Proposition 1 & 5.2 in Links: "Les nombres brésiliens". - Bernard Schott, Dec 26 2012
Number of line segments after n-th stage in the H tree. - Omar E. Pol, Feb 16 2013
Row sums of triangle in A162741. - Reinhard Zumkeller, Jul 16 2013
a(n) is the highest power of 2 such that 2^a(n) divides (2^n)!. - Ivan N. Ianakiev, Aug 17 2013
In computer programming, these are the only unsigned numbers such that k&(k+1)=0, where & is the bitwise AND operator and numbers are expressed in binary. - Stanislav Sykora, Nov 29 2013
Minimal number of moves needed to interchange n frogs in the frogs problem (see for example the NRICH 1246 link or the Britton link below). - N. J. A. Sloane, Jan 04 2014
a(n) !== 4 (mod 5); a(n) !== 10 (mod 11); a(n) !== 2, 4, 5, 6 (mod 7). - Carmine Suriano, Apr 06 2014
After 0, antidiagonal sums of the array formed by partial sums of integers (1, 2, 3, 4, ...). - Luciano Ancora, Apr 24 2015
a(n+1) equals the number of ternary words of length n avoiding 01,02. - Milan Janjic, Dec 16 2015
With offset 0 and another initial 0, the n-th term of 0, 0, 1, 3, 7, 15, ... is the number of commas required in the fully-expanded von Neumann definition of the ordinal number n. For example, 4 := {0, 1, 2, 3} := {{}, {{}}, {{}, {{}}}, {{}, {{}}, {{}, {{}}}}}, which uses seven commas. Also, for n>0, a(n) is the total number of symbols required in the fully-expanded von Neumann definition of ordinal n - 1, where a single symbol (as usual) is always used to represent the empty set and spaces are ignored. E.g., a(5) = 31, the total such symbols for the ordinal 4. - Rick L. Shepherd, May 07 2016
With the quantum integers defined by [n+1]A001045%20are%20given%20by%20q%20=%20i%20*%20sqrt(2)%20for%20i%5E2%20=%20-1.%20Cf.%20A239473.%20-%20_Tom%20Copeland">q = (q^(n+1) - q^(-n-1)) / (q - q^(-1)), the Mersenne numbers are a(n+1) = q^n [n+1]_q with q = sqrt(2), whereas the signed Jacobsthal numbers A001045 are given by q = i * sqrt(2) for i^2 = -1. Cf. A239473. - _Tom Copeland, Sep 05 2016
For n>1: numbers n such that n - 1 divides sigma(n + 1). - Juri-Stepan Gerasimov, Oct 08 2016
This is also the second column of the Stirling2 triangle A008277 (see also A048993). - Wolfdieter Lang, Feb 21 2017
Except for the initial terms, the decimal representation of the x-axis of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 659", "Rule 721" and "Rule 734", based on the 5-celled von Neumann neighborhood initialized with a single on cell. - Robert Price, Mar 14 2017
a(n), n > 1, is the number of maximal subsemigroups of the monoid of order-preserving partial injective mappings on a set with n elements. - James Mitchell and Wilf A. Wilson, Jul 21 2017
Also the number of independent vertex sets and vertex covers in the complete bipartite graph K_{n-1,n-1}. - Eric W. Weisstein, Sep 21 2017
Sum_{k=0..n} p^k is the determinant of n X n matrix M_(i, j) = binomial(i + j - 1, j)*p + binomial(i+j-1, i), in this case p=2 (empirical observation). - Tony Foster III, May 11 2019
The rational numbers r(n) = a(n+1)/2^(n+1) = a(n+1)/A000079(n+1) appear also as root of the n-th iteration f^{[n]}(c; x) = 2^(n+1)*x - a(n+1)*c of f(c; x) = f^{[0]}(c; x) = 2*x - c as r(n)*c. This entry is motivated by a riddle of Johann Peter Hebel (1760 - 1826): Erstes Rechnungsexempel(Ein merkwürdiges Rechnungs-Exempel) from 1803, with c = 24 and n = 2, leading to the root r(2)*24 = 21 as solution. See the link and reference. For the second problem, also involving the present sequence, see a comment in A130330. - Wolfdieter Lang, Oct 28 2019
a(n) is the sum of the smallest elements of all subsets of {1,2,..,n} that contain n. For example, a(3)=7; the subsets of {1,2,3} that contain 3 are {3}, {1,3}, {2,3}, {1,2,3}, and the sum of smallest elements is 7. - Enrique Navarrete, Aug 21 2020
a(n-1) is the number of nonempty subsets of {1,2,..,n} which don't have an element that is the size of the set. For example, for n = 4, a(3) = 7 and the subsets are {2}, {3}, {4}, {1,3}, {1,4}, {3,4}, {1,2,4}. - Enrique Navarrete, Nov 21 2020
From Eric W. Weisstein, Sep 04 2021: (Start)
Also the number of dominating sets in the complete graph K_n.
Also the number of minimum dominating sets in the n-helm graph for n >= 3. (End)
Conjecture: except for a(2)=3, numbers m such that 2^(m+1) - 2^j - 2^k - 1 is composite for all 0 <= j < k <= m. - Chai Wah Wu, Sep 08 2021
a(n) is the number of three-in-a-rows passing through a corner cell in n-dimensional tic-tac-toe. - Ben Orlin, Mar 15 2022
From Vladimir Pletser, Jan 27 2023: (Start)
a(n) == 1 (mod 30) for n == 1 (mod 4);
a(n) == 7 (mod 120) for n == 3 (mod 4);
(a(n) - 1)/30 = (a(n+2) - 7)/120 for n odd;
(a(n) - 1)/30 = (a(n+2) - 7)/120 = A131865(m) for n == 1 (mod 4) and m >= 0 with A131865(0) = 0. (End)
a(n) is the number of n-digit numbers whose smallest decimal digit is 8. - Stefano Spezia, Nov 15 2023
Also, number of nodes in a perfect binary tree of height n-1, or: number of squares (or triangles) after the n-th step of the construction of a Pythagorean tree: Start with a segment. At each step, construct squares having the most recent segment(s) as base, and isosceles right triangles having the opposite side of the squares as hypotenuse ("on top" of each square). The legs of these triangles will serve as the segments which are the bases of the squares in the next step. - M. F. Hasler, Mar 11 2024
a(n) is the length of the longest path in the n-dimensional hypercube. - Christian Barrientos, Apr 13 2024
a(n) is the diameter of the n-Hanoi graph. Equivalently, a(n) is the largest minimum number of moves between any two states of the Towers of Hanoi problem (aka problem of Benares Temple described above). - Allan Bickle, Aug 09 2024

Examples

			For n=3, a(3)=S(4,2)=7, a Stirling number of the second kind, since there are 7 ways to partition {a,b,c,d} into 2 nonempty subsets, namely,
  {a}U{b,c,d}, {b}U{a,c,d}, {c}U{a,b,d}, {d}U{a,b,c}, {a,b}U{c,d}, {a,c}U{b,d}, and {a,d}U{b,c}. - _Dennis P. Walsh_, Mar 29 2011
From _Justin M. Troyka_, Aug 13 2011: (Start)
Since a(3) = 7, there are 7 signed permutations of 4 that are equal to the bar of their reverse-complements and avoid {(-2,-1), (-1,+2), (+2,+1)}. These are:
  (+1,+2,-3,-4),
  (+1,+3,-2,-4),
  (+1,-3,+2,-4),
  (+2,+4,-1,-3),
  (+3,+4,-1,-2),
  (-3,+1,-4,+2),
  (-3,-4,+1,+2). (End)
G.f. = x + 3*x^2 + 7*x^3 + 15*x^4 + 31*x^5 + 63*x^6 + 127*x^7 + ...
For the Towers of Hanoi problem with 2 disks, the moves are as follows, so a(2) = 3.
12|_|_ -> 2|1|_ -> _|1|2 -> _|_|12  - _Allan Bickle_, Aug 07 2024

References

  • P. Bachmann, Niedere Zahlentheorie (1902, 1910), reprinted Chelsea, NY, 1968, vol. 2, p. 75.
  • Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, Fifth Edition, Addison-Wesley, 2004, p. 134.
  • Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §3.2 Prime Numbers, p. 79.
  • Johann Peter Hebel, Gesammelte Werke in sechs Bänden, Herausgeber: Jan Knopf, Franz Littmann und Hansgeorg Schmidt-Bergmann unter Mitarbeit von Ester Stern, Wallstein Verlag, 2019. Band 3, S. 20-21, Loesung, S. 36-37. See also the link below.
  • Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See pp. 46, 60, 75-83.
  • 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).
  • James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 141.
  • D. Wells, The Penguin Dictionary of Curious and Interesting Numbers, "Tower of Hanoi", Penguin Books, 1987, pp. 112-113.

Links

Crossrefs

Cf. A000043 (Mersenne exponents).
Cf. A000668 (Mersenne primes).
Cf. A001348 (Mersenne numbers with n prime).
Cf. A000079, A001045, A009545, A016189, A052955, A083329, A085104, A144081.
Cf. a(n)=A112492(n, 2). Rightmost column of A008969.
a(n) = A118654(n, 1) = A118654(n-1, 3), for n > 0.
Subsequence of A132781.
Smallest number whose base b sum of digits is n: this sequence (b=2), A062318 (b=3), A180516 (b=4), A181287 (b=5), A181288 (b=6), A181303 (b=7), A165804 (b=8), A140576 (b=9), A051885 (b=10).
Cf. A000203, A239473, A279396.
Cf. A008277, A048993 (columns k=2), A000918, A130330.
Cf. A000225, A029858, A058809, A375256 (Hanoi graphs).

Programs

  • Haskell
    a000225 = (subtract 1) . (2 ^)
a000225_list = iterate ((+ 1) . (* 2)) 0
-- Reinhard Zumkeller, Mar 20 2012
  • Maple
    A000225 := n->2^n-1; [ seq(2^n-1,n=0..50) ];
A000225:=1/(2*z-1)/(z-1); # Simon Plouffe in his 1992 dissertation, sequence starting at a(1)
  • Mathematica
    a[n_] := 2^n - 1; Table[a[n], {n, 0, 30}] (* Stefan Steinerberger, Mar 30 2006 *)
Array[2^# - 1 &, 50, 0] (* Joseph Biberstine (jrbibers(AT)indiana.edu), Dec 26 2006 *)
NestList[2 # + 1 &, 0, 32] (* Robert G. Wilson v, Feb 28 2011 *)
2^Range[0, 20] - 1 (* Eric W. Weisstein, Jul 17 2017 *)
LinearRecurrence[{3, -2}, {1, 3}, 20] (* Eric W. Weisstein, Sep 21 2017 *)
CoefficientList[Series[1/(1 - 3 x + 2 x^2), {x, 0, 20}], x] (* Eric W. Weisstein, Sep 21 2017 *)
  • PARI
    A000225(n) = 2^n-1  \\ Michael B. Porter, Oct 27 2009
  • PARI
    concat(0, Vec(x/((1-2*x)*(1-x)) + O(x^100))) \\ Altug Alkan, Oct 28 2015
  • Python
    def A000225(n): return (1<Chai Wah Wu, Jul 06 2022
  • SageMath
    def isMersenne(n): return n == sum([(1 - b) << s for (s, b) in enumerate((n+1).bits())]) # Peter Luschny, Sep 01 2019

Formula

G.f.: x/((1-2*x)*(1-x)).
E.g.f.: exp(2*x) - exp(x).
E.g.f. if offset 1: ((exp(x)-1)^2)/2.
a(n) = Sum_{k=0..n-1} 2^k. - Paul Barry, May 26 2003
a(n) = a(n-1) + 2*a(n-2) + 2, a(0)=0, a(1)=1. - Paul Barry, Jun 06 2003
Let b(n) = (-1)^(n-1)*a(n). Then b(n) = Sum_{i=1..n} i!*i*Stirling2(n,i)*(-1)^(i-1). E.g.f. of b(n): (exp(x)-1)/exp(2x). - Mario Catalani (mario.catalani(AT)unito.it), Dec 19 2003
a(n+1) = 2*a(n) + 1, a(0) = 0.
a(n) = Sum_{k=1..n} binomial(n, k).
a(n) = n + Sum_{i=0..n-1} a(i); a(0) = 0. - Rick L. Shepherd, Aug 04 2004
a(n+1) = (n+1)*Sum_{k=0..n} binomial(n, k)/(k+1). - Paul Barry, Aug 06 2004
a(n+1) = Sum_{k=0..n} binomial(n+1, k+1). - Paul Barry, Aug 23 2004
Inverse binomial transform of A001047. Also U sequence of Lucas sequence L(3, 2). - Ross La Haye, Feb 07 2005
a(n) = A099393(n-1) - A020522(n-1) for n > 0. - Reinhard Zumkeller, Feb 07 2006
a(n) = A119258(n,n-1) for n > 0. - Reinhard Zumkeller, May 11 2006
a(n) = 3*a(n-1) - 2*a(n-2); a(0)=0, a(1)=1. - Lekraj Beedassy, Jun 07 2006
Sum_{n>0} 1/a(n) = 1.606695152... = A065442, see A038631. - Philippe Deléham, Jun 27 2006
Stirling_2(n-k,2) starting from n=k+1. - Artur Jasinski, Nov 18 2006
a(n) = A125118(n,1) for n > 0. - Reinhard Zumkeller, Nov 21 2006
a(n) = StirlingS2(n+1,2). - Ross La Haye, Jan 10 2008
a(n) = A024036(n)/A000051(n). - Reinhard Zumkeller, Feb 14 2009
a(n) = A024088(n)/A001576(n). -Reinhard Zumkeller, Feb 15 2009
a(2*n) = a(n)*A000051(n); a(n) = A173787(n,0). - Reinhard Zumkeller, Feb 28 2010
For n > 0: A179857(a(n)) = A024036(n) and A179857(m) < A024036(n) for m < a(n). - Reinhard Zumkeller, Jul 31 2010
From Enrique Pérez Herrero, Aug 21 2010: (Start)
a(n) = J_n(2), where J_n is the n-th Jordan Totient function: (A007434, is J_2).
a(n) = Sum_{d|2} d^n*mu(2/d). (End)
A036987(a(n)) = 1. - Reinhard Zumkeller, Mar 06 2012
a(n+1) = A044432(n) + A182028(n). - Reinhard Zumkeller, Apr 07 2012
a(n) = A007283(n)/3 - 1. - Martin Ettl, Nov 11 2012
a(n+1) = A001317(n) + A219843(n); A219843(a(n)) = 0. - Reinhard Zumkeller, Nov 30 2012
a(n) = det(|s(i+2,j+1)|, 1 <= i,j <= n-1), where s(n,k) are Stirling numbers of the first kind. - Mircea Merca, Apr 06 2013
G.f.: Q(0), where Q(k) = 1 - 1/(4^k - 2*x*16^k/(2*x*4^k - 1/(1 - 1/(2*4^k - 8*x*16^k/(4*x*4^k - 1/Q(k+1)))))); (continued fraction). - Sergei N. Gladkovskii, May 22 2013
E.g.f.: Q(0), where Q(k) = 1 - 1/(2^k - 2*x*4^k/(2*x*2^k - (k+1)/Q(k+1))); (continued fraction).
G.f.: Q(0), where Q(k) = 1 - 1/(2^k - 2*x*4^k/(2*x*2^k - 1/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 23 2013
a(n) = A000203(2^(n-1)), n >= 1. - Ivan N. Ianakiev, Aug 17 2013
a(n) = Sum_{t_1+2*t_2+...+n*t_n=n} n*multinomial(t_1+t_2 +...+t_n,t_1,t_2,...,t_n)/(t_1+t_2 +...+t_n). - Mircea Merca, Dec 06 2013
a(0) = 0; a(n) = a(n-1) + 2^(n-1) for n >= 1. - Fred Daniel Kline, Feb 09 2014
a(n) = A125128(n) - A000325(n) + 1. - Miquel Cerda, Aug 07 2016
From Ilya Gutkovskiy, Aug 07 2016: (Start)
Binomial transform of A057427.
Sum_{n>=0} a(n)/n! = A090142. (End)
a(n) = A000918(n) + 1. - Miquel Cerda, Aug 09 2016
a(n+1) = (A095151(n+1) - A125128(n))/2. - Miquel Cerda, Aug 12 2016
a(n) = (A079583(n) - A000325(n+1))/2. - Miquel Cerda, Aug 15 2016
Convolution of binomial coefficient C(n,a(k)) with itself is C(n,a(k+1)) for all k >= 3. - Anton Zakharov, Sep 05 2016
a(n) = (A083706(n-1) + A000325(n))/2. - Miquel Cerda, Sep 30 2016
a(n) = A005803(n) + A005408(n-1). - Miquel Cerda, Nov 25 2016
a(n) = A279396(n+2,2). - Wolfdieter Lang, Jan 10 2017
a(n) = n + Sum_{j=1..n-1} (n-j)*2^(j-1). See a Jun 14 2017 formula for A000918(n+1) with an interpretation. - Wolfdieter Lang, Jun 14 2017
a(n) = Sum_{k=0..n-1} Sum_{i=0..n-1} C(k,i). - Wesley Ivan Hurt, Sep 21 2017
a(n+m) = a(n)*a(m) + a(n) + a(m). - Yuchun Ji, Jul 27 2018
a(n+m) = a(n+1)*a(m) - 2*a(n)*a(m-1). - Taras Goy, Dec 23 2018
a(n+1) is the determinant of n X n matrix M_(i, j) = binomial(i + j - 1, j)*2 + binomial(i+j-1, i) (empirical observation). - Tony Foster III, May 11 2019
From Peter Bala, Jun 27 2025: (Start)
For n >= 1, a(3*n)/a(n) = A001576(n), a(4*n)/a(n) = A034496(n), a(5*n)/a(n) = A020514(n) a(6*n)/a(n) = A034665(n), a(7*n)/a(n) = A020516(n) and a(8*n)/a(n) = A034674(n).
exp( Sum_{n >= 1} a(2*n)/a(n)*x^n/n ) = Sum_{n >= 0} a(n+1)*x^n.
Modulo differences in offsets, exp( Sum_{n >= 1} a(k*n)/a(n)*x^n/n ) is the o.g.f. of A006095 (k = 3), A006096 (k = 4), A006097 (k = 5), A006110 (k = 6), A022189 (k = 7), A022190 (k = 8), A022191 (k = 9) and A022192 (k = 10).
The following are all examples of telescoping series:
Sum_{n >= 1} 2^n/(a(n)*a(n+1)) = 1; Sum_{n >= 1} 2^n/(a(n)*a(n+1)*a(n+2)) = 1/9.
In general, for k >= 1, Sum_{n >= 1} 2^n/(a(n)*a(n+1)*...*a(n+k)) = 1/(a(1)*a(2)*...*a(k)*a(k)).
Sum_{n >= 1} 2^n/(a(n)*a(n+2)) = 4/9, since 2^n/(a(n)*a(n+2)) = b(n) - b(n+1), where b(n) = (2/3)*(3*2^(n-1) - 1)/((2^(n+1) - 1)*(2^n - 1)).
Sum_{n >= 1} (-2)^n/(a(n)*a(n+2)) = -2/9, since (-2)^n/(a(n)*a(n+2)) = c(n) - c(n+1), where c(n) = (1/3)*(-2)^n/((2^(n+1) - 1)*(2^n - 1)).
Sum_{n >= 1} 2^n/(a(n)*a(n+4)) = 18/175, since 2^n/(a(n)*a(n+4)) = d(n) - d(n+1), where d(n) = (120*8^n - 140*4^n + 45*2^n - 4)/(15*(2^n - 1)*(2^(n+1) - 1)*(2^(n+2) - 1)*(2^(n+3) - 1)).
Sum_{n >= 1} (-2)^n/(a(n)*a(n+4)) = -26/525, since (-2)^n/(a(n)*a(n+4)) = e(n) - e(n+1), where e(n) = (-1)^n*(40*8^n - 24*4^n + 5*2^n)/(15*(2^n - 1)*(2^(n+1) - 1)*(2^(n+2) - 1)*(2^(n+3) - 1)). (End)

Extensions

Name partially edited by Eric W. Weisstein, Sep 04 2021

A007814 Exponent of highest power of 2 dividing n, a.k.a. the binary carry sequence, the ruler sequence, or the 2-adic valuation of n.

Original entry on oeis.org

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

Views

Author

John Tromp, Dec 11 1996

Keywords

Comments

This sequence is an exception to my usual rule that when every other term of a sequence is 0 then those 0's should be omitted. In this case we would get A001511. - N. J. A. Sloane
To construct the sequence: start with 0,1, concatenate to get 0,1,0,1. Add + 1 to last term gives 0,1,0,2. Concatenate those 4 terms to get 0,1,0,2,0,1,0,2. Add + 1 to last term etc. - Benoit Cloitre, Mar 06 2003
The sequence is invariant under the following two transformations: increment every element by one (1, 2, 1, 3, 1, 2, 1, 4, ...), put a zero in front and between adjacent elements (0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, ...). The intermediate result is A001511. - Ralf Hinze (ralf(AT)informatik.uni-bonn.de), Aug 26 2003
Fixed point of the morphism 0->01, 1->02, 2->03, 3->04, ..., n->0(n+1), ..., starting from a(1) = 0. - Philippe Deléham, Mar 15 2004
Fixed point of the morphism 0->010, 1->2, 2->3, ..., n->(n+1), .... - Joerg Arndt, Apr 29 2014
a(n) is also the number of times to repeat a step on an even number in the hailstone sequence referenced in the Collatz conjecture. - Alex T. Flood (whiteangelsgrace(AT)gmail.com), Sep 22 2006
Let F(n) be the n-th Fermat number (A000215). Then F(a(r-1)) divides F(n)+2^k for r = k mod 2^n and r != 1. - T. D. Noe, Jul 12 2007
The following relation holds: 2^A007814(n)*(2*A025480(n-1)+1) = A001477(n) = n. (See functions hd, tl and cons in [Paul Tarau 2009].)
a(n) is the number of 0's at the end of n when n is written in base 2.
a(n+1) is the number of 1's at the end of n when n is written in base 2. - M. F. Hasler, Aug 25 2012
Shows which bit to flip when creating the binary reflected Gray code (bits are numbered from the right, offset is 0). That is, A003188(n) XOR A003188(n+1) == 2^A007814(n). - Russ Cox, Dec 04 2010
The sequence is squarefree (in the sense of not containing any subsequence of the form XX) [Allouche and Shallit]. Of course it contains individual terms that are squares (such as 4). - Comment expanded by N. J. A. Sloane, Jan 28 2019
a(n) is the number of zero coefficients in the n-th Stern polynomial, A125184. - T. D. Noe, Mar 01 2011
Lemma: For n < m with r = a(n) = a(m) there exists n < k < m with a(k) > r. Proof: We have n=b2^r and m=c2^r with b < c both odd; choose an even i between them; now a(i2^r) > r and n < i2^r < m. QED. Corollary: Every finite run of consecutive integers has a unique maximum 2-adic valuation. - Jason Kimberley, Sep 09 2011
a(n-2) is the 2-adic valuation of A000166(n) for n >= 2. - Joerg Arndt, Sep 06 2014
a(n) = number of 1's in the partition having Heinz number n. We define the Heinz number of a partition p = [p_1, p_2, ..., p_r] as Product_{j=1..r} p_j-th prime (concept used by Alois P. Heinz in A215366 as an "encoding" of a partition). For example, for the partition [1, 1, 2, 4, 10] we get 2*2*3*7*29 = 2436. Example: a(24)=3; indeed, the partition having Heinz number 24 = 2*2*2*3 is [1,1,1,2]. - Emeric Deutsch, Jun 04 2015
a(n+1) is the difference between the two largest parts in the integer partition having viabin number n (0 is assumed to be a part). Example: a(20) = 2. Indeed, we have 19 = 10011_2, leading to the Ferrers board of the partition [3,1,1]. For the definition of viabin number see the comment in A290253. - Emeric Deutsch, Aug 24 2017
Apart from being squarefree, as noted above, the sequence has the property that every consecutive subsequence contains at least one number an odd number of times. - Jon Richfield, Dec 20 2018
a(n+1) is the 2-adic valuation of Sum_{e=0..n} u^e = (1 + u + u^2 + ... + u^n), for any u of the form 4k+1 (A016813). - Antti Karttunen, Aug 15 2020
{a(n)} represents the "first black hat" strategy for the game of countably infinitely many hats, with a probability of success of 1/3; cf. the Numberphile link below. - Frederic Ruget, Jun 14 2021
a(n) is the least nonnegative 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

Examples

			2^3 divides 24, so a(24)=3.
From _Omar E. Pol_, Jun 12 2009: (Start)
Triangle begins:
  0;
  1,0;
  2,0,1,0;
  3,0,1,0,2,0,1,0;
  4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0;
  5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0;
  6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,...
(End)

References

  • J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 27.
  • K. Atanassov, On the 37th and the 38th Smarandache Problems, Notes on Number Theory and Discrete Mathematics, Sophia, Bulgaria, Vol. 5 (1999), No. 2, 83-85.
  • Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.

Links

Crossrefs

Cf. A011371 (partial sums), A094267 (first differences), A001511 (bisection), A346070 (mod 4).
Bisection of A050605 and |A088705|. Pairwise sums are A050603 and A136480. Difference of A285406 and A281264.
This is Guy Steele's sequence GS(1, 4) (see A135416). Cf. A053398(1,n). Column/row 1 of table A050602.
Cf. A007949 (3-adic), A235127 (4-adic), A112765 (5-adic), A122841 (6-adic), A214411 (7-adic), A244413 (8-adic), A122840 (10-adic).
Cf. A000079, A002487, A006519, A051064, A055457, A063787, A215366, A220466.
Cf. A086463 (Dgf at s=2).

Programs

  • Haskell
    a007814 n = if m == 0 then 1 + a007814 n' else 0
            where (n', m) = divMod n 2
-- Reinhard Zumkeller, Jul 05 2013, May 14 2011, Apr 08 2011
  • Haskell
    a007814 n | odd n = 0 | otherwise = 1 + a007814 (n `div` 2)
--  Walt Rorie-Baety, Mar 22 2013
  • Magma
    [Valuation(n, 2): n in [1..120]]; // Bruno Berselli, Aug 05 2013
  • Maple
    ord := proc(n) local i,j; if n=0 then return 0; fi; i:=0; j:=n; while j mod 2 <> 1 do i:=i+1; j:=j/2; od: i; end proc: seq(ord(n), n=1..111);
A007814 := n -> padic[ordp](n,2): seq(A007814(n), n=1..111); # Peter Luschny, Nov 26 2010
  • Mathematica
    Table[IntegerExponent[n, 2], {n, 64}] (* Eric W. Weisstein *)
IntegerExponent[Range[64], 2] (* Eric W. Weisstein, Feb 01 2024 *)
p=2; Array[ If[ Mod[ #, p ]==0, Select[ FactorInteger[ # ], Function[ q, q[ [ 1 ] ]==p ], 1 ][ [ 1, 2 ] ], 0 ]&, 96 ]
DigitCount[BitXor[x, x - 1], 2, 1] - 1; a different version based on the same concept: Floor[Log[2, BitXor[x, x - 1]]] (* Jaume Simon Gispert (jaume(AT)nuem.com), Aug 29 2004 *)
Nest[Join[ #, ReplacePart[ #, Length[ # ] -> Last[ # ] + 1]] &, {0, 1}, 5] (* N. J. Gunther, May 23 2009 *)
Nest[ Flatten[# /. a_Integer -> {0, a + 1}] &, {0}, 7] (* Robert G. Wilson v, Jan 17 2011 *)
  • PARI
    A007814(n)=valuation(n,2);
  • Python
    import math
def a(n): return int(math.log(n - (n & n - 1), 2)) # Indranil Ghosh, Apr 18 2017
  • Python
    def A007814(n): return (~n & n-1).bit_length() # Chai Wah Wu, Jul 01 2022
  • R
    sapply(1:100,function(x) sum(gmp::factorize(x)==2)) # Christian N. K. Anderson, Jun 20 2013
  • Scheme
    (define (A007814 n) (let loop ((n n) (e 0)) (if (odd? n) e (loop (/ n 2) (+ 1 e))))) ;; Antti Karttunen, Oct 06 2017

Formula

a(n) = A001511(n) - 1.
a(2*n) = A050603(2*n) = A001511(n).
a(n) = A091090(n-1) + A036987(n-1) - 1.
a(n) = 0 if n is odd, otherwise 1 + a(n/2). - Reinhard Zumkeller, Aug 11 2001
Sum_{k=1..n} a(k) = n - A000120(n). - Benoit Cloitre, Oct 19 2002
G.f.: A(x) = Sum_{k>=1} x^(2^k)/(1-x^(2^k)). - Ralf Stephan, Apr 10 2002
G.f. A(x) satisfies A(x) = A(x^2) + x^2/(1-x^2). A(x) = B(x^2) = B(x) - x/(1-x), where B(x) is the g.f. for A001151. - Franklin T. Adams-Watters, Feb 09 2006
Totally additive with a(p) = 1 if p = 2, 0 otherwise.
Dirichlet g.f.: zeta(s)/(2^s-1). - Ralf Stephan, Jun 17 2007
Define 0 <= k <= 2^n - 1; binary: k = b(0) + 2*b(1) + 4*b(2) + ... + 2^(n-1)*b(n-1); where b(x) are 0 or 1 for 0 <= x <= n - 1; define c(x) = 1 - b(x) for 0 <= x <= n - 1; Then: a(k) = c(0) + c(0)*c(1) + c(0)*c(1)*c(2) + ... + c(0)*c(1)...c(n-1); a(k+1) = b(0) + b(0)*b(1) + b(0)*b(1)*b(2) + ... + b(0)*b(1)...b(n-1). - Arie Werksma (werksma(AT)tiscali.nl), May 10 2008
a(n) = floor(A002487(n - 1) / A002487(n)). - Reikku Kulon, Oct 05 2008
Sum_{k=1..n} (-1)^A000120(n-k)*a(k) = (-1)^(A000120(n)-1)*(A000120(n) - A000035(n)). - Vladimir Shevelev, Mar 17 2009
a(A001147(n) + A057077(n-1)) = a(2*n). - Vladimir Shevelev, Mar 21 2009
For n>=1, a(A004760(n+1)) = a(n). - Vladimir Shevelev, Apr 15 2009
2^(a(n)) = A006519(n). - Philippe Deléham, Apr 22 2009
a(n) = A063787(n) - A000120(n). - Gary W. Adamson, Jun 04 2009
a(C(n,k)) = A000120(k) + A000120(n-k) - A000120(n). - Vladimir Shevelev, Jul 19 2009
a(n!) = n - A000120(n). - Vladimir Shevelev, Jul 20 2009
v_{2}(n) = Sum_{r>=1} (r / 2^(r+1)) Sum_{k=0..2^(r+1)-1} e^(2(k*Pi*i(n+2^r))/(2^(r+1))). - A. Neves, Sep 28 2010, corrected Oct 04 2010
a(n) mod 2 = A096268(n-1). - Robert G. Wilson v, Jan 18 2012
a(A005408(n)) = 1; a(A016825(n)) = 3; A017113(a(n)) = 5; A051062(a(n)) = 7; a(n) = (A037227(n)-1)/2. - Reinhard Zumkeller, Jun 30 2012
a((2*n-1)*2^p) = p, p >= 0 and n >= 1. - Johannes W. Meijer, Feb 04 2013
a(n) = A067255(n,1). - Reinhard Zumkeller, Jun 11 2013
a(n) = log_2(n - (n AND n-1)). - Gary Detlefs, Jun 13 2014
a(n) = 1 + A000120(n-1) - A000120(n), where A000120 is the Hamming weight function. - Stanislav Sykora, Jul 14 2014
A053398(n,k) = a(A003986(n-1,k-1)+1); a(n) = A053398(n,1) = A053398(n,n) = A053398(2*n-1,n) = Min_{k=1..n} A053398(n,k). - Reinhard Zumkeller, Aug 04 2014
a((2*x-1)*2^n) = a((2*y-1)*2^n) for positive n, x and y. - Juri-Stepan Gerasimov, Aug 04 2016
a(n) = A285406(n) - A281264(n). - Ralf Steiner, Apr 18 2017
a(n) = A000005(n)/(A000005(2*n) - A000005(n)) - 1. - conjectured by Velin Yanev, Jun 30 2017, proved by Nicholas Stearns, Sep 11 2017
Equivalently to above formula, a(n) = A183063(n) / A001227(n), i.e., a(n) is the number of even divisors of n divided by number of odd divisors of n. - Franklin T. Adams-Watters, Oct 31 2018
a(n)*(n mod 4) = 2*floor(((n+1) mod 4)/3). - Gary Detlefs, Feb 16 2019
Asymptotic mean: lim_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 1. - Amiram Eldar, Jul 11 2020
a(n) = 2*Sum_{j=1..floor(log_2(n))} frac(binomial(n, 2^j)*2^(j-1)/n). - Dario T. de Castro, Jul 08 2022
a(n) = A070939(n) - A070939(A030101(n)). - Andrew T. Porter, Dec 16 2022
a(n) = floor((gcd(n, 2^n)^(n+1) mod (2^(n+1)-1)^2)/(2^(n+1)-1)) (see Lemma 3.4 from Mazzanti's 2002 article). - Lorenzo Sauras Altuzarra, Mar 10 2024
a(n) = 1 - A088705(n). - Chai Wah Wu, Sep 18 2024

Extensions

Formula index adapted to the offset of A025480 by R. J. Mathar, Jul 20 2010
Edited by Ralf Stephan, Feb 08 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

Views

Author

N. J. A. Sloane

Keywords

Comments

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 m
Between 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

Examples

			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 + ...

References

  • 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).

Links

Crossrefs

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.

Programs

  • Haskell
    a001511 n = length $ takeWhile ((== 0) . (mod n)) a000079_list
-- Reinhard Zumkeller, Sep 27 2011
  • Haskell
    a001511 n | odd n = 1 | otherwise = 1 + a001511 (n `div` 2)
-- Walt Rorie-Baety, Mar 22 2013
  • MATLAB
    nmax=5;r=1;for n=2:nmax;r=[r n r];end % Adriano Caroli, Feb 26 2016
  • Magma
    [Valuation(2*n,2): n in [1..105]]; // Bruno Berselli, Nov 23 2015
  • Maple
    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
  • Mathematica
    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 *)
  • PARI
    a(n) = sum(k=0,floor(log(n)/log(2)),floor(n/2^k)-floor((n-1)/2^k)) /* Ralf Stephan */
  • PARI
    a(n)=if(n%2,1,factor(n)[1,2]+1) /* Jon Perry, Jun 06 2004 */
  • PARI
    {a(n) = if( n, valuation(n, 2) + 1, 0)}; /* Michael Somos, Sep 30 2006 */
  • PARI
    {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 */
  • Python
    def a(n): return bin(n)[2:][::-1].index("1") + 1 # Indranil Ghosh, May 11 2017
  • Python
    A001511 = lambda n: (n&-n).bit_length() # M. F. Hasler, Apr 09 2020
  • Python
    def A001511(n): return (~n & n-1).bit_length()+1 # Chai Wah Wu, Jul 01 2022
  • Sage
    [valuation(2*n,2) for n in (1..105)]  # Bruno Berselli, Nov 23 2015
  • Scheme
    (define (A001511 n) (let loop ((n n) (e 1)) (if (odd? n) e (loop (/ n 2) (+ 1 e))))) ;; Antti Karttunen, Oct 06 2017

Formula

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

Extensions

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

A008966 a(n) = 1 if n is squarefree, otherwise 0.

Original entry on oeis.org

1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

a(n) depends only on prime signature of n (cf. A025487). So a(24) = a(375) since 24 = 2^3*3 and 375 = 3*5^3 both have prime signature (3, 1).
The infinite lower triangular matrix with A008966 on the main diagonal and the rest zeros is the square of triangle A143255. - Gary W. Adamson, Aug 02 2008

Links

Crossrefs

Cf. A005117, A008836 (Dirichlet inverse), A013928 (partial sums).
Cf. A179211, A179212, A179213, A179214, A179215.
Cf. A020639, A073576, A087188.
Cf. A124010, A212793, A085357, A156552.
Parity of A002033.
Cf. A047999, A036987
Cf. A082020 (Dgf at s=2), A157289 (Dgf at s=3), A157290 (Dgf at s=4).

Programs

  • Haskell
    a008966 = abs . a008683
-- Reinhard Zumkeller, Dec 13 2015, Dec 15 2014, May 27 2012, Jan 25 2012
  • Magma
    [ Abs(MoebiusMu(n)) : n in [1..100]];
  • Maple
    A008966 := proc(n) if numtheory[issqrfree](n) then 1 ; else 0 ; end if; end proc: # R. J. Mathar, Mar 14 2011
  • Mathematica
    A008966[n_] := Abs[MoebiusMu[n]]; Table[A008966[n], {n, 100}] (* Enrique Pérez Herrero, Apr 15 2010 *)
Table[If[SquareFreeQ[n],1,0],{n,100}] (* or *) Boole[SquareFreeQ/@ Range[ 100]] (* Harvey P. Dale, Feb 28 2015 *)
  • MuPAD
    func(abs(numlib::moebius(n)), n):
  • PARI
    a(n)=if(n<1,0,direuler(p=2,n,1+X))[n]
  • PARI
    a(n)=issquarefree(n) \\ Michel Marcus, Feb 22 2015
  • Python
    from sympy import factorint
def A008966(n): return int(max(factorint(n).values(),default=1)==1) # Chai Wah Wu, Apr 05 2023

Formula

Dirichlet g.f.: zeta(s)/zeta(2s).
a(n) = abs(mu(n)), where mu is the Moebius function (A008683).
a(n) = 0^(bigomega(n) - omega(n)), where bigomega(n) and omega(n) are the numbers of prime factors of n with and without repetition (A001222, A001221, A046660). - Reinhard Zumkeller, Apr 05 2003
Multiplicative with p^e -> 0^(e - 1), p prime and e > 0. - Reinhard Zumkeller, Jul 15 2003
a(n) = 0^(A046951(n) - 1). - Reinhard Zumkeller, May 20 2007
a(n) = 1 - A107078(n). - Reinhard Zumkeller, Oct 03 2008
a(n) = floor(rad(n)/n), where rad() is A007947. - Enrique Pérez Herrero, Nov 13 2009
A175046(n) = a(n)*A073311(n). - Reinhard Zumkeller, Apr 05 2010
a(n) = floor(A000005(n^2)/A007425(n)). - Enrique Pérez Herrero, Apr 15 2010
a(A005117(n)) = 1; a(A013929(n)) = 0; a(n) = A013928(n + 1) - A013928(n). - Reinhard Zumkeller, Jul 05 2010
a(n) * A112526(n) = A063524(n). - Reinhard Zumkeller, Sep 16 2011
a(n) = mu(n) * lambda(n) = A008836(n) * A008683(n). - Enrique Pérez Herrero, Nov 29 2013
a(n) = Sum_{d|n} 2^omega(d)*mu(n/d). - Geoffrey Critzer, Feb 22 2015
a(n) = A085357(A156552(n)). - Antti Karttunen, Mar 06 2017
Limit_{n->oo} (1/n)*Sum_{j=1..n} a(j) = 6/Pi^2. - Andres Cicuttin, Aug 13 2017
a(1) = 1; a(n) = -Sum_{d|n, d < n} (-1)^bigomega(n/d) * a(d). - Ilya Gutkovskiy, Mar 10 2021

Extensions

Deleted an unclear comment. - N. J. A. Sloane, May 30 2021

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

Views

Author

N. J. A. Sloane

Keywords

Comments

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

Examples

			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

References

  • 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.

Links

Crossrefs

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

Programs

  • Haskell
    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
  • Magma
    [Ceiling(Log(2, n)): n in [1..100]]; // Vincenzo Librandi, Jun 14 2019
  • Maple
    a:= n-> (p-> p+`if`(2^pAlois P. Heinz, Mar 18 2013
  • Mathematica
    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 *)
  • PARI
    {a(n) = if( n<1, 0, ceil(log(n) / log(2)))};
  • PARI
    /* 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, ", "))
  • PARI
    {a(n) = if( n<2, 0, exponent(n-1)+1)}; /* Michael Somos, Jul 10 2018 */
  • Python
    def A029837(n):
    s = bin(n)[2:]
    return len(s) - (1 if s.count('1') == 1 else 0) # Chai Wah Wu, Jul 09 2020
  • Python
    def A029837(n): return (n-1).bit_length() # Chai Wah Wu, Jun 30 2022
  • Scala
    (1 to 80).map(n => Math.ceil(Math.log(n)/Math.log(2)).toInt) // Alonso del Arte, Feb 19 2020

Formula

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

Extensions

Additional comments from Daniele Parisse
More terms from Michael Somos, Aug 02 2002

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

Views

Author

Leroy Quet, Jul 29 2009

Keywords

Comments

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

Examples

			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

Links

Crossrefs

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).

Programs

  • Mathematica
    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 *)
  • Python
    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

Formula

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)

Extensions

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

A209229 Characteristic function of powers of 2, cf. A000079.

Original entry on oeis.org

0, 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
Offset: 0

Views

Author

Reinhard Zumkeller, Mar 06 2012

Keywords

Comments

Essentially the same as A036987 (the Fredholm-Rueppel sequence).
Completely multiplicative with a(2^e) = 1, a(p^e) = 0 for odd primes p. - Mitch Harris, Apr 19 2005
Moebius transform of A001511. - R. J. Mathar, Jun 20 2014

Examples

			x + x^2 + x^4 + x^8 + x^16 + x^32 + x^64 + x^128 + x^256 + x^512 + x^1024 + ...

References

  • Michel Dekking, Michel Mendes France and Alf van der Poorten, "Folds", The Mathematical Intelligencer, Vol. 4, No. 3 (1982), pp. 130-138 & front cover, and Vol. 4, No. 4 (1982), pp. 173-181 (printed in two parts).
  • Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.

Links

Crossrefs

Cf. A001511, A029837 (partial sums), A087003 (moebius transform), A090678, A104977, A154955 (Dirichlet inverse).
Cf. A069517, A154269, A201219, A255738.

Programs

  • C
    int a (unsigned long n) { return n & !(n & (n-1)); } /* Charles R Greathouse IV, Sep 15 2012 */
  • Haskell
    a209229 n | n < 2 = n
          | n > 1 = if m > 0 then 0 else a209229 n'
          where (n',m) = divMod n 2
  • Maple
    A209229 := proc(n)
    if n <= 0 then
        0 ;
    elif n = 1 then
        1;
    elif type (n,'odd') or A001221(n) > 1 then
        0 ;
    else
        1;
    end if;
end proc:
seq(A209229(n),n=0..40) ; # R. J. Mathar, Jan 07 2021
  • Mathematica
    a[n_] := Boole[n == 2^IntegerExponent[n, 2]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, May 06 2014 *)
Table[If[IntegerQ[Log[2,n]],1,0],{n,0,100}] (* Harvey P. Dale, Jun 24 2018 *)
  • PARI
    a(n)=n==1<Charles R Greathouse IV, Mar 07 2012
  • PARI
    {a(n) = if( n<2 || n%2, n==1, isprimepower(n) > 0)} \\ Michael Somos, Jan 03 2013
  • Python
    def A209229(n): return int(not(n&-n)^n) if n else 0 # Chai Wah Wu, Jul 08 2022

Formula

a(A000079(n)) = 1; a(A057716(n)) = 0.
a(n+1) = A036987(n).
a(n) = if n < 2 then n else (if n is even then a(n/2) else 0).
The generating function g(x) satisfies g(x) - g(x^2) = x. - Joerg Arndt, May 11 2010
Dirichlet g.f.: 1/(1 - 2^(-s)). - R. J. Mathar, Mar 07 2012
G.f.: x / (1 - x / (1 + x / (1 + x / (1 - x / (1 + x / (1 - x / ...)))))) = x / (1 + b(1) * x / (1 + b(2) * x / (1 + b(3) * x / ...))) where b(n) = (-1)^ A090678(n+1). - Michael Somos, Jan 03 2013
With a(0) = 0 removed is convolution inverse of A104977. - Michael Somos, Jan 03 2013
From Antti Karttunen, Nov 19 2017: (Start)
a(n) = abs(A154269(n)).
For n > 1, a(n) = A069517(n)/2 = 2 - A201219(n). (End)
a(n) = A048298(n)/n. - R. J. Mathar, Jan 07 2021
a(n) = floor((2^n)/n) - floor((2^n - 1)/n), for n>=1. - Ridouane Oudra, Oct 15 2021

A018819 Binary partition function: number of partitions of n into powers of 2.

Original entry on oeis.org

1, 1, 2, 2, 4, 4, 6, 6, 10, 10, 14, 14, 20, 20, 26, 26, 36, 36, 46, 46, 60, 60, 74, 74, 94, 94, 114, 114, 140, 140, 166, 166, 202, 202, 238, 238, 284, 284, 330, 330, 390, 390, 450, 450, 524, 524, 598, 598, 692, 692, 786, 786, 900, 900, 1014, 1014, 1154, 1154, 1294, 1294
Offset: 0

Views

Author

David W. Wilson, N. J. A. Sloane and J. H. Conway

Keywords

Comments

First differences of A000123; also A000123 with terms repeated. See the relevant proof that follows the first formula below.
Among these partitions there is exactly one partition with all distinct terms, as every number can be expressed as the sum of the distinct powers of 2.
Euler transform of A036987 with offset 1.
a(n) is the number of "non-squashing" partitions of n, that is, partitions n = p_1 + p_2 + ... + p_k with 1 <= p_1 <= p_2 <= ... <= p_k and p_1 + p_2 + ... + p_i <= p_{i+1} for all 1 <= i < k. - N. J. A. Sloane, Nov 30 2003
Normally the OEIS does not include sequences like this where every term is repeated, but an exception was made for this one because of its importance. The unrepeated sequence A000123 is the main entry.
Number of different partial sums from 1 + [1, *2] + [1, *2] + ..., where [1, *2] means we can either add 1 or multiply by 2. E.g., a(6) = 6 because we have 6 = 1 + 1 + 1 + 1 + 1 + 1 = (1+1) * 2 + 1 + 1 = 1 * 2 * 2 + 1 + 1 = (1+1+1) * 2 = 1 * 2 + 1 + 1 + 1 + 1 = (1*2+1) * 2 where the connection is defined via expanding each bracket; e.g., this is 6 = 1 + 1 + 1 + 1 + 1 + 1 = 2 + 2 + 1 + 1 = 4 + 1 + 1 = 2 + 2 + 2 = 2 + 1 + 1 + 1 + 1 = 4 + 2. - Jon Perry, Jan 01 2004
Number of partitions p of n such that the number of compositions generated by p is odd. For proof see the Alekseyev and Adams-Watters link. - Vladeta Jovovic, Aug 06 2007
Differs from A008645 first at a(64). - R. J. Mathar, May 28 2008
Appears to be row sums of A155077. - Mats Granvik, Jan 19 2009
Number of partitions (p_1, p_2, ..., p_k) of n, with p_1 >= p_2 >= ... >= p_k, such that for each i, p_i >= p_{i+1} + ... + p_k. - John MCKAY (mckay(AT)encs.concordia.ca), Mar 06 2009 (these are the "non-squashing" partitions as nonincreasing lists).
Equals rightmost diagonal of triangle of A168261. Starting with offset 1 = eigensequence of triangle A115361 and row sums of triangle A168261. - Gary W. Adamson, Nov 21 2009
Equals convolution square root of A171238: (1, 2, 5, 8, 16, 24, 40, 56, 88, ...). - Gary W. Adamson, Dec 05 2009
Let B = the n-th convolution power of the sequence and C = the aerated variant of B. It appears that B/C = the binomial sequence beginning (1, n, ...). Example: Third convolution power of the sequence is (1, 3, 9, 19, 42, 78, 146, ...), with C = (1, 0, 3, 0, 9, 0, 19, ...). Then B/C = (1, 3, 6, 10, 15, 21, ...). - Gary W. Adamson, Aug 15 2016
From Gary W. Adamson, Sep 08 2016: (Start)
The limit of the matrix power M^k as n-->inf results in a single column vector equal to the sequence, where M is the following production matrix:
1, 0, 0, 0, 0, ...
1, 0, 0, 0, 0, ...
1, 1, 0, 0, 0, ...
1, 1, 0, 0, 0, ...
1, 1, 1, 0, 0, ...
1, 1, 1, 0, 0, ...
1, 1, 1, 1, 0, ...
1, 1, 1, 1, 0, ...
1, 1, 1, 1, 1, ...
... (End)
a(n) is the number of "non-borrowing" partitions of n, meaning binary subtraction of a smaller part from a larger part will never require place-value borrowing. - David V. Feldman, Jan 29 2020
From Gus Wiseman, May 25 2024: (Start)
Also the number of multisets of positive integers whose binary rank is n, where the binary rank of a multiset m is given by Sum_i 2^(m_i-1). For example, the a(1) = 1 through a(8) = 10 multisets are:
{1} {2} {12} {3} {13} {23} {123} {4}
{11} {111} {22} {122} {113} {1113} {33}
{112} {1112} {222} {1222} {223}
{1111} {11111} {1122} {11122} {1123}
{11112} {111112} {2222}
{111111} {1111111} {11113}
{11222}
{111122}
{1111112}
{11111111}
(End)

Examples

			G.f. = 1 + x + 2*x^2 + 2*x^3 + 4*x^4 + 4*x^5 + 6*x^6 + 6*x^7 + 10*x^8 + ...
a(4) = 4: the partitions are 4, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1.
a(7) = 6: the partitions are 4 + 2 + 1, 4 + 1 + 1 + 1, 2 + 2 + 2 + 1, 2 + 2 + 1 + 1 + 1, 2 + 1 + 1 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1 + 1 + 1.
From _Joerg Arndt_, Dec 17 2012: (Start)
The a(10) = 14 binary partitions of 10 are (in lexicographic order)
[ 1]  [ 1 1 1 1 1 1 1 1 1 1 ]
[ 2]  [ 2 1 1 1 1 1 1 1 1 ]
[ 3]  [ 2 2 1 1 1 1 1 1 ]
[ 4]  [ 2 2 2 1 1 1 1 ]
[ 5]  [ 2 2 2 2 1 1 ]
[ 6]  [ 2 2 2 2 2 ]
[ 7]  [ 4 1 1 1 1 1 1 ]
[ 8]  [ 4 2 1 1 1 1 ]
[ 9]  [ 4 2 2 1 1 ]
[10]  [ 4 2 2 2 ]
[11]  [ 4 4 1 1 ]
[12]  [ 4 4 2 ]
[13]  [ 8 1 1 ]
[14]  [ 8 2 ]
The a(11) = 14 binary partitions of 11 are obtained by appending 1 to each partition in the list.
The a(10) = 14 non-squashing partitions of 10 are (in lexicographic order)
[ 1]  [ 6 3 1 1 ]
[ 2]  [ 6 3 2 ]
[ 3]  [ 6 4 1 ]
[ 4]  [ 6 5 ]
[ 5]  [ 7 2 1 1 ]
[ 6]  [ 7 2 2 ]
[ 7]  [ 7 3 1 ]
[ 8]  [ 7 4 ]
[ 9]  [ 8 2 1 ]
[10]  [ 8 3 ]
[11]  [ 9 1 1 ]
[12]  [ 9 2 ]
[13]  [ 10 1 ]
[14]  [ 11 ]
The a(11) = 14 non-squashing partitions of 11 are obtained by adding 1 to the first part in each partition in the list.
(End)
From _David V. Feldman_, Jan 29 2020: (Start)
The a(10) = 14 non-borrowing partitions of 10 are (in lexicographic order)
[ 1] [1 1 1 1 1 1 1 1 1 1]
[ 2] [2 2 2 2 2]
[ 3] [3 1 1 1 1 1 1 1]
[ 4] [3 3 1 1 1 1]
[ 5] [3 3 2 2]
[ 6] [3 3 3 1]
[ 7] [5 1 1 1 1 1]
[ 8] [5 5]
[ 9] [6 2 2]
[10] [6 4]
[11] [7 1 1 1]
[12] [7 3]
[13] [9 1]
[14] [10]
The a(11) = 14 non-borrowing partitions of 11 are obtained either by adding 1 to the first even part in each partition (if any) or else appending a 1 after the last part.
(End)
For example, the five partitions of 4, written in nonincreasing order, are [1, 1, 1, 1], [2, 1, 1], [2, 2], [3, 1], [4]. The last four satisfy the condition, and a(4) = 4. The Maple program below verifies this for small values of n.

Links

Crossrefs

A000123 is the main entry for the binary partition function and gives many more properties and references.
Cf. A115625 (labeled binary partitions), A115626 (labeled non-squashing partitions).
Convolution inverse of A106400.
Cf. A023893, A062051, A105420, A131995, A040039, A018819, A088567, A089054, A115361, A168261, A171238, A179051, A008619.
Multiplicity of n in A048675, for distinct prime indices A087207.
Row lengths of A277905.
A118462 lists binary ranks of strict integer partitions, row sums A372888.
A372890 adds up binary ranks of integer partitions.
Binary indices: A000120, A001511, A029931, A048793, A070939, A272020.
Cf. A005940, A019565, A056239, A158704, A158705, A231204, A277319, A372688.

Programs

  • Haskell
    a018819 n = a018819_list !! n
a018819_list = 1 : f (tail a008619_list) where
   f (x:xs) = (sum $ take x a018819_list) : f xs
-- Reinhard Zumkeller, Jan 28 2012
  • Haskell
    import Data.List (intersperse)
a018819 = (a018819_list !!)
a018819_list = 1 : 1 : (<*>) (zipWith (+)) (intersperse 0) (tail a018819_list)
-- Johan Wiltink, Nov 08 2018
  • Maple
    with(combinat); N:=8; a:=array(1..N); c:=array(1..N);
for n from 1 to N do p:=partition(n); np:=nops(p); t:=0;
for s to np do r:=p[s]; r:=sort(r,`>`); nr:=nops(r); j:=1;
# while jsum(r[k],k=j+1..nr) do j:=j+1;od; # gives A040039
while j= sum(r[k],k=j+1..nr) do j:=j+1;od; # gives A018819
if j=nr then t:=t+1;fi od; a[n]:=t; od; # John McKay
  • Mathematica
    max = 59; a[0] = a[1] = 1; a[n_?OddQ] := a[n] = a[n-1]; a[n_?EvenQ] := a[n] = a[n-1] + a[n/2]; Table[a[n], {n, 0, max}]
(* or *) CoefficientList[Series[1/Product[(1-x^(2^j)), {j, 0, Log[2, max] // Ceiling}], {x, 0, max}], x] (* Jean-François Alcover, May 17 2011, updated Feb 17 2014 *)
a[ n_] := If[n<1, Boole[n==0], a[n] = a[n-1] + If[EvenQ@n, a[Quotient[n,2]], 0]]; (* Michael Somos, May 04 2022 *)
Table[Count[IntegerPartitions[n],?(AllTrue[Log2[#],IntegerQ]&)],{n,0,60}] (* _Harvey P. Dale, Jun 20 2024 *)
  • PARI
    { n=15; v=vector(n); for (i=1,n,v[i]=vector(2^(i-1))); v[1][1]=1; for (i=2,n, k=length(v[i-1]); for (j=1,k, v[i][j]=v[i-1][j]+1; v[i][j+k]=v[i-1][j]*2)); c=vector(n); for (i=1,n, for (j=1,2^(i-1), if (v[i][j]<=n, c[v[i][j]]++))); c } /* Jon Perry */
  • PARI
    {a(n) = my(A, m); if( n<1, n==0, m=1; A = 1 + O(x); while(m<=n, m*=2; A = subst(A, x, x^2) / (1 - x)); polcoeff(A, n))}; /* Michael Somos, Aug 25 2003 */
  • PARI
    {a(n) = if( n<1, n==0, if( n%2, a(n-1), a(n/2)+a(n-1)))}; /* Michael Somos, Aug 25 2003 */
  • Python
    from functools import lru_cache
@lru_cache(maxsize=None)
def A018819(n): return 1 if n == 0 else A018819(n-1) + (0 if n % 2 else A018819(n//2)) # Chai Wah Wu, Jan 18 2022

Formula

a(2m+1) = a(2m), a(2m) = a(2m-1) + a(m). Proof: If n is odd there is a part of size 1; removing it gives a partition of n - 1. If n is even either there is a part of size 1, whose removal gives a partition of n - 1, or else all parts have even sizes and dividing each part by 2 gives a partition of n/2.
G.f.: 1 / Product_{j>=0} (1-x^(2^j)).
a(n) = (1/n)*Sum_{k = 1..n} A038712(k)*a(n-k), n > 1, a(0) = 1. - Vladeta Jovovic, Aug 22 2002
a(2*n) = a(2*n + 1) = A000123(n). - Michael Somos, Aug 25 2003
a(n) = 1 if n = 0, Sum_{j = 0..floor(n/2)} a(j) if n > 0. - David W. Wilson, Aug 16 2007
G.f. A(x) satisfies A(x^2) = (1-x) * A(x). - Michael Somos, Aug 25 2003
G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^4)) where f(u, v, w) = u^2*w - 2*u*v^2 + v^3. - Michael Somos, Apr 10 2005
G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^3), A(x^6)) where f(u1, u2, u3, u6) = u6 * u1^3 - 3*u3*u2*u1^2 + 3*u3*u2^2*u1 - u3*u2^3. - Michael Somos, Oct 15 2006
G.f.: 1/( Sum_{n >= 0} x^evil(n) - x^odious(n) ), where evil(n) = A001969(n) and odious(n) = A000069(n). - Paul D. Hanna, Jan 23 2012
Let A(x) by the g.f. and B(x) = A(x^k), then 0 = B*((1-A)^k - (-A)^k) + (-A)^k, see fxtbook link. - Joerg Arndt, Dec 17 2012
G.f.: Product_{n>=0} (1+x^(2^n))^(n+1), see the fxtbook link. - Joerg Arndt, Feb 28 2014
G.f.: 1 + Sum_{i>=0} x^(2^i) / Product_{j=0..i} (1 - x^(2^j)). - Ilya Gutkovskiy, May 07 2017

A053645 Distance to largest power of 2 less than or equal to n; write n in binary, change the first digit to zero, and convert back to decimal.

Original entry on oeis.org

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

Views

Author

Henry Bottomley, Mar 22 2000

Keywords

Comments

Triangle read by rows in which row n lists the first 2^n nonnegative integers (A001477), n >= 0. Right border gives A000225. Row sums give A006516. See example. - Omar E. Pol, Oct 17 2013
Without the initial zero also: zeroless numbers in base 3 (A032924: 1, 2, 11, 12, 21, ...), ternary digits decreased by 1 and read as binary. - M. F. Hasler, Jun 22 2020

Examples

			From _Omar E. Pol_, Oct 17 2013: (Start)
Written as an irregular triangle the sequence begins:
  0;
  0,1;
  0,1,2,3;
  0,1,2,3,4,5,6,7;
  0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15;
  ...
(End)

Links

Crossrefs

Cf. A000225, A000523, A002262, A004760, A006257, A006516, A030308, A036987, A053644, A062050, A083741, A160588.

Programs

  • Haskell
    a053645 1 = 0
a053645 n = 2 * a053645 n' + b  where (n', b) = divMod n 2
-- Reinhard Zumkeller, Aug 28 2014
a053645_list = concatMap (0 `enumFromTo`) a000225_list
-- Reinhard Zumkeller, Feb 04 2013, Mar 23 2012
  • Magma
    [n - 2^Ilog2(n): n in [1..70]]; // Vincenzo Librandi, Jul 18 2019
  • Maple
    seq(n - 2^ilog2(n), n=1..1000); # Robert Israel, Dec 23 2015
  • Mathematica
    Table[n - 2^Floor[Log2[n]], {n, 100}] (* IWABUCHI Yu(u)ki, May 25 2017 *)
Table[FromDigits[Rest[IntegerDigits[n, 2]], 2], {n, 100}] (* IWABUCHI Yu(u)ki, May 25 2017 *)
  • PARI
    a(n)=n-2^(#binary(n)-1) \\ Charles R Greathouse IV, Sep 02 2015
  • Python
    def a(n): return n - 2**(n.bit_length()-1)
print([a(n) for n in range(1, 85)]) # Michael S. Branicky, Jul 03 2021
  • Python
    def A053645(n): return n&(1<Chai Wah Wu, Jan 22 2023

Formula

a(n) = n - 2^A000523(n).
G.f.: 1/(1-x) * ((2x-1)/(1-x) + Sum_{k>=1} 2^(k-1)*x^2^k). - Ralf Stephan, Apr 18 2003
a(n) = (A006257(n)-1)/2. - N. J. A. Sloane, May 16 2003
a(1) = 0, a(2n) = 2a(n), a(2n+1) = 2a(n) + 1. - N. J. A. Sloane, Sep 13 2003
a(n) = A062050(n) - 1. - N. J. A. Sloane, Jun 12 2004
a(A004760(n+1)) = n. - Reinhard Zumkeller, May 20 2009
a(n) = f(n-1,1) with f(n,m) = if n < m then n else f(n-m,2*m). - Reinhard Zumkeller, May 20 2009
Conjecture: a(n) = (1 - A036987(n-1))*(1 + a(n-1)) for n > 1 with a(1) = 0. - Mikhail Kurkov, Jul 16 2019
Previous Showing 11-20 of 120 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.