cp's OEIS Frontend

As A001222 and A064097 are both fully additive sequences, all sequences that give the positions of multiples of some natural number k in this sequence are closed under multiplication, i.e., are multiplicative semigroups.

Terms a(3) .. a(11) are squarefree semiprimes, but 33554945 = 5 * 47 * 142787.

Records themselves are: 0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13.

Completely additive because A003961 is fully multiplicative and A064097 is fully additive.

Completely additive because A064097 and A334863 are.

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

MacMahon calls this the potency of n.

Downgrades the operators in a prime decomposition. E.g., 40 factors as 2^3 * 5 and sopfr(40) = 2 * 3 + 5 = 11.

Consider all ways of writing n as a product of zero, one, or more factors; sequence gives smallest sum of terms. - Amarnath Murthy, Jul 07 2001

a(n) <= n for all n, and a(n) = n iff n is 4 or a prime.

Look at the graph of this sequence. At the lower edge of the logarithmic scatterplot there is a set of fuzzy but unmistakable diagonal fringes, sloping toward the southeast. Their spacing gradually increases, and their slopes gradually decrease; they are more distinct toward the lower edge of the range. Is any explanation known? - Allan C. Wechsler, Oct 11 2015

For n >= 2, the glb and lub are: 3 * log(n) / log(3) <= a(n) <= n, where the lub occurs when n = 3^k, k >= 1. (Jakimczuk 2012) - Daniel Forgues, Oct 12 2015

Except for the initial term, row sums of A027746. - M. F. Hasler, Feb 08 2016

Atanassov proves that a(n) <= A065387(n) - n. - Charles R Greathouse IV, Dec 06 2016

From Robert G. Wilson v, Aug 15 2022: (Start)

Differs from A337310 beginning with n at 64, 192, 256, 320, 448, 512, ..., .

The number of terms which equal k is A000607(k).

The first occurrence of k>1 is A056240(k).

The last occurrence of k>1 is A000792(k).

The Amarnath Murthy comment of Jul 07 2001 is a result of the fundamental theorem of arithmetic.

(End)

Is a(n) the least m > 0 such that n - m divides n! + m? - Clark Kimberling, Jul 28 2012

Is a(n) the least m > 0 such that L(n-m) divides L(n+m), where L = A000032 (Lucas numbers)? - Clark Kimberling, Jul 30 2012

Records give A006093. - Omar E. Pol, Oct 26 2013

Divide n by its smallest prime factor p, then multiply with (p-1), with a(1) = 0 by convention. Compare also to A366387. - Antti Karttunen, Oct 23 2023

a(n) is also the smallest LCM of positive integers x and y where x + y = n. - Felix Huber, Aug 28 2024

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