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 61-70 of 1353 results. Next

A003462 a(n) = (3^n - 1)/2.

Original entry on oeis.org

0, 1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 797161, 2391484, 7174453, 21523360, 64570081, 193710244, 581130733, 1743392200, 5230176601, 15690529804, 47071589413, 141214768240, 423644304721, 1270932914164
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Partial sums of A000244. Values of base 3 strings of 1's.
a(n) = (3^n-1)/2 is also the number of different nonparallel lines determined by pair of vertices in the n dimensional hypercube. Example: when n = 2 the square has 4 vertices and then the relevant lines are: x = 0, y = 0, x = 1, y = 1, y = x, y = 1-x and when we identify parallel lines only 4 remain: x = 0, y = 0, y = x, y = 1 - x so a(2) = 4. - Noam Katz (noamkj(AT)hotmail.com), Feb 11 2001
Also number of 3-block bicoverings of an n-set (if offset is 1, cf. A059443). - Vladeta Jovovic, Feb 14 2001
3^a(n) is the highest power of 3 dividing (3^n)!. - Benoit Cloitre, Feb 04 2002
Apart from the a(0) and a(1) terms, maximum number of coins among which a lighter or heavier counterfeit coin can be identified (but not necessarily labeled as heavier or lighter) by n weighings. - Tom Verhoeff, Jun 22 2002, updated Mar 23 2017
n such that A001764(n) is not divisible by 3. - Benoit Cloitre, Jan 14 2003
Consider the mapping f(a/b) = (a + 2b)/(2a + b). Taking a = 1, b = 2 to start with and carrying out this mapping repeatedly on each new (reduced) rational number gives the sequence 1/2, 4/5, 13/14, 40/41, ... converging to 1. Sequence contains the numerators = (3^n-1)/2. The same mapping for N, i.e., f(a/b) = (a + Nb)/(a+b) gives fractions converging to N^(1/2). - Amarnath Murthy, Mar 22 2003
Binomial transform of A000079 (with leading zero). - Paul Barry, Apr 11 2003
With leading zero, inverse binomial transform of A006095. - Paul Barry, Aug 19 2003
Number of walks of length 2*n + 2 in the path graph P_5 from one end to the other one. Example: a(2) = 4 because in the path ABCDE we have ABABCDE, ABCBCDE, ABCDCDE and ABCDEDE. - Emeric Deutsch, Apr 02 2004
The number of triangles of all sizes (not counting holes) in Sierpiński's triangle after n inscriptions. - Lee Reeves (leereeves(AT)fastmail.fm), May 10 2004
Number of (s(0), s(1), ..., s(2n+1)) such that 0 < s(i) < 6 and |s(i) - s(i-1)| = 1 for i = 1, 2, ..., 2*n + 1, s(0) = 1, s(2n+1) = 4. - Herbert Kociemba, Jun 10 2004
Number of non-degenerate right-angled incongruent integer-edged Heron triangles whose circumdiameter is the product of n distinct primes of shape 4k + 1. - Alex Fink and R. K. Guy, Aug 18 2005
Also numerator of the sum of the reciprocals of the first n powers of 3, with A000244 being the sequence of denominators. With the exception of n < 2, the base 10 digital root of a(n) is always 4. In base 3 the digital root of a(n) is the same as the digital root of n. - Alonso del Arte, Jan 24 2006
The sequence 3*a(n), n >= 1, gives the number of edges of the Hanoi graph H_3^{n} with 3 pegs and n >= 1 discs. - Daniele Parisse, Jul 28 2006
Numbers n such that a(n) is prime are listed in A028491 = {3, 7, 13, 71, 103, 541, 1091, ...}. 2^(m+1) divides a(2^m*k) for m > 0. 5 divides a(4k). 5^2 divides a(20k). 7 divides a(6k). 7^2 divides a(42k). 11^2 divides a(5k). 13 divides a(3k). 17 divides a(16k). 19 divides a(18k). 1093 divides a(7k). 41 divides a(8k). p divides a((p-1)/5) for prime p = {41, 431, 491, 661, 761, 1021, 1051, 1091, 1171, ...}. p divides a((p-1)/4) for prime p = {13, 109, 181, 193, 229, 277, 313, 421, 433, 541, ...}. p divides a((p-1)/3) for prime p = {61, 67, 73, 103, 151, 193, 271, 307, 367, ...} = A014753, 3 and -3 are both cubes (one implies other) mod these primes p = 1 mod 6. p divides a((p-1)/2) for prime p = {11, 13, 23, 37, 47, 59, 61, 71, 73, 83, 97, ...} = A097933(n). p divides a(p-1) for prime p > 7. p^2 divides a(p*(p-1)k) for all prime p except p = 3. p^3 divides a(p*(p-1)*(p-2)k) for prime p = 11. - Alexander Adamchuk, Jan 22 2007
Let P(A) be the power set of an n-element set A. Then a(n) = the number of [unordered] pairs of elements {x,y} of P(A) for which x and y are disjoint [and both nonempty]. Wieder calls these "disjoint usual 2-combinations". - Ross La Haye, Jan 10 2008 [This is because each of the elements of {1, 2, ..., n} can be in the first subset, in the second or in neither. Because there are three options for each, the total number of options is 3^n. However, since the sets being empty is not an option we subtract 1 and since the subsets are unordered we then divide by 2! (The number of ways two objects can be arranged.) Thus we obtain (3^n-1)/2 = a(n). - Chayim Lowen, Mar 03 2015]
Also, still with P(A) being the power set of a n-element set A, a(n) is the number of 2-element subsets {x,y} of P(A) such that the union of x and y is equal to A. Cf. A341590. - Fabio Visonà, Feb 20 2021
Starting with offset 1 = binomial transform of A003945: (1, 3, 6, 12, 24, ...) and double bt of (1, 2, 1, 2, 1, 2, ...); equals polcoeff inverse of (1, -4, 3, 0, 0, 0, ...). - Gary W. Adamson, May 28 2009
Also the constant of the polynomials C(x) = 3x + 1 that form a sequence by performing this operation repeatedly and taking the result at each step as the input at the next. - Nishant Shukla (n.shukla722(AT)gmail.com), Jul 11 2009
It appears that this is A120444(3^n-1) = A004125(3^n) - A004125(3^n-1), where A004125 is the sum of remainders of n mod k for k = 1, 2, 3, ..., n. - John W. Layman, Jul 29 2009
Subsequence of A134025; A171960(a(n)) = a(n). - Reinhard Zumkeller, Jan 20 2010
Let A be the Hessenberg matrix of order n, defined by: A[1,j] = 1, A[i, i] := 3, (i > 1), A[i, i-1] = -1, and A[i, j] = 0 otherwise. Then, for n >= 1, a(n) = det(A). - Milan Janjic, Jan 27 2010
This is the sequence A(0, 1; 2, 3; 2) = A(0, 1; 4, -3; 0) of the family of sequences [a, b:c, d:k] considered by Gary Detlefs, and treated as A(a, b; c, d; k) in the Wolfdieter Lang link given below. - Wolfdieter Lang, Oct 18 2010
It appears that if s(n) is a first order rational sequence of the form s(0) = 0, s(n) = (2*s(n-1)+1)/(s(n-1)+2), n > 0, then s(n)= a(n)/(a(n)+1). - Gary Detlefs, Nov 16 2010
This sequence also describes the total number of moves to solve the [RED ; BLUE ; BLUE] or [RED ; RED ; BLUE] pre-colored Magnetic Towers of Hanoi puzzle (cf. A183111 - A183125).
From Adi Dani, Jun 08 2011: (Start)
a(n) is number of compositions of odd numbers into n parts less than 3. For example, a(3) = 13 and there are 13 compositions odd numbers into 3 parts < 3:
1: (0, 0, 1), (0, 1, 0), (1, 0, 0);
3: (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0), (1, 1, 1);
5: (1, 2, 2), (2, 1, 2), (2, 2, 1).
(End)
Pisano period lengths: 1, 2, 1, 2, 4, 2, 6, 4, 1, 4, 5, 2, 3, 6, 4, 8, 16, 2, 18, 4, ... . - R. J. Mathar, Aug 10 2012
a(n) is the total number of holes (triangles removed) after the n-th step of a Sierpiński triangle production. - Ivan N. Ianakiev, Oct 29 2013
a(n) solves Sum_{j = a(n) + 1 .. a(n+1)} j = k^2 for some integer k, given a(0) = 0 and requiring smallest a(n+1) > a(n). Corresponding k = 3^n. - Richard R. Forberg, Mar 11 2015
a(n+1) equals the number of words of length n over {0, 1, 2, 3} avoiding 01, 02 and 03. - Milan Janjic, Dec 17 2015
For n >= 1, a(n) is also the total number of words of length n, over an alphabet of three letters, such that one of the letters appears an odd number of times (See A006516 for 4 letter words, and the Balakrishnan reference there). - Wolfdieter Lang, Jul 16 2017
Also, the number of maximal cliques, maximum cliques, and cliques of size 4 in the n-Apollonian network. - Andrew Howroyd, Sep 02 2017
For n > 1, the number of triangles (cliques of size 3) in the (n-1)-Apollonian network. - Andrew Howroyd, Sep 02 2017
a(n) is the largest number that can be represented with n trits in balanced ternary. Correspondingly, -a(n) is the smallest number that can be represented with n trits in balanced ternary. - Thomas König, Apr 26 2020
These form Sierpinski nesting-stars, which alternate pattern on 3^n+1/2 star numbers A003154, based on the square configurations of 9^n. The partial sums of 3^n are delineated according to the geometry of a hexagram, see illustrations in links. (3*a(n-1) + 1) create Sierpinski-anti-triangles, representing the number of holes in a (n+1) Sierpinski triangle (see illustrations). - John Elias, Oct 18 2021
For n > 1, a(n) is the number of iterations necessary to calculate the hyperbolic functions with CORDIC. - Mathias Zechmeister, Jul 26 2022
a(n) is the least number k such that A065363(k) = n. - Amiram Eldar, Sep 03 2022
For all n >= 0, Sum_{k=a(n)+1..a(n+1)} 1/k < Sum_{j=a(n+1)+1..a(n+2)} 1/j. These are the minimal points which partition the infinite harmonic series into a monotonically increasing sequence. Each partition approximates log(3) from below as n tends to infinity. - Joseph Wheat, Apr 15 2023
a(n) is also the number of 3-cycles in the n-Dorogovtsev-Goltsev-Mendes graph (using the convention the 0-Dorogovtsev-Goltsev-Mendes graph is P_2). - Eric W. Weisstein, Dec 06 2023

