cp's OEIS Frontend

Is the sequence finite?

In the general case, the residue of a number n in the 3x+1 problem is defined as the ratio res(n) = 2^A006666(n) / (n*3^A006667(n)) (see A127789).

Conjecture: for all prime p, res(p) < res(993) = 2^61/(3^32*993) = 1.253142... (see A304174).

A006666 and A006667 are respectively the number of halving and tripling steps in the '3x+1' problem.

The corresponding integers are 4, 3, 5, 3, 6, 6, 4, 4, 7, 7, 3, 3, 3, 8, 8, 8, 5, 5, 5, 3, 5, 3, 3, 3, ...

The numbers of the form (4^k - 1)/3 for k > 1 (A002450) are in the sequence.

We observe subsets of consecutive numbers: (5, 6), (20, 21), (44, 45, 46), (84, 85), (112, 113), ...

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

The 3x+1 or Collatz problem is as follows: start with any number n. If n is even, divide it by 2, otherwise multiply it by 3 and add 1. Do we always reach 1? This is a famous unsolved problem. It is conjectured that the answer is yes.

It seems that about half of the terms satisfy a(i) = a(i+1). For example, up to 10000000, 4964705 terms satisfy this condition.

n is an element of row a(n) in triangle A127824. - Reinhard Zumkeller, Oct 03 2012

The number of terms that satisfy a(i) = a(i+1) for i being a power of ten from 10^1 through 10^10 are: 0, 31, 365, 4161, 45022, 477245, 4964705, 51242281, 526051204, 5378743993. - John Mason, Mar 02 2018

5 seems to be the only number whose value matches its total number of steps (checked to n <= 10^9). - Peter Woodward, Feb 15 2021

Equals the total number of steps to reach 1 under the modified '3x+1' map: T(n) = n/2 if n is even, (3n+1)/2 if n is odd (see A014682).

Pairs of consecutive integers of the same height occur infinitely often and in infinitely many different patterns (Garner 1985). - Joe Slater, May 24 2018

The number of steps (iterations of the map A006370) to reach 1 is given by A006577, this sequence counts 1 more. - M. F. Hasler, Nov 05 2017

When Collatz 3N+1 function is seen as an isometry over the dyadics, the halving step necessarily following each tripling is not counted, hence N -> N/2, if even, but N -> (3N+1)/2, if odd. Counting iterations of this map until reaching 1 leads to sequence A064433. - Michael Vielhaber (vielhaber(AT)gmail.com), Nov 18 2009

The Collatz function (related to the "3x+1 problem") is defined by: f(n) = n/2 if n is even; f(n) = 3n + 1 if n is odd. A famous conjecture states that n, f(n), f(f(n)), .... eventually reaches 1.

a(n) = A006667(n) + 1; a(A000079(n))=1; a(A062052(n))=2; a(A062053(n))=3; a(A062054(n))=4; a(A062055(n))=5; a(A062056(n))=6; a(A062057(n))=7; a(A062058(n))=8; a(A062059(n))=9; a(A062060(n))=10. - Reinhard Zumkeller, Oct 08 2011

The count includes also the starting value n if it is odd. See A286380 for the version which never includes n itself. - Antti Karttunen, Aug 10 2017

See A075677 for the function R applied to the odd numbers once. The 3x+1 conjecture asserts that a(n) is a finite number for all n. The function R applied to the odd numbers shows the essential behavior of the 3x+1 iterations.

Bisection of A006667. - T. D. Noe, Jun 01 2006

The Collatz (or 3x+1) function is f(x) = x/2 if x is even, 3x+1 if x is odd.

The Collatz trajectory of n is obtained by applying f repeatedly to n until 1 is reached.

The sequence consists of terms of A002450 and their 2^k multiples. The first odd integer in the trajectory is one of the terms of A002450 and the second odd one is the terminal 1. - Antti Karttunen, Feb 21 2006

This sequence looks to appear first in the literature on page 1285 in R. E. Crandall.