Examples

			There are 4 3-block bicoverings of a 3-set: {{1, 2, 3}, {1, 2}, {3}}, {{1, 2, 3}, {1, 3}, {2}}, {{1, 2, 3}, {1}, {2, 3}} and {{1, 2}, {1, 3}, {2, 3}}.
Ternary........Decimal
0.................0
1.................1
11................4
111..............13
1111.............40 etc. - _Zerinvary Lajos_, Jan 14 2007
There are altogether a(3) = 13 three letter words over {A,B,C} with say, A, appearing an odd number of times: AAA; ABC, ACB, ABB, ACC; BAC, CAB, BAB, CAC; BCA, CBA, BBA, CCA. - _Wolfdieter Lang_, Jul 16 2017

References

  • J. G. Mauldon, Strong solutions for the counterfeit coin problem, IBM Research Report RC 7476 (#31437) 9/15/78, IBM Thomas J. Watson Research Center, P. O. Box 218, Yorktown Heights, N. Y. 10598.
  • Paulo Ribenboim, The Book of Prime Number Records, Springer-Verlag, NY, 2nd ed., 1989, p. 60.
  • Paulo Ribenboim, The Little Book of Big Primes, Springer-Verlag, NY, 1991, p. 53.
  • Amir Sapir, The Tower of Hanoi with Forbidden Moves, The Computer J. 47 (1) (2004) 20, case three-in-a row, sequence a(n).
  • Robert Sedgewick, Algorithms, 1992, pp. 109.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Sequences used for Shell sort: A033622, A003462, A036562, A036564, A036569, A055875.
Cf. A179526 (repeats), A113047 (characteristic function).
Cf. A000225, A000392, A004125, A014753, A028491 (indices of primes), A059443 (column k = 3), A065363, A097933, A120444, A321872 (sum reciprocals).
Cf. A064099 (minimal number of weightings to detect lighter or heavier coin among n coins).
Cf. A039755 (column k = 1).
Cf. A006516 (binomial transform, and special 4 letter words).
Cf. A341590.
Cf. A003462(n) (3-cycles), A367967(n) (5-cycles), A367968(n) (6-cycles).

Programs

Formula

G.f.: x/((1-x)*(1-3*x)).
a(n) = 4*a(n-1) - 3*a(n-2), n > 1. a(0) = 0, a(1) = 1.
a(n) = 3*a(n-1) + 1, a(0) = 0.
E.g.f.: (exp(3*x) - exp(x))/2. - Paul Barry, Apr 11 2003
a(n+1) = Sum_{k = 0..n} binomial(n+1, k+1)*2^k. - Paul Barry, Aug 20 2004
a(n) = Sum_{i = 0..n-1} 3^i, for n > 0; a(0) = 0.
a(n) = A125118(n, 2) for n > 1. - Reinhard Zumkeller, Nov 21 2006
a(n) = StirlingS2(n+1, 3) + StirlingS2(n+1, 2). - Ross La Haye, Jan 10 2008
a(n) = Sum_{k = 0..n} A106566(n, k)*A106233(k). - Philippe Deléham, Oct 30 2008
a(n) = 2*a(n-1) + 3*a(n-2) + 2, n > 1. - Gary Detlefs, Jun 21 2010
a(n) = 3*a(n-1) + a(n-2) - 3*a(n-3) = 5*a(n-1) - 7*a(n-2) + 3*a(n-3), a(0) = 0, a(1) = 1, a(2) = 4. Observation by G. Detlefs. See the W. Lang comment and link. - Wolfdieter Lang, Oct 18 2010
A008344(a(n)) = 0, for n > 1. - Reinhard Zumkeller, May 09 2012
A085059(a(n)) = 1 for n > 0. - Reinhard Zumkeller, Jan 31 2013
G.f.: Q(0)/2 where Q(k) = 1 - 1/(9^k - 3*x*81^k/(3*x*9^k - 1/(1 - 1/(3*9^k - 27*x*81^k/(9*x*9^k - 1/Q(k+1)))))); (continued fraction ). - Sergei N. Gladkovskii, Apr 12 2013
a(n) = A001065(3^n) where A001065(m) is the sum of the proper divisors of m for positive integer m. - Chayim Lowen, Mar 03 2015
a(n) = A000244(n) - A007051(n) = A007051(n)-1. - Yuchun Ji, Oct 23 2018
Sum_{n>=1} 1/a(n) = A321872. - Amiram Eldar, Nov 18 2020

Extensions

More terms from Michael Somos
Corrected my comment of Jan 10 2008. - Ross La Haye, Oct 29 2008
Removed comment that duplicated a formula. - Joerg Arndt, Mar 11 2010

A007283 a(n) = 3*2^n.

Original entry on oeis.org

3, 6, 12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144, 12288, 24576, 49152, 98304, 196608, 393216, 786432, 1572864, 3145728, 6291456, 12582912, 25165824, 50331648, 100663296, 201326592, 402653184, 805306368, 1610612736, 3221225472, 6442450944, 12884901888
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Same as Pisot sequences E(3, 6), L(3, 6), P(3, 6), T(3, 6). See A008776 for definitions of Pisot sequences.
Numbers k such that A006530(A000010(k)) = A000010(A006530(k)) = 2. - Labos Elemer, May 07 2002
Also least number m such that 2^n is the smallest proper divisor of m which is also a suffix of m in binary representation, see A080940. - Reinhard Zumkeller, Feb 25 2003
Length of the period of the sequence Fibonacci(k) (mod 2^(n+1)). - Benoit Cloitre, Mar 12 2003
The sequence of first differences is this sequence itself. - Alexandre Wajnberg and Eric Angelini, Sep 07 2005
Subsequence of A122132. - Reinhard Zumkeller, Aug 21 2006
Apart from the first term, a subsequence of A124509. - Reinhard Zumkeller, Nov 04 2006
Total number of Latin n-dimensional hypercubes (Latin polyhedra) of order 3. - Kenji Ohkuma (k-ookuma(AT)ipa.go.jp), Jan 10 2007
Number of different ternary hypercubes of dimension n. - Edwin Soedarmadji (edwin(AT)systems.caltech.edu), Dec 10 2005
For n >= 1, a(n) is equal to the number of functions f:{1, 2, ..., n + 1} -> {1, 2, 3} such that for fixed, different x_1, x_2,...,x_n in {1, 2, ..., n + 1} and fixed y_1, y_2,...,y_n in {1, 2, 3} we have f(x_i) <> y_i, (i = 1,2,...,n). - Milan Janjic, May 10 2007
a(n) written in base 2: 11, 110, 11000, 110000, ..., i.e.: 2 times 1, n times 0 (see A003953). - Jaroslav Krizek, Aug 17 2009
Subsequence of A051916. - Reinhard Zumkeller, Mar 20 2010
Numbers containing the number 3 in their Collatz trajectories. - Reinhard Zumkeller, Feb 20 2012
a(n-1) gives the number of ternary numbers with n digits with no two adjacent digits in common; e.g., for n=3 we have 010, 012, 020, 021, 101, 102, 120, 121, 201, 202, 210 and 212. - Jon Perry, Oct 10 2012
If n > 1, then a(n) is a solution for the equation sigma(x) + phi(x) = 3x-4. This equation also has solutions 84, 3348, 1450092, ... which are not of the form 3*2^n. - Farideh Firoozbakht, Nov 30 2013
a(n) is the upper bound for the "X-ray number" of any convex body in E^(n + 2), conjectured by Bezdek and Zamfirescu, and proved in the plane E^2 (see the paper by Bezdek and Zamfirescu). - L. Edson Jeffery, Jan 11 2014
If T is a topology on a set V of size n and T is not the discrete topology, then T has at most 3 * 2^(n-2) many open sets. See Brown and Stephen references. - Ross La Haye, Jan 19 2014
Comment from Charles Fefferman, courtesy of Doron Zeilberger, Dec 02 2014: (Start)
Fix a dimension n. For a real-valued function f defined on a finite set E in R^n, let Norm(f, E) denote the inf of the C^2 norms of all functions F on R^n that agree with f on E. Then there exist constants k and C depending only on the dimension n such that Norm(f, E) <= C*max{ Norm(f, S) }, where the max is taken over all k-point subsets S in E. Moreover, the best possible k is 3 * 2^(n-1).
The analogous result, with the same k, holds when the C^2 norm is replaced, e.g., by the C^1, alpha norm (0 < alpha <= 1). However, the optimal analogous k, e.g., for the C^3 norm is unknown.
For the above results, see Y. Brudnyi and P. Shvartsman (1994). (End)
Also, coordination sequence for (infinity, infinity, infinity) tiling of hyperbolic plane. - N. J. A. Sloane, Dec 29 2015
The average of consecutive powers of 2 beginning with 2^1. - Melvin Peralta and Miriam Ong Ante, May 14 2016
For n > 1, a(n) is the smallest Zumkeller number with n divisors that are also Zumkeller numbers (A083207). - Ivan N. Ianakiev, Dec 09 2016
Also, for n >= 2, the number of length-n strings over the alphabet {0,1,2,3} having only the single letters as nonempty palindromic subwords. (Corollary 21 in Fleischer and Shallit) - Jeffrey Shallit, Dec 02 2019
Also, a(n) is the minimum link-length of any covering trail, circuit, path, and cycle for the set of the 2^(n+2) vertices of an (n+2)-dimensional hypercube. - Marco Ripà, Aug 22 2022
The known fixed points of maps n -> A163511(n) and n -> A243071(n). [See comments in A163511]. - Antti Karttunen, Sep 06 2023
The finite subsequence a(3), a(4), a(5), a(6) = 24, 48, 96, 192 is one of only two geometric sequences that can be formed with all interior angles (all integer, in degrees) of a simple polygon. The other sequence is a subsequence of A000244 (see comment there). - Felix Huber, Feb 15 2024
A level 1 Sierpiński triangle is a triangle. Level n+1 is formed from three copies of level n by identifying pairs of corner vertices of each pair of triangles. For n>2, a(n-3) is the radius of the level n Sierpiński triangle graph. - Allan Bickle, Aug 03 2024

References

  • Jason I. Brown, Discrete Structures and Their Interactions, CRC Press, 2013, p. 71.
  • T. Ito, Method, equipment, program and storage media for producing tables, Publication number JP2004-272104A, Japan Patent Office (written in Japanese, a(2)=12, a(3)=24, a(4)=48, a(5)=96, a(6)=192, a(7)=384 (a(7)=284 was corrected)).
  • Kenji Ohkuma, Atsuhiro Yamagishi and Toru Ito, Cryptography Research Group Technical report, IT Security Center, Information-Technology Promotion Agency, JAPAN.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Coordination sequences for triangular tilings of hyperbolic space: A001630, A007283, A054886, A078042, A096231, A163876, A179070, A265057, A265058, A265059, A265060, A265061, A265062, A265063, A265064, A265065, A265066, A265067, A265068, A265069, A265070, A265071, A265072, A265073, A265074, A265075, A265076, A265077.
Subsequence of the following sequences: A029744, A029747, A029748, A029750, A362804 (after 3), A364494, A364496, A364289, A364291, A364292, A364295, A364497, A364964, A365422.
Essentially same as A003945 and A042950.
Row sums of (5, 1)-Pascal triangle A093562 and of (1, 5) Pascal triangle A096940.
Cf. A000079, A100540, A124508, A221718.
Cf. Latin squares: A000315, A002860, A003090, A040082, A003191; Latin cubes: A098843, A098846, A098679, A099321.
Cf. A133466, A225546, A163511, A243071.
Cf. A007283, A029858, A067771, A193277, A233774, A233775, A246959.

Programs

Formula

G.f.: 3/(1-2*x).
a(n) = 2*a(n - 1), n > 0; a(0) = 3.
a(n) = Sum_{k = 0..n} (-1)^(k reduced (mod 3))*binomial(n, k). - Benoit Cloitre, Aug 20 2002
a(n) = A118416(n + 1, 2) for n > 1. - Reinhard Zumkeller, Apr 27 2006
a(n) = A000079(n) + A000079(n + 1). - Zerinvary Lajos, May 12 2007
a(n) = A000079(n)*3. - Omar E. Pol, Dec 16 2008
From Paul Curtz, Feb 05 2009: (Start)
a(n) = b(n) + b(n+3) for b = A001045, A078008, A154879.
a(n) = abs(b(n) - b(n+3)) with b(n) = (-1)^n*A084247(n). (End)
a(n) = 2^n + 2^(n + 1). - Jaroslav Krizek, Aug 17 2009
a(n) = A173786(n + 1, n) = A173787(n + 2, n). - Reinhard Zumkeller, Feb 28 2010
A216022(a(n)) = 6 and A216059(a(n)) = 7, for n > 0. - Reinhard Zumkeller, Sep 01 2012
a(n) = (A000225(n) + 1)*3. - Martin Ettl, Nov 11 2012
E.g.f.: 3*exp(2*x). - Ilya Gutkovskiy, May 15 2016
A020651(a(n)) = 2. - Yosu Yurramendi, Jun 01 2016
a(n) = sqrt(A014551(n + 1)*A014551(n + 2) + A014551(n)^2). - Ezhilarasu Velayutham, Sep 01 2019
a(A048672(n)) = A225546(A133466(n)). - Michel Marcus and Peter Munn, Nov 29 2019
Sum_{n>=1} 1/a(n) = 2/3. - Amiram Eldar, Oct 28 2020

A000215 Fermat numbers: a(n) = 2^(2^n) + 1.

Original entry on oeis.org

3, 5, 17, 257, 65537, 4294967297, 18446744073709551617, 340282366920938463463374607431768211457, 115792089237316195423570985008687907853269984665640564039457584007913129639937
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

It is conjectured that just the first 5 numbers in this sequence are primes.
An infinite coprime sequence defined by recursion. - Michael Somos, Mar 14 2004
For n>0, Fermat numbers F(n) have digital roots 5 or 8 depending on whether n is even or odd (Koshy). - Lekraj Beedassy, Mar 17 2005
This is the special case k=2 of sequences with exact mutual k-residues. In general, a(1)=k+1 and a(n)=min{m | m>a(n-1), mod(m,a(i))=k, i=1,...,n-1}. k=1 gives Sylvester's sequence A000058. - Seppo Mustonen, Sep 04 2005
For n>1 final two digits of a(n) are periodically repeated with period 4: {17, 57, 37, 97}. - Alexander Adamchuk, Apr 07 2007
For 1 < k <= 2^n, a(A007814(k-1)) divides a(n) + 2^k. More generally, for any number k, let r = k mod 2^n and suppose r != 1, then a(A007814(r-1)) divides a(n) + 2^k. - T. D. Noe, Jul 12 2007
From Daniel Forgues, Jun 20 2011: (Start)
The Fermat numbers F_n are F_n(a,b) = a^(2^n) + b^(2^n) with a = 2 and b = 1.
For n >= 2, all factors of F_n = 2^(2^n) + 1 are of the form k*(2^(n+2)) + 1 (k >= 1).
The products of distinct Fermat numbers (in their binary representation, see A080176) give rows of Sierpiński's triangle (A006943). (End)
Let F(n) be a Fermat number. For n > 2, F(n) is prime if and only if 5^((F(n)-1)/4) == sqrt(F(n)-1) (mod F(n)). - Arkadiusz Wesolowski, Jul 16 2011
Conjecture: let the smallest prime factor of Fermat number F(n) be P(F(n)). If F(n) is composite, then P(F(n)) < 3*2^(2^n/2 - n - 2). - Arkadiusz Wesolowski, Aug 10 2012
The Fermat primes are not Brazilian numbers, so they belong to A220627, but the Fermat composites are Brazilian numbers so they belong to A220571. For a proof, see Proposition 3 page 36 on "Les nombres brésiliens" in Links. - Bernard Schott, Dec 29 2012
It appears that this sequence is generated by starting with a(0)=3 and following the rule "Write in binary and read in base 4". For an example of "Write in binary and read in ternary", see A014118. - John W. Layman, Jul 30 2013
Conjecture: the numbers > 5 in this sequence, i.e., 2^2^k + 1 for k>1, are exactly the numbers n such that (n-1)^4-1 divides 2^(n-1)-1. - M. F. Hasler, Jul 24 2015

Examples

			a(0) = 1*2^1 + 1 = 3 = 1*(2*1) + 1.
a(1) = 1*2^2 + 1 = 5 = 1*(2*2) + 1.
a(2) = 1*2^4 + 1 = 17 = 2*(2*4) + 1.
a(3) = 1*2^8 + 1 = 257 = 16*(2*8) + 1.
a(4) = 1*2^16 + 1 = 65537 = 2048*(2*16) + 1.
a(5) = 1*2^32 + 1 = 4294967297 = 641*6700417 = (10*(2*32) + 1)*(104694*(2*32) + 1).
a(6) = 1*2^64 + 1 = 18446744073709551617 = 274177*67280421310721 = (2142*(2*64) + 1)*(525628291490*(2*64) + 1).

References

  • M. Aigner and G. M. Ziegler, Proofs from The Book, Springer-Verlag, Berlin, 2nd. ed., 2001; see p. 3.
  • T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 7.
  • P. Bachmann, Niedere Zahlentheorie (1902, 1910), reprinted Chelsea, NY, 1968, vol. 2, p. 87.
  • James Gleick, Faster, Vintage Books, NY, 2000 (see pp. 259-261).
  • Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §3.2 Prime Numbers, pp. 78-79.
  • R. K. Guy, Unsolved Problems in Number Theory, A3.
  • G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 14.
  • E. Hille, Analytic Function Theory, Vol. I, Chelsea, N.Y., see p. 64.
  • T. Koshy, "The Digital Root Of A Fermat Number", Journal of Recreational Mathematics Vol. 32 No. 2 2002-3 Baywood NY.
  • M. Krizek, F. Luca & L. Somer, 17 Lectures on Fermat Numbers, Springer-Verlag NY 2001.
  • C. S. Ogilvy and J. T. Anderson, Excursions in Number Theory, Oxford University Press, NY, 1966, p. 36.
  • Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see pp. 18, 59.
  • C. A. Pickover, The Math Book, Sterling, NY, 2009; see p. 202.
  • Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See pp. 6-7, 70-75.
  • 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, pages 136-137.
  • David Wells, The Penguin Dictionary of Curious and Interesting Numbers, Penguin Books, 1987, pp. 148-149.

Links

Crossrefs

a(n) = A001146(n) + 1 = A051179(n) + 2.
Cf. A019434, A050922, A051158, A051179, A063486, A073617, A085866.
See A004249 for a similar sequence.
Cf. A080176 for binary representation of Fermat numbers.
Cf. A220627, A220570, A220571, A125134, A249119.
Cf. A000058, A000120, A000225, A006943, A007814, A014118, A077585, A242619, A242620, A257916, A257917.
Cf. A000058, A000120, A000225, A006943, A007814, A014118, A077585, A242619, A242620, A257916, A257917.

Programs

  • Haskell
    a000215 = (+ 1) . (2 ^) . (2 ^)  -- Reinhard Zumkeller, Feb 13 2015
  • Maple
    A000215 := n->2^(2^n)+1;
  • Mathematica
    Table[2^(2^n) + 1, {n, 0, 8}] (* Alonso del Arte, Jun 07 2011 *)
  • Maxima
    A000215(n):=2^(2^n)+1$ makelist(A000215(n),n,0,10); /* Martin Ettl, Dec 10 2012 */
  • PARI
    a(n)=if(n<1,3*(n==0),(a(n-1)-1)^2+1)
  • Python
    def a(n): return 2**(2**n) + 1
print([a(n) for n in range(9)]) # Michael S. Branicky, Apr 19 2021

Formula

a(0) = 3; a(n) = (a(n-1)-1)^2 + 1, n >= 1.
a(n) = a(n-1)*a(n-2)*...*a(1)*a(0) + 2, n >= 0, where for n = 0, we get the empty product, i.e., 1, plus 2, giving 3 = a(0). - Benoit Cloitre, Sep 15 2002 [edited by Daniel Forgues, Jun 20 2011]
The above formula implies that the Fermat numbers (being all odd) are coprime.
Conjecture: F is a Fermat prime if and only if phi(F-2) = (F-1)/2. - Benoit Cloitre, Sep 15 2002
A000120(a(n)) = 2. - Reinhard Zumkeller, Aug 07 2010
If a(n) is composite, then a(n) = A242619(n)^2 + A242620(n)^2 = A257916(n)^2 - A257917(n)^2. - Arkadiusz Wesolowski, May 13 2015
Sum_{n>=0} 1/a(n) = A051158. - Amiram Eldar, Oct 27 2020
From Amiram Eldar, Jan 28 2021: (Start)
Product_{n>=0} (1 + 1/a(n)) = A249119.
Product_{n>=0} (1 - 1/a(n)) = 1/2. (End)
a(n) = 2*A077585(n) + 3. - César Aguilera, Jul 26 2023
a(n) = 2*2^A000225(n) + 1. - César Aguilera, Jul 11 2024

A005187 a(n) = a(floor(n/2)) + n; also denominators in expansion of 1/sqrt(1-x) are 2^a(n); also 2n - number of 1's in binary expansion of 2n.

Original entry on oeis.org

0, 1, 3, 4, 7, 8, 10, 11, 15, 16, 18, 19, 22, 23, 25, 26, 31, 32, 34, 35, 38, 39, 41, 42, 46, 47, 49, 50, 53, 54, 56, 57, 63, 64, 66, 67, 70, 71, 73, 74, 78, 79, 81, 82, 85, 86, 88, 89, 94, 95, 97, 98, 101, 102, 104, 105, 109, 110, 112, 113, 116, 117, 119, 120, 127, 128
Offset: 0

Views

Author

N. J. A. Sloane, May 20 1991; Allan Wilks, Dec 11 1999

Keywords

Comments

Also exponent of the largest power of 2 dividing (2n)! (A010050) and (2n)!! (A000165).
Write n in binary: 1ab..yz, then a(n) = 1ab..yz + ... + 1ab + 1a + 1. - Ralf Stephan, Aug 27 2003
Also numbers having a partition into distinct Mersenne numbers > 0; A079559(a(n))=1; complement of A055938. - Reinhard Zumkeller, Mar 18 2009
Wikipedia's article on the "Whitney Immersion theorem" mentions that the a(n)-dimensional sphere arises in the Immersion Conjecture proved by Ralph Cohen in 1985. - Jonathan Vos Post, Jan 25 2010
For n > 0, denominators for consecutive pairs of integral numerator polynomials L(n+1,x) for the Legendre polynomials with o.g.f. 1 / sqrt(1-tx+x^2). - Tom Copeland, Feb 04 2016
a(n) is the total number of pointers in the first n elements of a perfect skip list. - Alois P. Heinz, Dec 14 2017
a(n) is the position of the n-th a (indexing from 0) in the fixed point of the morphism a -> aab, b -> b. - Jeffrey Shallit, Dec 24 2020
Numbers that can be expressed as the sum of distinct numbers of the form 2^k - 1 (lenient Mersenne numbers, A000225). This follows from the 2N - Hamming weight definition. A corollary is that these are the numbers with no 2 in their skew-binary representation (cf. A169683). - Allan C. Wechsler, Feb 25 2025

Examples

			G.f. = x + 3*x^2 + 4*x^3 + 7*x^4 + 8*x^5 + 10*x^6 + 11*x^7 + 15*x^8 + ...

References

  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A001790, A011371, A067080, A098844, A132027, A004128, A054899, A046161.
Cf. A001511 (first differences), A122247 (partial sums), A055938 (complement).
Cf. A004134, A010050, A000165.
Cf. A000120, A079559, A085354, A030308, A000225.

Programs

  • Haskell
    a005187 n = a005187_list !! n
a005187_list = 0 : zipWith (+) [1..] (map (a005187 . (`div` 2)) [1..])
-- Reinhard Zumkeller, Nov 07 2011, Oct 05 2011
  • Magma
    [n + Valuation(Factorial(n), 2): n in [0..70]]; // Vincenzo Librandi, Jun 11 2019
  • Maple
    A005187 := n -> 2*n - add(i, i=convert(n, base, 2)):
seq(A005187(n), n=0..65); # Peter Luschny, Apr 08 2014
  • Mathematica
    a[0] = 0; a[n_] := a[n] = a[Floor[n/2]] + n; Table[ a[n], {n, 0, 50}] (* or *)
Table[IntegerExponent[(2n)!, 2], {n, 0, 65}] (* Robert G. Wilson v, Apr 19 2006 *)
Table[2n-DigitCount[2n,2,1],{n,0,70}] (* Harvey P. Dale, May 24 2014 *)
  • PARI
    {a(n) = if( n<0, 0, valuation((2*n)!, 2))}; /* Michael Somos, Oct 24 2002 */
  • PARI
    {a(n) = if( n<0, 0, sum(k=1, n, (2*n)\2^k))}; /* Michael Somos, Oct 24 2002 */
  • PARI
    {a(n) = if( n<0, 0, 2*n - subst( Pol( binary( n ) ), x, 1) ) }; /* Michael Somos, Aug 28 2007 */
  • PARI
    a(n)=my(s=n);while(n>>=1,s+=n);s \\ Charles R Greathouse IV, Apr 07 2012
  • PARI
    a(n)=2*n-hammingweight(n) \\ Charles R Greathouse IV, Jan 07 2013
  • Python
    def A005187(n): return 2*n-bin(n).count('1') # Chai Wah Wu, Jun 03 2021
  • Sage
    @CachedFunction
def A005187(n): return A005187(n//2) + n if n > 0 else 0
[A005187(n) for n in range(66)]  # Peter Luschny, Dec 13 2012

Formula

a(n) = A011371(2n+1) = A011371(n) + n, n >= 0.
A046161(n) = 2^a(n).
For m>0, let q = floor(log_2(m)); a(2m+1) = 2^q + 3m + Sum_{k>=1} floor((m-2^q)/2^k); a(2m) = a(2m+1) - 1. - Len Smiley
a(n) = Sum_{k >= 0} floor(n/2^k) = n + A011371(n). - Henry Bottomley, Jul 03 2001
G.f.: A(x) = Sum_{k>=0} x^(2^k)/((1-x)*(1-x^(2^k))). - Ralf Stephan, Dec 24 2002
a(n) = Sum_{k=1..n} A001511(k), sum of binary Hamming distances between consecutive integers up to n. - Gary W. Adamson, Jun 15 2003
Conjecture: a(n) = 2n + O(log(n)). - Benoit Cloitre, Oct 07 2003 [true as a(n) = 2*n - hamming_weight(2*n). Joerg Arndt, Jun 10 2019]
Sum_{n=2^k..2^(k+1)-1} a(n) = 3*4^k - (k+4)*2^(k-1) = A085354(k). - Philippe Deléham, Feb 19 2004
From Hieronymus Fischer, Aug 14 2007: (Start)
Recurrence: a(n) = n + a(floor(n/2)); a(2n) = 2n + a(n); a(n*2^m) = 2*n*(2^m-1) + a(n).
a(2^m) = 2^(m+1) - 1, m >= 0.
Asymptotic behavior: a(n) = 2n + O(log(n)), a(n+1) - a(n) = O(log(n)); this follows from the inequalities below.
a(n) <= 2n-1; equality holds for powers of 2.
a(n) >= 2n-1-floor(log_2(n)); equality holds for n = 2^m-1, m > 0.
lim inf (2n - a(n)) = 1, for n-->oo.
lim sup (2n - log_2(n) - a(n)) = 0, for n-->oo.
lim sup (a(n+1) - a(n) - log_2(n)) = 1, for n-->oo. (End)
a(n) = 2n - A000120(n). - Paul Barry, Oct 26 2007
PURRS demo results: Bounds for a(n) = n + a(n/2) with initial conditions a(1) = 1: a(n) >= -2 + 2*n - log(n)*log(2)^(-1), a(n) <= 1 + 2*n for each n >= 1. - Alexander R. Povolotsky, Apr 06 2008
If n = 2^a_1 + 2^a_2 + ... + 2^a_k, then a(n) = n-k. This can be used to prove that 2^n maximally divides (2n!)/n!. - Jon Perry, Jul 16 2009
a(n) = Sum_{k>=0} A030308(n,k)*A000225(k+1). - Philippe Deléham, Oct 16 2011
a(n) = log_2(denominator(binomial(-1/2,n))). - Peter Luschny, Nov 25 2011
a(2n+1) = a(2n) + 1. - M. F. Hasler, Jan 24 2015
a(n) = A004134(n) - n. - Cyril Damamme, Aug 04 2015
G.f.: (1/(1 - x))*Sum_{k>=0} (2^(k+1) - 1)*x^(2^k)/(1 + x^(2^k)). - Ilya Gutkovskiy, Jul 23 2017

A000295 Eulerian numbers (Euler's triangle: column k=2 of A008292, column k=1 of A173018).

Original entry on oeis.org

0, 0, 1, 4, 11, 26, 57, 120, 247, 502, 1013, 2036, 4083, 8178, 16369, 32752, 65519, 131054, 262125, 524268, 1048555, 2097130, 4194281, 8388584, 16777191, 33554406, 67108837, 134217700, 268435427, 536870882, 1073741793, 2147483616, 4294967263, 8589934558
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

There are 2 versions of Euler's triangle:
* A008292 Classic version of Euler's triangle used by Comtet (1974).
* A173018 Version of Euler's triangle used by Graham, Knuth and Patashnik in Concrete Math. (1990).
Euler's triangle rows and columns indexing conventions:
* A008292 The rows and columns of the Eulerian triangle are both indexed starting from 1. (Classic version: used in the classic books by Riordan and Comtet.)
* A173018 The rows and columns of the Eulerian triangle are both indexed starting from 0. (Graham et al.)
Number of Dyck paths of semilength n having exactly one long ascent (i.e., ascent of length at least two). Example: a(4)=11 because among the 14 Dyck paths of semilength 4, the paths that do not have exactly one long ascent are UDUDUDUD (no long ascent), UUDDUUDD and UUDUUDDD (two long ascents). Here U=(1,1) and D=(1,-1). Also number of ordered trees with n edges having exactly one branch node (i.e., vertex of outdegree at least two). - Emeric Deutsch, Feb 22 2004
Number of permutations of {1,2,...,n} with exactly one descent (i.e., permutations (p(1),p(2),...,p(n)) such that #{i: p(i)>p(i+1)}=1). E.g., a(3)=4 because the permutations of {1,2,3} with one descent are 132, 213, 231 and 312.
a(n+1) is the convolution of nonnegative integers (A001477) and powers of two (A000079). - Graeme McRae, Jun 07 2006
Partial sum of main diagonal of A125127. - Jonathan Vos Post, Nov 22 2006
Number of partitions of an n-set having exactly one block of size > 1. Example: a(4)=11 because, if the partitioned set is {1,2,3,4}, then we have 1234, 123|4, 124|3, 134|2, 1|234, 12|3|4, 13|2|4, 14|2|3, 1|23|4, 1|24|3 and 1|2|34. - Emeric Deutsch, Oct 28 2006
k divides a(k+1) for k in A014741. - Alexander Adamchuk, Nov 03 2006
(Number of permutations avoiding patterns 321, 2413, 3412, 21534) minus one. - Jean-Luc Baril, Nov 01 2007, Mar 21 2008
The chromatic invariant of the prism graph P_n for n >= 3. - Jonathan Vos Post, Aug 29 2008
Decimal integer corresponding to the result of XORing the binary representation of 2^n - 1 and the binary representation of n with leading zeros. This sequence and a few others are syntactically similar. For n > 0, let D(n) denote the decimal integer corresponding to the binary number having n consecutive 1's. Then D(n).OP.n represents the n-th term of a sequence when .OP. stands for a binary operator such as '+', '-', '*', 'quotentof', 'mod', 'choose'. We then get the various sequences A136556, A082495, A082482, A066524, A000295, A052944. Another syntactically similar sequence results when we take the n-th term as f(D(n)).OP.f(n). For example if f='factorial' and .OP.='/', we get (A136556)(A000295) ; if f='squaring' and .OP.='-', we get (A000295)(A052944). - K.V.Iyer, Mar 30 2009
Chromatic invariant of the prism graph Y_n.
Number of labelings of a full binary tree of height n-1, such that each path from root to any leaf contains each label from {1,2,...,n-1} exactly once. - Michael Vielhaber (vielhaber(AT)gmail.com), Nov 18 2009
Also number of nontrivial equivalence classes generated by the weak associative law X((YZ)T)=(X(YZ))T on words with n open and n closed parentheses. Also the number of join (resp. meet)-irreducible elements in the pruning-grafting lattice of binary trees with n leaves. - Jean Pallo, Jan 08 2010
Nonzero terms of this sequence can be found from the row sums of the third sub-triangle extracted from Pascal's triangle as indicated below by braces:
1;
1, 1;
{1}, 2, 1;
{1, 3}, 3, 1;
{1, 4, 6}, 4, 1;
{1, 5, 10, 10}, 5, 1;
{1, 6, 15, 20, 15}, 6, 1;
... - L. Edson Jeffery, Dec 28 2011
For integers a, b, denote by a<+>b the least c >= a, such that the Hamming distance D(a,c) = b (note that, generally speaking, a<+>b differs from b<+>a). Then for n >= 3, a(n) = n<+>n. This has a simple explanation: for n >= 3 in binary we have a(n) = (2^n-1)-n = "anti n". - Vladimir Shevelev, Feb 14 2012
a(n) is the number of binary sequences of length n having at least one pair 01. - Branko Curgus, May 23 2012
Nonzero terms are those integers k for which there exists a perfect (Hamming) error-correcting code. - L. Edson Jeffery, Nov 28 2012
a(n) is the number of length n binary words constructed in the following manner: Select two positions in which to place the first two 0's of the word. Fill in all (possibly none) of the positions before the second 0 with 1's and then complete the word with an arbitrary string of 0's or 1's. So a(n) = Sum_{k=2..n} (k-1)*2^(n-k). - Geoffrey Critzer, Dec 12 2013
Without first 0: a(n)/2^n equals Sum_{k=0..n} k/2^k. For example: a(5)=57, 57/32 = 0/1 + 1/2 + 2/4 + 3/8 + 4/16 + 5/32. - Bob Selcoe, Feb 25 2014
The first barycentric coordinate of the centroid of the first n rows of Pascal's triangle, assuming the numbers are weights, is A000295(n+1)/A000337(n). See attached figure. - César Eliud Lozada, Nov 14 2014
Starting (0, 1, 4, 11, ...), this is the binomial transform of (0, 1, 2, 2, 2, ...). - Gary W. Adamson, Jul 27 2015
Also the number of (non-null) connected induced subgraphs in the n-triangular honeycomb rook graph. - Eric W. Weisstein, Aug 27 2017
a(n) is the number of swaps needed in the worst case to transform a binary tree with n full levels into a heap, using (bottom-up) heapify. - Rudy van Vliet, Sep 19 2017
The utility of large networks, particularly social networks, with n participants is given by the terms a(n) of this sequence. This assertion is known as Reed's Law, see the Wikipedia link. - Johannes W. Meijer, Jun 03 2019
a(n-1) is the number of subsets of {1..n} in which the largest element of the set exceeds by at least 2 the next largest element. For example, for n = 5, a(4) = 11 and the 11 sets are {1,3}, {1,4}, {1,5}, {2,4}, {2,5}, {3,5}, {1,2,4}, {1,2,5}, {1,3,5}, {2,3,5}, {1,2,3,5}. - Enrique Navarrete, Apr 08 2020
a(n-1) is also the number of subsets of {1..n} in which the second smallest element of the set exceeds by at least 2 the smallest element. For example, for n = 5, a(4) = 11 and the 11 sets are {1,3}, {1,4}, {1,5}, {2,4}, {2,5}, {3,5}, {1,3,4}, {1,3,5}, {1,4,5}, {2,4,5}, {1,3,4,5}. - Enrique Navarrete, Apr 09 2020
a(n+1) is the sum of the smallest elements of all subsets of {1..n}. For example, for n=3, a(4)=11; the subsets of {1,2,3} are {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}, and the sum of smallest elements is 11. - Enrique Navarrete, Aug 20 2020
Number of subsets of an n-set that have more than one element. - Eric M. Schmidt, Mar 13 2021
Number of individual bets in a "full cover" bet on n-1 horses, dogs, etc. in different races. Each horse, etc. can be bet on or not, giving 2^n bets. But, by convention, singles (a bet on only one race) are not included, reducing the total number bets by n. It is also impossible to bet on no horses at all, reducing the number of bets by another 1. A full cover on 4 horses, dogs, etc. is therefore 6 doubles, 4 trebles and 1 four-horse etc. accumulator. In British betting, such a bet on 4 horses etc. is a Yankee; on 5, a super-Yankee. - Paul Duckett, Nov 17 2021
From Enrique Navarrete, May 25 2022: (Start)
Number of binary sequences of length n with at least two 1's.
a(n-1) is the number of ways to choose an odd number of elements greater than or equal to 3 out of n elements.
a(n+1) is the number of ways to split [n] = {1,2,...,n} into two (possibly empty) complementary intervals {1,2,...,i} and {i+1,i+2,...,n} and then select a subset from the first interval (2^i choices, 0 <= i <= n), and one block/cell (i.e., subinterval) from the second interval (n-i choices, 0 <= i <= n).
(End)
Number of possible conjunctions in a system of n planets; for example, there can be 0 conjunctions with one planet, one with two planets, four with three planets (three pairs of planets plus one with all three) and so on. - Wendy Appleby, Jan 02 2023
Largest exponent m such that 2^m divides (2^n-1)!. - Franz Vrabec, Aug 18 2023
It seems that a(n-1) is the number of odd r with 0 < r < 2^n for which there exist u,v,w in the x-independent beginning of the Collatz trajectory of 2^n x + r with u+v = w+1, as detailed in the link "Collatz iteration and Euler numbers?". A better understanding of this might also give a formula for A374527. - Markus Sigg, Aug 02 2024
This sequence has a connection to consecutively halved positional voting (CHPV); see Mendenhall and Switkay. - Hal M. Switkay, Feb 25 2025
a(n) is the number of subsets of size 2 and more of an n-element set. Equivalently, a(n) is the number of (hyper)edges of size 2 and more in a complete hypergraph of n vertices. - Yigit Oktar, Apr 05 2025

Examples

			G.f. = x^2 + 4*x^3 + 11*x^4 + 26*x^5 + 57*x^6 + 120*x^7 + 247*x^8 + 502*x^9 + ...

References

  • O. Bottema, Problem #562, Nieuw Archief voor Wiskunde, 28 (1980) 115.
  • L. Comtet, "Permutations by Number of Rises; Eulerian Numbers." Section 6.5 in Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, pp. 51 and 240-246, 1974.
  • F. N. David and D. E. Barton, Combinatorial Chance. Hafner, NY, 1962, p. 151.
  • R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990.
  • D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, p. 34.
  • J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 215.
  • 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

Cf. A008292 (classic version of Euler's triangle used by Comtet (1974)).
Cf. A173018 (version of Euler's triangle used by Graham, Knuth and Patashnik in Concrete Math. (1990)).
Cf. A002662 (partial sums).
Partial sums of A000225.
Row sums of A014473 and of A143291.
Second column of triangles A112493 and A112500.
Sequences A125128 and A130103 are essentially the same.
Column k=1 of A124324.
Cf. A000079, A000108, A000217, A000325, A000975, A001511, A002663.
Cf. A002664, A007814, A008292, A008949, A014741, A016031, A028366.
Cf. A035039, A035040, A035041, A035042, A079583, A107907, A130321.
Cf. A130128, A130330, A131768, A131816.

Programs

  • Haskell
    a000295 n = 2^n - n - 1  -- Reinhard Zumkeller, Nov 25 2013
  • Magma
    [2^n-n-1: n in [0..40]]; // Vincenzo Librandi, Jul 29 2015
  • Magma
    [EulerianNumber(n, 1): n in [0..40]]; // G. C. Greubel, Oct 02 2024
  • Maple
    [ seq(2^n-n-1, n=1..50) ];
A000295 := -z/(2*z-1)/(z-1)**2; # Simon Plouffe in his 1992 dissertation
# Grammar specification:
spec := [S, { B = Set(Z, 1 <= card), C = Sequence(B, 2 <= card), S = Prod(B, C) }, unlabeled]:
struct := n -> combstruct[count](spec, size = n+1);
seq(struct(n), n = 0..33); # Peter Luschny, Jul 22 2014
  • Mathematica
    a[n_] = If[n==0, 0, n*(HypergeometricPFQ[{1, 1-n}, {2}, -1] - 1)];
Table[a[n], {n,0,40}] (* Olivier Gérard, Mar 29 2011 *)
LinearRecurrence[{4, -5, 2}, {0, 0, 1}, 40] (* Vincenzo Librandi, Jul 29 2015 *)
Table[2^n -n-1, {n,0,40}] (* Eric W. Weisstein, Nov 16 2017 *)
  • PARI
    a(n)=2^n-n-1 \\ Charles R Greathouse IV, Jun 10 2011
  • SageMath
    [2^n -(n+1) for n in range(41)] # G. C. Greubel, Oct 02 2024

Formula

a(n) = 2^n - n - 1.
G.f.: x^2/((1-2*x)*(1-x)^2).
A107907(a(n+2)) = A000079(n+2). - Reinhard Zumkeller, May 28 2005
E.g.f.: exp(x)*(exp(x)-1-x). - Emeric Deutsch, Oct 28 2006
a(0)=0, a(1)=0, a(n) = 3*a(n-1) - 2*a(n-2) + 1. - Miklos Kristof, Mar 09 2005
a(0)=0, a(n) = 2*a(n-1) + n - 1 for all n in Z.
a(n) = Sum_{k=2..n} binomial(n, k). - Paul Barry, Jun 05 2003
a(n+1) = Sum_{i=1..n} Sum_{j=1..i} C(i, j). - Benoit Cloitre, Sep 07 2003
a(n+1) = 2^n*Sum_{k=0..n} k/2^k. - Benoit Cloitre, Oct 26 2003
a(0)=0, a(1)=0, a(n) = Sum_{i=0..n-1} i+a(i) for i > 1. - Gerald McGarvey, Jun 12 2004
a(n+1) = Sum_{k=0..n} (n-k)*2^k. - Paul Barry, Jul 29 2004
a(n) = Sum_{k=0..n} binomial(n, k+2); a(n+2) = Sum_{k=0..n} binomial(n+2, k+2). - Paul Barry, Aug 23 2004
a(n) = Sum_{k=0..floor((n-1)/2)} binomial(n-k-1, k+1)*2^(n-k-2)*(-1/2)^k. - Paul Barry, Oct 25 2004
a(0) = 0; a(n) = Stirling2(n,2) + a(n-1) = A000225(n-1) + a(n-1). - Thomas Wieder, Feb 18 2007
a(n) = A000325(n) - 1. - Jonathan Vos Post, Aug 29 2008
a(0) = 0, a(n) = Sum_{k=0..n-1} 2^k - 1. - Doug Bell, Jan 19 2009
a(n) = A000217(n-1) + A002662(n) for n>0. - Geoffrey Critzer, Feb 11 2009
a(n) = A000225(n) - n. - Zerinvary Lajos, May 29 2009
a(n) = n*(2F1([1,1-n],[2],-1) - 1). - Olivier Gérard, Mar 29 2011
Column k=1 of A173018 starts a'(n) = 0, 1, 4, 11, ... and has the hypergeometric representation n*hypergeom([1, -n+1], [-n], 2). This can be seen as a formal argument to prefer Euler's A173018 over A008292. - Peter Luschny, Sep 19 2014
E.g.f.: exp(x)*(exp(x)-1-x); this is U(0) where U(k) = 1 - x/(2^k - 2^k/(x + 1 - x^2*2^(k+1)/(x*2^(k+1) - (k+1)/U(k+1)))); (continued fraction, 3rd kind, 4-step). - Sergei N. Gladkovskii, Dec 01 2012
a(n) = A079583(n) - A000225(n+1). - Miquel Cerda, Dec 25 2016
a(0) = 0; a(1) = 0; for n > 1: a(n) = Sum_{i=1..2^(n-1)-1} A001511(i). - David Siegers, Feb 26 2019
a(n) = A007814(A028366(n)). - Franz Vrabec, Aug 18 2023
a(n) = Sum_{k=1..floor((n+1)/2)} binomial(n+1, 2*k+1). - Taras Goy, Jan 02 2025

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

A040000 a(0)=1; a(n)=2 for n >= 1.

Original entry on oeis.org

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

Views

Author

N. J. A. Sloane, Dec 11 1999

Keywords

Comments

Continued fraction expansion of sqrt(2) is 1 + 1/(2 + 1/(2 + 1/(2 + ...))).
Inverse binomial transform of Mersenne numbers A000225(n+1) = 2^(n+1) - 1. - Paul Barry, Feb 28 2003
A Chebyshev transform of 2^n: if A(x) is the g.f. of a sequence, map it to ((1-x^2)/(1+x^2))A(x/(1+x^2)). - Paul Barry, Oct 31 2004
An inverse Catalan transform of A068875 under the mapping g(x)->g(x(1-x)). A068875 can be retrieved using the mapping g(x)->g(xc(x)), where c(x) is the g.f. of A000108. A040000 and A068875 may be described as a Catalan pair. - Paul Barry, Nov 14 2004
Sequence of electron arrangement in the 1s 2s and 3s atomic subshells. Cf. A001105, A016825. - Jeremy Gardiner, Dec 19 2004
Binomial transform of A165326. - Philippe Deléham, Sep 16 2009
Let m=2. We observe that a(n) = Sum_{k=0..floor(n/2)} binomial(m,n-2*k). Then there is a link with A113311 and A115291: it is the same formula with respectively m=3 and m=4. We can generalize this result with the sequence whose g.f. is given by (1+z)^(m-1)/(1-z). - Richard Choulet, Dec 08 2009
With offset 1: number of permutations where |p(i) - p(i+1)| <= 1 for n=1,2,...,n-1. This is the identical permutation and (for n>1) its reversal.
Equals INVERT transform of bar(1, 1, -1, -1, ...).
Eventual period is (2). - Zak Seidov, Mar 05 2011
Also decimal expansion of 11/90. - Vincenzo Librandi, Sep 24 2011
a(n) = 3 - A054977(n); right edge of the triangle in A182579. - Reinhard Zumkeller, May 07 2012
With offset 1: minimum cardinality of the range of a periodic sequence with (least) period n. Of course the range's maximum cardinality for a purely periodic sequence with (least) period n is n. - Rick L. Shepherd, Dec 08 2014
With offset 1: n*a(1) + (n-1)*a(2) + ... + 2*a(n-1) + a(n) = n^2. - Warren Breslow, Dec 12 2014
With offset 1: decimal expansion of gamma(4) = 11/9 where gamma(n) = Cp(n)/Cv(n) is the n-th Poisson's constant. For the definition of Cp and Cv see A272002. - Natan Arie Consigli, Sep 11 2016
a(n) equals the number of binary sequences of length n where no two consecutive terms differ. Also equals the number of binary sequences of length n where no two consecutive terms are the same. - David Nacin, May 31 2017
a(n) is the period of the continued fractions for sqrt((n+2)/(n+1)) and sqrt((n+1)/(n+2)). - A.H.M. Smeets, Dec 05 2017
Also, number of self-avoiding walks and coordination sequence for the one-dimensional lattice Z. - Sean A. Irvine, Jul 27 2020

Examples

			sqrt(2) = 1.41421356237309504... = 1 + 1/(2 + 1/(2 + 1/(2 + 1/(2 + ...)))). - _Harry J. Smith_, Apr 21 2009
G.f. = 1 + 2*x + 2*x^2 + 2*x^3 + 2*x^4 + 2*x^5 + 2*x^6 + 2*x^7 + 2*x^8 + ...
11/90 = 0.1222222222222222222... - _Natan Arie Consigli_, Sep 11 2016

References

  • A. Beiser, Concepts of Modern Physics, 2nd Ed., McGraw-Hill, 1973.
  • John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See p. 186.
  • Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §4.4 Powers and Roots, p. 144.
  • James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 276-278.

Links

Crossrefs

Convolution square is A008574.
See A003945 etc. for (1+x)/(1-k*x).
From Jaume Oliver Lafont, Mar 26 2009: (Start)
Sum_{0<=k<=n} a(k) = A005408(n).
Prod_{0<=k<=n} a(k) = A000079(n). (End)
Cf. A113311, A115291, A171418, A171440, A171441, A171442, A171443.
Cf. A000674 (boustrophedon transform).
Cf. A001333/A000129 (continued fraction convergents).
Cf. A000122, A002193 (sqrt(2) decimal expansion), A006487 (Egyptian fraction).
Cf. Other continued fractions for sqrt(a^2+1) = (a, 2a, 2a, 2a....): A040002 (contfrac(sqrt(5)) = (2,4,4,...)), A040006, A040012, A040020, A040030, A040042, A040056, A040072, A040090, A040110 (contfrac(sqrt(122)) = (11,22,22,...)), A040132, A040156, A040182, A040210, A040240, A040272, A040306, A040342, A040380, A040420 (contfrac(sqrt(442)) = (21,42,42,...)), A040462, A040506, A040552, A040600, A040650, A040702, A040756, A040812, A040870, A040930 (contfrac(sqrt(962)) = (31,62,62,...)).

Programs

  • Haskell
    a040000 0 = 1; a040000 n = 2
a040000_list = 1 : repeat 2  -- Reinhard Zumkeller, May 07 2012
  • Maple
    Digits := 100: convert(evalf(sqrt(2)),confrac,90,'cvgts'):
  • Mathematica
    ContinuedFraction[Sqrt[2],300] (* Vladimir Joseph Stephan Orlovsky, Mar 04 2011 *)
a[ n_] := 2 - Boole[n == 0]; (* Michael Somos, Dec 28 2014 *)
PadRight[{1},120,2] (* or *) RealDigits[11/90, 10, 120][[1]] (* Harvey P. Dale, Jul 12 2025 *)
  • PARI
    {a(n) = 2-!n}; /* Michael Somos, Apr 16 2007 */
  • PARI
    a(n)=1+sign(n)  \\ Jaume Oliver Lafont, Mar 26 2009
  • PARI
    allocatemem(932245000); default(realprecision, 21000); x=contfrac(sqrt(2)); for (n=0, 20000, write("b040000.txt", n, " ", x[n+1]));  \\ Harry J. Smith, Apr 21 2009

Formula

G.f.: (1+x)/(1-x). - Paul Barry, Feb 28 2003
a(n) = 2 - 0^n; a(n) = Sum_{k=0..n} binomial(1, k). - Paul Barry, Oct 16 2004
a(n) = n*Sum_{k=0..floor(n/2)} (-1)^k*binomial(n-k, k)*2^(n-2*k)/(n-k). - Paul Barry, Oct 31 2004
A040000(n) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*(-1)^k*A068875(n-k). - Paul Barry, Nov 14 2004
From Michael Somos, Apr 16 2007: (Start)
Euler transform of length 2 sequence [2, -1].
G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^4)) where f(u, v, w) = (u-v)*(u+v) - 2*v*(u-w).
E.g.f.: 2*exp(x) - 1.
a(n) = a(-n) for all n in Z (one possible extension to n<0). (End)
G.f.: (1-x^2)/(1-x)^2. - Jaume Oliver Lafont, Mar 26 2009
G.f.: exp(2*atanh(x)). - Jaume Oliver Lafont, Oct 20 2009
a(n) = Sum_{k=0..n} A108561(n,k)*(-1)^k. - Philippe Deléham, Nov 17 2013
a(n) = 1 + sign(n). - Wesley Ivan Hurt, Apr 16 2014
10 * 11/90 = 11/9 = (11/2 R)/(9/2 R) = Cp(4)/Cv(4) = A272005/A272004, with R = A081822 (or A070064). - Natan Arie Consigli, Sep 11 2016
a(n) = A001227(A000040(n+1)). - Omar E. Pol, Feb 28 2018

A002326 Multiplicative order of 2 mod 2n+1.

Original entry on oeis.org

1, 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 28, 5, 10, 12, 36, 12, 20, 14, 12, 23, 21, 8, 52, 20, 18, 58, 60, 6, 12, 66, 22, 35, 9, 20, 30, 39, 54, 82, 8, 28, 11, 12, 10, 36, 48, 30, 100, 51, 12, 106, 36, 36, 28, 44, 12, 24, 110, 20, 100, 7, 14, 130, 18, 36, 68, 138, 46, 60, 28
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

In other words, least m > 0 such that 2n+1 divides 2^m-1.
Number of riffle shuffles of 2n+2 cards required to return a deck to initial state. A riffle shuffle replaces a list s(1), s(2), ..., s(m) with s(1), s((i/2)+1), s(2), s((i/2)+2), ... a(1) = 2 because a riffle shuffle of [1, 2, 3, 4] requires 2 iterations [1, 2, 3, 4] -> [1, 3, 2, 4] -> [1, 2, 3, 4] to restore the original order.
Concerning the complexity of computing this sequence, see for example Bach and Shallit, p. 115, exercise 8.
It is not difficult to prove that if 2n+1 is a prime then 2n is a multiple of a(n). But the converse is not true. Indeed, one can prove that a(2^(2t-1))=4t. Thus if n=2^(2t-1), where, for any m > 0, t=2^(m-1) then 2n is a multiple of a(n) while 2n+1 is a Fermat number which, as is well known, is not always a prime. It is an interesting problem to describe all composite numbers for which 2n is divisible by a(n). - Vladimir Shevelev, May 09 2008
For an algorithm of calculation of a(n) see author's comment in A179680. - Vladimir Shevelev, Jul 21 2010
From V. Raman, Sep 18 2012, Dec 10 2012: (Start)
If 2n+1 is prime, then the polynomial (x^(2n+1)+1)/(x+1) factors into 2n/a(n) polynomials of the same degree a(n) over GF(2).
If (x^(2n+1)+1)/(x+1) is irreducible over GF(2), then 2n+1 is prime, and 2 is a primitive root (mod 2n+1) (cf. A001122).
For all n > 0, a(n) is the degree of the largest irreducible polynomial factor for the polynomial (x^(2n+1)+1)/(x+1) over GF(2). (End)
a(n) is a factor of phi(2n+1) (A000010(2n+1)). - Douglas Boffey, Oct 21 2013
Conjecture: if p is an odd prime then a((p^3-1)/2) = p * a((p^2-1)/2). Because otherwise a((p^3-1)/2) < p * a((p^2-1)/2) iff a((p^3-1)/2) = a((p-1)/2) for a prime p. Equivalently p^3 divides 2^(p-1)-1, but no such prime p is known. - Thomas Ordowski, Feb 10 2014
A generalization of the previous conjecture: For each k>=2, if p is an odd prime then a(((p^(k+1))-1)/2) = p * a((p^k-1)/2). Computer testing of this generalized conjecture shows that there is no counterexample for k and p both up to 1000. - Ahmad J. Masad, Oct 17 2020
a(n) = a((N-1)/2), with odd N = 2*n+1 >= 3 (n >= 1), is also the primitive period length of (1/N) in binary notation: (1/N)2 = 0.repeat(a[1]a[2]...a[P(N)]), and P(N) = a((N-1)/2). E.g., N = 11 (n = 5), (1/11)_2 = 0.repeat(0001011101), with P(11) = 10 = a(5). Proof: Use a cyclic shift operation sigma (1 step to the left) on the cycle: sigma((1/N)_2) = .repeat(a[2]...a[P(N)]a[1]). Then one can prove for the composition sigma^[k] (k=0 is the identity map) written back in decimal notation the result (sigma^[k]((1/N)_2))_10 = (1/N)*2^k (mod N). E.g. N = 11, sigma^[2]((1/11)_2) = .repeat(0101110100), written in base 10 as 4/11, etc. Hence P(N) and the order of 2 modulo N coincide. - _Gary W. Adamson and Wolfdieter Lang, Oct 14 2020

Examples

			From _Vladimir Shevelev_, Oct 03 2017: (Start)
Our algorithm for the calculation of a(n) in the author's comment in A179680 (see also the Sage program below) could be represented in the form of a "finite continued fraction". For example let n = 8, 2*n+1 = 17. We have
    1 + 17
    ------- + 17
       2
    ------------- + 17
           2
    ------------------- + 17
              2
    -------------------------- = 1
                 32
Here the denominators are the A006519 of the numerators: A006519(1+17) = 2, A006519(9+17) = 2, A006519(13+17) = 2, A006519(15+17) = 32. Summing the exponents of these powers of 2, we obtain the required result: a(8) = 1 + 1 + 1 + 5 = 8. Indeed, we have (((1*32 - 17)*2 - 17)*2 - 17)*2 - 17 = 1. So 32*2*2*2 - 1 == 0 (mod 17), 2^8 - 1 == 0 (mod 17). In the general case, note that all "partial fractions" (which indeed are integers) are odd residues modulo 2*n+1 in the interval [1, 2*n-1]. It is easy to prove that the first 1 appears not later than in the n-th step. (End)

References

  • E. Bach and Jeffrey Shallit, Algorithmic Number Theory, I.
  • T. Folger, "Shuffling Into Hyperspace," Discover, 1991 (vol 12, no 1), pages 66-67.
  • M. Gardner, "Card Shuffles," Mathematical Carnival chapter 10, pages 123-138. New York: Vintage Books, 1977.
  • L. Lunelli and M. Lunelli, Tavola di congruenza a^n == 1 mod K per a=2,5,10, Atti Sem. Mat. Fis. Univ. Modena 10 (1960/61), 219-236 (1961).
  • J. H. Silverman, A Friendly Introduction to Number Theory, 3rd ed., Pearson Education, Inc, 2006, p. 146, Exer. 21.3
  • 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

Cf. A003571, A003573, A217469, A070667-A070683, A053447, A053451, A292239, A292265.
Cf. A024222, A006694 (number of cyclotomic cosets).
Cf. A014664 (order of 2 mod n-th prime).
Cf. A001122 (primes for which 2 is a primitive root).
Cf. A216838 (primes for which 2 is not a primitive root).
Cf. A000010, A000225, A005420, A006519, A007733, A025192, A048675, A056239, A179680.
Bisections give A274298, A274299.
Partial sums: A359147.

Programs

  • GAP
    List([0..100],n->OrderMod(2,2*n+1)); # Muniru A Asiru, Feb 01 2019
  • Haskell
    import Data.List (findIndex)
import Data.Maybe (fromJust)
a002326 n = (+ 1) $ fromJust $
            findIndex ((== 0) . (`mod` (2 * n + 1))) $ tail a000225_list
-- Reinhard Zumkeller, Apr 22 2013
  • Magma
    [ 1 ] cat [ Modorder(2, 2*n+1): n in [1..72] ]; // Klaus Brockhaus, Dec 03 2008
  • Maple
    a := n -> `if`(n=0, 1, numtheory:-order(2, 2*n+1)):
seq(a(n), n=0..72);
  • Mathematica
    Table[MultiplicativeOrder[2, 2*n + 1], {n, 0, 100}] (* Robert G. Wilson v, Apr 05 2011 *)
  • PARI
    a(n)=if(n<0,0,znorder(Mod(2,2*n+1))) /* Michael Somos, Mar 31 2005 */
  • Python
    from sympy import n_order
[n_order(2, 2*n+1) for n in range(73)] # Hermann Stamm-Wilbrandt, Jul 27 2021
  • Sage
    # From Peter Luschny, Oct 06 2017: (Start)
[Mod(2,n).multiplicative_order() for n in (0..145) if gcd(n,2) == 1]
# Algorithm from Vladimir Shevelev as described in A179680 and presented in Example.
def A002326VS(n):
    s, m, N = 0, 1, 2*n + 1
    while True:
        k = N + m
        v = valuation(k, 2)
        s += v
        m = k >> v
        if m == 1: break
    return s
[A002326VS(n) for n in (0..72)] # (End)

Formula

a((3^n-1)/2) = A025192(n). - Vladimir Shevelev, May 09 2008
Bisection of A007733: a(n) = A007733(2*n+1). - Max Alekseyev, Jun 11 2009
a((b(n)-1)/2) = n for odd n and even n such that b(n/2) != b(n), where b(n) = A005420(n). - Thomas Ordowski, Jan 11 2014
Note that a(2^n-1) = n+1 and a(2^n) = 2*(n+1). - Thomas Ordowski, Jan 16 2014
a(n) = A056239(A292239(n)) = A048675(A292265(n)). - Antti Karttunen, Oct 04 2017

Extensions

More terms from David W. Wilson, Jan 13 2000
More terms from Benoit Cloitre, Apr 11 2003

A058891 a(n) = 2^(2^(n-1) - 1).

Original entry on oeis.org

1, 2, 8, 128, 32768, 2147483648, 9223372036854775808, 170141183460469231731687303715884105728, 57896044618658097711785492504343953926634992332820282019728792003956564819968
Offset: 1

Views

Author

N. J. A. Sloane, Jan 08 2001

Keywords

Comments

For n > 1, a(n) is the least solution > 1 to rad(x)^(n-1) = tau(x) where rad(x) = A007947(x) is the squarefree kernel of x and tau(x) = A000005(x) the number of divisors of x. - Benoit Cloitre, Apr 18 2002 [Corrected by Michel Marcus, Oct 15 2018]
For n > 1, a(n) is also the total number of possible outcomes of a knockout tournament starting with 2^(n-1) players, taking account of all matches in the tournament. - Martin Griffiths, Mar 26 2009
Also, a(n+1) = 2^(2^n-1) for n >= 1 are solutions x = y of the Diophantine equation x^y * y^x = (x+y)^z in positive integers; corresponding solutions z are in A348332 (see this last sequence for more informations and links). - Bernard Schott, Oct 13 2021
For n > 2, a(n) ends with 8. - Bernard Schott, Oct 20 2021
a(n) is the number of labeled hypergraphs on n - 1 vertices. - Lorenzo Sauras Altuzarra, Apr 01 2023

Examples

			The 8 possible hyperedge sets for the vertex set {1, 2} are {}, {{1}}, {{2}}, {{1, 2}}, {{1}, {2}}, {{1}, {1, 2}}, {{2}, {1, 2}} and {{1}, {2}, {1, 2}}. - _Lorenzo Sauras Altuzarra_, Apr 01 2023

References

  • F. Harary, Graph Theory, Page 209, Problem 16.11.

Links

Crossrefs

Cf. A000079, A000225, A053287, A076214, A077585, A348332.

Programs

  • Maple
    a[1]:=1: for n from 2 to 20 do a[n]:=2*a[n-1]^2 od: seq(a[n], n=1..9); # Zerinvary Lajos, Apr 16 2009
  • Mathematica
    a = 1; b = -3; Table[Expand[(-1/2) ((a + Sqrt[b])^(2^n) + (a - Sqrt[b])^(2^n))], {n, 1, 10}] (* Artur Jasinski, Oct 11 2008 *)
  • PARI
    a(n) = { 2^(2^(n-1)-1) } \\ Harry J. Smith, Jun 23 2009
  • Python
    def A058891(n): return 1<<(1<Chai Wah Wu, Dec 12 2022

Formula

a(n) = A053287(A000079(n-1)).
a(1) = 1, a(n+1) = 2*a(n)^2.
a(1) = 1, a(n+1) = 2^n*a(1)*a(2)*...*a(n). - Benoit Cloitre, Sep 13 2003
a(n) = (-1/2)*((1 + sqrt(-3))^(2^n) + (1 - sqrt(-3))^(2^n)). - Artur Jasinski, Oct 11 2008
a(n) = 2*a(n-1)^2 is an example with a(1) = 1 and k = 2 of a(n) = k*a(n-1)^2; general explicit formula: a(n) = ((a(1)*k)^(2^(n-1)))/k. - Andreas Pfaffel (andreas.pfaffel(AT)gmx.at), Apr 27 2010
a(n) = A077585(n-1) + 1. - Maurizio De Leo, Feb 25 2015
a(n) = 2^A000225(n-1). - Michel Marcus, Aug 19 2020
Sum_{n>=0} 1/a(n) = A076214. - Amiram Eldar, Oct 27 2020

A262626 Visible parts of the perspective view of the stepped pyramid whose structure essentially arises after the 90-degree-zig-zag folding of the isosceles triangle A237593.

Original entry on oeis.org

1, 1, 1, 3, 2, 2, 2, 2, 2, 1, 1, 2, 7, 3, 1, 1, 3, 3, 3, 3, 2, 2, 3, 12, 4, 1, 1, 1, 1, 4, 4, 4, 4, 2, 1, 1, 2, 4, 15, 5, 2, 1, 1, 2, 5, 5, 3, 5, 5, 2, 2, 2, 2, 5, 9, 9, 6, 2, 1, 1, 1, 1, 2, 6, 6, 6, 6, 3, 1, 1, 1, 1, 3, 6, 28, 7, 2, 2, 1, 1, 2, 2, 7, 7, 7, 7, 3, 2, 1, 1, 2, 3, 7, 12, 12, 8, 3, 1, 2, 2, 1, 3, 8, 8, 8, 8, 8, 3, 2, 1, 1
Offset: 1

Views

Author

Omar E. Pol, Sep 26 2015

Keywords

Comments

Also the rows of both triangles A237270 and A237593 interleaved.
Also, irregular triangle read by rows in which T(n,k) is the area of the k-th region (from left to right in ascending diagonal) of the n-th symmetric set of regions (from the top to the bottom in descending diagonal) in the two-dimensional diagram of the perspective view of the infinite stepped pyramid described in A245092 (see the diagram in the Links section).
The diagram of the symmetric representation of sigma is also the top view of the pyramid, see Links section. For more information about the diagram see also A237593 and A237270.
The number of cubes at the n-th level is also A024916(n), the sum of all divisors of all positive integers <= n.
Note that this pyramid is also a quarter of the pyramid described in A244050. Both pyramids have infinitely many levels.
Odd-indexed rows are also the rows of the irregular triangle A237270.
Even-indexed rows are also the rows of the triangle A237593.
Lengths of the odd-indexed rows are in A237271.
Lengths of the even-indexed rows give 2*A003056.
Row sums of the odd-indexed rows gives A000203, the sum of divisors function.
Row sums of the even-indexed rows give the positive even numbers (see A005843).
Row sums give A245092.
From the front view of the stepped pyramid emerges a geometric pattern which is related to A001227, the number of odd divisors of the positive integers.
The connection with the odd divisors of the positive integers is as follows: A261697 --> A261699 --> A237048 --> A235791 --> A237591 --> A237593 --> A237270 --> this sequence.

Examples

			Irregular triangle begins:
  1;
  1, 1;
  3;
  2, 2;
  2, 2;
  2, 1, 1, 2;
  7;
  3, 1, 1, 3;
  3, 3;
  3, 2, 2, 3;
  12;
  4, 1, 1, 1, 1, 4;
  4, 4;
  4, 2, 1, 1, 2, 4;
  15;
  5, 2, 1, 1, 2, 5;
  5, 3, 5;
  5, 2, 2, 2, 2, 5;
  9, 9;
  6, 2, 1, 1, 1, 1, 2, 6;
  6, 6;
  6, 3, 1, 1, 1, 1, 3, 6;
  28;
  7, 2, 2, 1, 1, 2, 2, 7;
  7, 7;
  7, 3, 2, 1, 1, 2, 3, 7;
  12, 12;
  8, 3, 1, 2, 2, 1, 3, 8;
  8, 8, 8;
  8, 3, 2, 1, 1, 1, 1, 2, 3, 8;
  31;
  9, 3, 2, 1, 1, 1, 1, 2, 3, 9;
  ...
Illustration of the odd-indexed rows of triangle as the diagram of the symmetric representation of sigma which is also the top view of the stepped pyramid:
.
   n  A000203    A237270    _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
   1     1   =      1      |_| | | | | | | | | | | | | | | |
   2     3   =      3      |_ _|_| | | | | | | | | | | | | |
   3     4   =    2 + 2    |_ _|  _|_| | | | | | | | | | | |
   4     7   =      7      |_ _ _|    _|_| | | | | | | | | |
   5     6   =    3 + 3    |_ _ _|  _|  _ _|_| | | | | | | |
   6    12   =     12      |_ _ _ _|  _| |  _ _|_| | | | | |
   7     8   =    4 + 4    |_ _ _ _| |_ _|_|    _ _|_| | | |
   8    15   =     15      |_ _ _ _ _|  _|     |  _ _ _|_| |
   9    13   =  5 + 3 + 5  |_ _ _ _ _| |      _|_| |  _ _ _|
  10    18   =    9 + 9    |_ _ _ _ _ _|  _ _|    _| |
  11    12   =    6 + 6    |_ _ _ _ _ _| |  _|  _|  _|
  12    28   =     28      |_ _ _ _ _ _ _| |_ _|  _|
  13    14   =    7 + 7    |_ _ _ _ _ _ _| |  _ _|
  14    24   =   12 + 12   |_ _ _ _ _ _ _ _| |
  15    24   =  8 + 8 + 8  |_ _ _ _ _ _ _ _| |
  16    31   =     31      |_ _ _ _ _ _ _ _ _|
  ...
The above diagram arises from a simpler diagram as shown below.
Illustration of the even-indexed rows of triangle as the diagram of the deployed front view of the corner of the stepped pyramid:
.
.                                 A237593
Level                               _ _
1                                 _|1|1|_
2                               _|2 _|_ 2|_
3                             _|2  |1|1|  2|_
4                           _|3   _|1|1|_   3|_
5                         _|3    |2 _|_ 2|    3|_
6                       _|4     _|1|1|1|1|_     4|_
7                     _|4      |2  |1|1|  2|      4|_
8                   _|5       _|2 _|1|1|_ 2|_       5|_
9                 _|5        |2  |2 _|_ 2|  2|        5|_
10              _|6         _|2  |1|1|1|1|  2|_         6|_
11            _|6          |3   _|1|1|1|1|_   3|          6|_
12          _|7           _|2  |2  |1|1|  2|  2|_           7|_
13        _|7            |3    |2 _|1|1|_ 2|    3|            7|_
14      _|8             _|3   _|1|2 _|_ 2|1|_   3|_             8|_
15    _|8              |3    |2  |1|1|1|1|  2|    3|              8|_
16   |9                |3    |2  |1|1|1|1|  2|    3|                9|
...
The number of horizontal line segments in the n-th level in each side of the diagram equals A001227(n), the number of odd divisors of n.
The number of horizontal line segments in the left side of the diagram plus the number of the horizontal line segment in the right side equals A054844(n).
The total number of vertical line segments in the n-th level of the diagram equals A131507(n).
The diagram represents the first 16 levels of the pyramid.
The diagram of the isosceles triangle and the diagram of the top view of the pyramid shows the connection between the partitions into consecutive parts and the sum of divisors function (see also A286000 and A286001). - _Omar E. Pol_, Aug 28 2018
The connection between the isosceles triangle and the stepped pyramid is due to the fact that this object can also be interpreted as a pop-up card. - _Omar E. Pol_, Nov 09 2022

Links

Crossrefs

Famous sequences that are visible in the stepped pyramid:
Cf. A000040 (prime numbers)......., for the characteristic shape see A346871.
Cf. A000079 (powers of 2)........., for the characteristic shape see A346872.
Cf. A000203 (sum of divisors)....., total area of the terraces in the n-th level.
Cf. A000217 (triangular numbers).., for the characteristic shape see A346873.
Cf. A000225 (Mersenne numbers)...., for a visualization see A346874.
Cf. A000384 (hexagonal numbers)..., for the characteristic shape see A346875.
Cf. A000396 (perfect numbers)....., for the characteristic shape see A346876.
Cf. A000668 (Mersenne primes)....., for a visualization see A346876.
Cf. A001097 (twin primes)........., for a visualization see A346871.
Cf. A001227 (# of odd divisors)..., number of subparts in the n-th level.
Cf. A002378 (oblong numbers)......, for a visualization see A346873.
Cf. A008586 (multiples of 4)......, perimeters of the successive levels.
Cf. A008588 (multiples of 6)......, for the characteristic shape see A224613.
Cf. A013661 (zeta(2))............., (area of the horizontal faces)/(n^2), n -> oo.
Cf. A014105 (second hexagonals)..., for the characteristic shape see A346864.
Cf. A067742 (# of middle divisors), # cells in the main diagonal in n-th level.
Other sequences that are visible in the stepped pyramid: A000096, A001065, A001359, A001747, A002939, A002943, A003056, A004125, A004277, A004526, A005279, A006512, A007606, A007607, A082647, A008438, A008578, A008864, A010814, A014106, A014107, A014132, A014574, A016945, A019434, A024206, A024916, A028552, A028982, A028983, A034856, A038550, A047836, A048050, A052928, A054735, A054844, A062731, A065091, A065475, A071561, A071562, A071904, A092506, A100484, A108605, A139256, A139257, A144396, A152677, A152678, A153485, A155085, A161680, A161983, A162917, A174905, A174973, A175254, A176810, A224880, A235791, A237270, A237271, A237591, A237593, A238005, A238524, A244049, A245092, A259176, A259177, A261348, A278972, A317302, A317303, A317304, A317305, A317307, A319529, A319796, A319801, A319802, A327329, A336305, (and several others).
Apart from zeta(2) other constants that are related to the stepped pyramid are A072691, A353908, A354238.
Cf. A054844, A131507, A196020, A236104, A237048, A239660, A244050, A259179, A261350, A261697, A261699, A262612, A280850, A286000, A286001, A296508.
Previous Showing 61-70 of 1353 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.