A048744 -id:A048744 - cp's OEIS frontend

A000325 a(n) = 2^n - n.

1, 1, 2, 5, 12, 27, 58, 121, 248, 503, 1014, 2037, 4084, 8179, 16370, 32753, 65520, 131055, 262126, 524269, 1048556, 2097131, 4194282, 8388585, 16777192, 33554407, 67108838, 134217701, 268435428, 536870883, 1073741794, 2147483617

Offset: 0

Rosario Salamone (Rosario.Salamone(AT)risc.uni-linz.ac.at)

Number of permutations of degree n with at most one fall; called "Grassmannian permutations" by Lascoux and Schützenberger. - Axel Kohnert (Axel.Kohnert(AT)uni-bayreuth.de)
Number of different permutations of a deck of n cards that can be produced by a single shuffle. [DeSario]
Number of Dyck paths of semilength n having at most one long ascent (i.e., ascent of length at least two). Example: a(4)=12 because among the 14 Dyck paths of semilength 4, the only paths that have more than one long ascent are UUDDUUDD and UUDUUDDD (each with two long ascents). Here U = (1, 1) and D = (1, -1). Also number of ordered trees with n edges having at most one branch node (i.e., vertex of outdegree at least two). - Emeric Deutsch, Feb 22 2004
Number of {12,1*2*,21*}-avoiding signed permutations in the hyperoctahedral group.
Number of 1342-avoiding circular permutations on [n+1].
2^n - n is the number of ways to partition {1, 2, ..., n} into arithmetic progressions, where in each partition all the progressions have the same common difference and have lengths at least 1. - Marty Getz (ffmpg1(AT)uaf.edu) and Dixon Jones (fndjj(AT)uaf.edu), May 21 2005
if b(0) = x and b(n) = b(n-1) + b(n-1)^2*x^(n-2) for n > 0, then b(n) is a polynomial of degree a(n). - Michael Somos, Nov 04 2006
The chromatic invariant of the Mobius ladder graph M_n for n >= 2. - Jonathan Vos Post, Aug 29 2008
Dimension sequence of the dual alternative operad (i.e., associative and satisfying the identity xyz + yxz + zxy + xzy + yzx + zyx = 0) over the field of characteristic 3. - Pasha Zusmanovich, Jun 09 2009
An elephant sequence, see A175654. For the corner squares six A[5] vectors, with decimal values between 26 and 176, lead to this sequence (without the first leading 1). For the central square these vectors lead to the companion sequence A168604. - Johannes W. Meijer, Aug 15 2010
a(n+1) is also the number of order-preserving and order-decreasing partial isometries (of an n-chain). - Abdullahi Umar, Jan 13 2011
A040001(n) = p(-1) where p(x) is the unique degree-n polynomial such that p(k) = a(k) for k = 0, 1, ..., n. - Michael Somos, May 12 2012
A130103(n+1) = p(n+1) where p(x) is the unique degree-n polynomial such that p(k) = a(k) for k = 0, 1, ..., n. - Michael Somos, May 12 2012
The number of labeled graphs with n vertices whose vertex set can be partitioned into a clique and a set of isolated points. - Alex J. Best, Nov 20 2012
For n > 0, a(n) is a B_2 sequence. - Thomas Ordowski, Sep 23 2014
See coefficients of the linear terms of the polynomials of the table on p. 10 of the Getzler link. - Tom Copeland, Mar 24 2016
Consider n points lying on a circle, then for n>=2 a(n-1) is the maximum number of ways to connect two points with non-intersecting chords. - Anton Zakharov, Dec 31 2016
Also the number of cliques in the (n-1)-triangular honeycomb rook graph. - Eric W. Weisstein, Jul 14 2017
From Eric M. Schmidt, Jul 17 2017: (Start)
Number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) != e(j) < e(k). [Martinez and Savage, 2.7]
Number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i), e(j), e(k) pairwise distinct. [Martinez and Savage, 2.7]
Number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(j) >= e(k) and e(i) != e(k) pairwise distinct. [Martinez and Savage, 2.7]
(End)
Number of F-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are F-equivalent iff the positions of pattern F are identical in these paths. -  Sergey Kirgizov, Apr 08 2018
From Gus Wiseman, Feb 10 2019: (Start)
Also the number of connected partitions of an n-cycle. For example, the a(1) = 1 through a(4) = 12 connected partitions are:
  {{1}}  {{12}}    {{123}}      {{1234}}
         {{1}{2}}  {{1}{23}}    {{1}{234}}
                   {{12}{3}}    {{12}{34}}
                   {{13}{2}}    {{123}{4}}
                   {{1}{2}{3}}  {{124}{3}}
                                {{134}{2}}
                                {{14}{23}}
                                {{1}{2}{34}}
                                {{1}{23}{4}}
                                {{12}{3}{4}}
                                {{14}{2}{3}}
                                {{1}{2}{3}{4}}
(End)
Number of subsets of n-set without the single-element subsets. - Yuchun Ji, Jul 16 2019
For every prime p, there are infinitely many terms of this sequence that are divisible by p (see IMO Compendium link and Doob reference). Corresponding indices n are: for p = 2, even numbers A299174; for p = 3, A047257; for p = 5, A349767. - Bernard Schott, Dec 10 2021
Primes are in A081296 and corresponding indices in A048744. - Bernard Schott, Dec 12 2021

			G.f. = 1 + x + 2*x^2 + 5*x^3 + 12*x^4 + 27*x^5 + 58*x^6 + 121*x^7 + ...

Michael Doob, The Canadian Mathematical Olympiad & L'Olympiade Mathématique du Canada 1969-1993, Canadian Mathematical Society & Société Mathématique du Canada, Problem 4, 1983, page 158, 1993.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Kassie Archer and Aaron Geary, Descents in powers of permutations, arXiv:2406.09369 [math.CO], 2024.
Cory B. H. Ball, The Apprentices' Tower of Hanoi, Electronic Theses and Dissertations, East Tennessee State University, Paper 2512, 2015.
Jean-Luc Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, 18 (2011), #P178;
Jean-Luc Baril, Sergey Kirgizov and Armen Petrossian, Enumeration of Łukasiewicz paths modulo some patterns, arXiv:1804.01293 [math.CO], 2018.
David Callan, Pattern avoidance in circular permutations, arXiv:math/0210014 [math.CO], 2002.
Charles Cratty, Samuel Erickson, Frehiwet Negass, and Lara Pudwell, Pattern Avoidance in Double Lists, preprint, 2015.
Robert DeSario and LeRoy Wenstrom, Invertible shuffles, Problem 10931, Amer. Math. Monthly, 111 (No. 2, 2004), 169-170.
Askar Dzhumadil'daev and Pasha Zusmanovich, The alternative operad is not Koszul, arXiv:0906.1272 [math.RA], 2009-2013.
Marty Getz, Dixon Jones and Ken Dutch, Partitioning by Arithmetic Progressions: Problem 11005, American Math. Monthly, Vol. 112, 2005, p. 89. (The published solution is incomplete. Letting d be the common difference of the arithmetic progressions, the solver's expression q_1(n,d)=2^(n-d) must be summed over all d=1,...,n and duplicate partitions must be removed.)
E. Getzler, The semi-classical approximation for modular operads, arXiv:alg-geom/9612005, 1996.
Juan B. Gil and Jessica A. Tomasko, Restricted Grassmannian permutations, arXiv:2112.03338 [math.CO], 2021.
Juan B. Gil and Michael D. Weiner, On pattern-avoiding Fishburn permutations, arXiv:1812.01682 [math.CO], 2018.
The IMO Compendium, Problem 4, 15th Canadian Mathematical Olympiad 1983.
R. Kehinde, S. O. Makanjuola and A. Umar, On the semigroup of order-decreasing partial isometries of a finite chain, arXiv:1101.2558 [math.GR], 2011.
Alain Lascoux and Marcel-Paul Schützenberger, Schubert polynomials and the Littlewood Richardson rule, Letters in Math. Physics 10 (1985) 111-124.
T. Mansour and J. West, Avoiding 2-letter signed patterns, arXiv:math/0207204 [math.CO], 2002.
Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.
Eric Weisstein's World of Mathematics, Chromatic Invariant
Eric Weisstein's World of Mathematics, Clique
Eric Weisstein's World of Mathematics, Moebius Ladder
Chunyan Yan and Zhicong Lin, Inversion sequences avoiding pairs of patterns, arXiv:1912.03674 [math.CO], 2019.
Index entries for linear recurrences with constant coefficients, signature (4,-5,2).
Index to sequences related to Olympiads.

Column 1 of triangle A008518.
Row sum of triangles A184049 and A184050.
Cf. A000108, A002064, A133116, A160692, A005803, A006127, A186947.
Cf. A001610, A066982, A323950, A323951.
Cf. A047257, A299174, A349767.
Cf.  A048744, A081296.

a000325 n = 2 ^ n - n
a000325_list = zipWith (-) a000079_list [0..]
-- Reinhard Zumkeller, Jul 17 2012

[2^n - n: n in [0..35]]; // Vincenzo Librandi, May 13 2011

A000325 := proc(n) option remember; if n <=1 then n+1 else 2*A000325(n-1)+n-1; fi; end;
g:=1/(1-2*z): gser:=series(g, z=0, 43): seq(coeff(gser, z, n)-n, n=0..31); # Zerinvary Lajos, Jan 09 2009

Table[2^n - n, {n, 0, 39}] (* Alonso del Arte, Sep 15 2014 *)
LinearRecurrence[{4, -5, 2}, {1, 2, 5}, {0, 20}] (* Eric W. Weisstein, Jul 14 2017 *)

{a(n) = 2^n - n}; /* Michael Somos, Nov 04 2006 */

def A000325(n): return (1<Chai Wah Wu, Jan 11 2023

a(n+1) = 2*a(n) + n - 1, a(0) = 1. - Reinhard Zumkeller, Apr 12 2003
Binomial transform of 1, 0, 1, 1, 1, .... The sequence starting 1, 2, 5, ... has a(n) = 1 + n + 2*Sum_{k=2..n} binomial(n, k) = 2^(n+1) - n - 1. This is the binomial transform of 1, 1, 2, 2, 2, 2, .... a(n) = 1 + Sum_{k=2..n} C(n, k). - Paul Barry, Jun 06 2003
G.f.: (1-3x+3x^2)/((1-2x)*(1-x)^2). - Emeric Deutsch, Feb 22 2004
A107907(a(n+2)) = A000051(n+2) for n > 0. - Reinhard Zumkeller, May 28 2005
a(n+1) = sum of n-th row of the triangle in A109128. - Reinhard Zumkeller, Jun 20 2005
Row sums of triangle A133116. - Gary W. Adamson, Sep 14 2007
G.f.: 1 / (1 - x / (1 - x / ( 1 - x / (1 + x / (1 - 2*x))))). - Michael Somos, May 12 2012
First difference is A000225. PSUM transform is A084634. - Michael Somos, May 12 2012
a(n) = [x^n](B(x)^n-B(x)^(n-1)), n>0, a(0)=1, where B(x) = (1+2*x+sqrt(1+4*x^2))/2. - Vladimir Kruchinin, Mar 07 2014
E.g.f.: (exp(x) - x)*exp(x). - Ilya Gutkovskiy, Aug 07 2016
a(n) = A125128(n) - A000225(n) + 1. - Miquel Cerda, Aug 12 2016
a(n) = 2*A125128(n) - A095151(n) + 1. - Miquel Cerda, Aug 12 2016
a(n) = A079583(n-1) - A000225(n-1). - Miquel Cerda, Aug 15 2016
a(n)^2 - 4*a(n-1)^2 = (n-2)*(a(n)+2*a(n-1)). - Yuchun Ji, Jul 13 2018
a(n) = 2^(-n) * A186947(n) = 2^n * A002064(-n) for all n in Z. - Michael Somos, Jul 18 2018
a(2^n) = (2^a(n) - 1)*2^n. - Lorenzo Sauras Altuzarra, Feb 01 2022

A052007 Numbers m such that 2^m + m is prime.

Original entry on oeis.org

1, 3, 5, 9, 15, 39, 75, 81, 89, 317, 701, 735, 1311, 1881, 3201, 3225, 11795, 88071, 204129, 678561

Offset: 1

G. L. Honaker, Jr. and Patrick De Geest, Nov 15 1999

Terms >= 701 are currently only strong pseudoprimes.
If m=1 (mod 6) or m=2 (mod 6) then 3 divides 2^m+m. Thus for n > 1, a(n)!=1 (mod 6) and a(n)!=2 (mod 6).
Some of the results were computed using the PrimeFormGW (PFGW) primality-testing program. - Hugo Pfoertner, Nov 14 2019
Keller (see Links) notes that a Mersenne number M(2^m+m) = 2^(2^m+m) - 1 can be written as (2^m)*2^(2^m) - 1, and lists the first twelve terms of this sequence. The last known case where M(2^m+m) is prime is for m=a(4)=9, which gives the prime M(521). - Jeppe Stig Nielsen, Apr 20 2021

			2^39 + 39 = 549755813927 is prime.

W. Keller, New Cullen Primes, Math. Comp. 64 (1995), 1733-1741, S39.
Henri Lifchitz, Renaud Lifchitz, PRP Top Records. 2^n+n.

Cf. A006127, A048744, A129962.

Do[ If[ PrimeQ[ 2^n + n ], Print[ n ] ], {n, 0, 7000} ]
v={1}; Do[If[Mod[n, 2]*(Mod[n, 6]-1)!= 0&&PrimeQ[2^n+n], v=Append[v, n]; Print[v]], {n, 2, 20000}]

is(n)=isprime(2^n+n) \\ Charles R Greathouse IV, Feb 09 2017

11795 from Farideh Firoozbakht, Aug 21 2003
88071 from Hugo Pfoertner, Dec 26 2004
More terms from Henri Lifchitz submitted by Ray Chandler, Mar 02 2007

A081296 Primes of the form 2^k - k.

Original entry on oeis.org

2, 5, 503, 8179, 524269, 2097131, 36028797018963913, 3705346855594118253554271520278013051304639509300498049262642688253220148477691

Offset: 1

Reinhard Zumkeller, Apr 20 2003

nonn

Primes in A000325.
The corresponding k are given in A048744.
Next term a(9) contains 1029 digits and is too large to include. - R. J. Mathar, Jul 15 2007

Cf. A048744 (k such that 2^k - k is prime).

Select[Table[2^n-n,{n,300}],PrimeQ] (* Harvey P. Dale, Nov 24 2018 *)

{ for(k=1,100000, if(isprime(2^k-k), print1(2^k-k,", ")));} \\ R. J. Mathar, Jul 15 2007

a(n) = 2^A048744(n) - A048744(n). - R. J. Mathar, Jul 22 2009

More terms from R. J. Mathar, Jul 15 2007

A061421 Primes of the form 2^n+n+1.

Original entry on oeis.org

2, 7, 71, 110427941548649020598956093796432407239217743554726184882600387580788973

Offset: 1

Jason Earls, May 02 2001

nonn

Next term is 2^1884+1884+1, with 568 digits and is too large to include. - Emeric Deutsch, May 13 2006

The Wikipedia article "Zeisel number" gives a historical connection to A051015. - Jonathan Sondow, Oct 17 2017

K. S. Brown, The Sum of the Prime Factors of N (Part 2: Primes of the Form 2k-1 + k), Math Pages
Wikipedia, Zeisel number

Cf. A001580, A069539, A052007, A048744, A100357, A100358, A100359.

Cf. A061422.

a:=proc(n) if isprime(2^n+n+1)=true then 2^n+n+1 else fi end: seq(a(n),n=0..1000); # Emeric Deutsch, May 13 2006

{ta={{0}}, tb={{0}}};Do[g=n;s=2^n+n+1; If[PrimeQ[s], Print[n];ta=Append[ta, n]; tb=Append[tb, s]], {n, 1, 10000}];{ta, tb, g} (* Labos Elemer, Nov 19 2004 *)

Edited by N. J. A. Sloane, May 04 2007

A100361 Numbers k such that 2^k - k + 1 is prime.

Original entry on oeis.org

0, 1, 2, 4, 6, 16, 18, 54, 58, 100, 120, 504, 1302, 3234, 14748, 16102, 22782, 34656, 64764, 70866, 194940, 274074, 313344, 331416, 354640

Offset: 1

Labos Elemer, Nov 19 2004

a(21) > 150000. - Giovanni Resta, Mar 18 2014

a(26) > 5*10^5. - Robert Price, Oct 13 2014

Cf. A001580, A052007, A048744, A100357-A100359, A061421.

A100361:=n->`if`(isprime(2^n-n+1), n, NULL): seq(A100361(n), n=0..10^3); # Wesley Ivan Hurt, Oct 13 2014

{ta={{0}}, tb={{0}}};Do[g=n;s=2^n-n+1; If[PrimeQ[s], Print[n];ta=Append[ta, n]; tb=Append[tb, s]], {n, 1, 10000}];{ta, tb, g}

is(n)=ispseudoprime(2^n-n+1) \\ Charles R Greathouse IV, Feb 20 2017

a(15)-a(20) from Giovanni Resta, Mar 18 2014

a(21)-a(25) from Robert Price, Oct 13 2014

A100362 Primes of the form 2^k - k + 1.

Original entry on oeis.org

2, 2, 3, 13, 59, 65521, 262127, 18014398509481931, 288230376151711687, 1267650600228229401496703205277, 1329227995784915872903807060280344457

Offset: 1

Labos Elemer, Nov 19 2004

The next term has 151 digits. - Stefan Steinerberger, Feb 11 2006

Vincenzo Librandi, Table of n, a(n) for n = 1..14

Cf. A001580, A052007, A048744, A100357-A100361.

[ a: n in [0..200] | IsPrime(a) where a is 2^n-n+1 ]; // Vincenzo Librandi, Jul 18 2012

Select[Table[2^n-n+1,{n,0,500}],PrimeQ] (* Vincenzo Librandi, Jul 18 2012 *)

def list_a(k):
  return [(2**i) - i + 1 for i in range(k) if (2**i) - i + 1 in Primes()] # Giuseppe Bonaccorso, Aug 15 2019

A100359 Numbers k such that 2^k + k + 1 is prime.

Original entry on oeis.org

0, 2, 6, 236, 1884, 51380, 75764

Offset: 1

Labos Elemer, Nov 19 2004

a(8) > 500000. - Robert Price, May 24 2014

Cf. A001580, A061422, A069539, A052007, A048744, A100357, A100358.

{ta={{0}}, tb={{0}}};Do[g=n;s=2^n+n+1; If[PrimeQ[s], Print[n];ta=Append[ta, n]; tb=Append[tb, s]], {n, 1, 10000}];{ta, tb, g}

is(n)=ispseudoprime(2^n+n+1) \\ Charles R Greathouse IV, Feb 20 2017

a(n) = A061422(n) - 1.

a(6) from A061422 Max Alekseyev, Feb 08 2009

a(7) from Giovanni Resta, Mar 19 2014

A224470 Numbers k such that 7^k - k is prime.

Original entry on oeis.org

2, 6, 8, 12, 44, 48, 512, 1088, 1104, 6038

Offset: 1

Alex Ratushnyak, Apr 06 2013

a(11) > 92000. - Giovanni Resta, Apr 08 2013

a(11) > 2*10^5. - Robert Price, Feb 11 2014

Cf. A048744, A058037, A057908, A058046, A058829, A224468.

forstep(n=2,10^4,2,if(ispseudoprime(7^n-n),print1(n,", "))); /* Joerg Arndt, Apr 07 2013 */

A224471 Numbers k such that 8^k - k is prime.

Original entry on oeis.org

1, 3, 37, 45, 597, 1131, 14203, 112539

Offset: 1

Alex Ratushnyak, Apr 06 2013

a(8) > 41000. - Giovanni Resta, Apr 07 2013

a(9) > 2*10^5. - Robert Price, Jan 19 2014

Cf. A048744, A058037, A057908, A058046, A058829, A224470, A224469, A224469.

import java.math.BigInteger;
public class A224471 {
  public static void main (String[] args) {
    BigInteger b8 = BigInteger.valueOf(8);
    BigInteger m = BigInteger.valueOf(64);
    for(long n=1; ; n+=2) {
        BigInteger b = b8.subtract(BigInteger.valueOf(n));
        if (b.isProbablePrime(2)) {
            if (b.isProbablePrime(80))
                System.out.printf("%d\n", n);
        }
        b8 = b8.multiply(m);
    }
  }
}

forstep(n=1,10^4,2,if(ispseudoprime(8^n-n),print1(n,", "))); /* Joerg Arndt, Apr 07 2013 */

a(7) from Giovanni Resta, Apr 07 2013

a(8) from Robert Price, Jan 19 2014

A359735 Let f(s,n) = 2^n + s*n, with s in {-1, 1}. Let c be the number of primes out of the pair f(-1,n), f(1,n). If only f(-1,n) is prime, a(n) = -1, otherwise a(n) = c.

Original entry on oeis.org

0, 1, -1, 2, 0, 1, 0, 0, 0, 2, 0, 0, 0, -1, 0, 1, 0, 0, 0, -1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 0

Jean-Marc Rebert, Jan 12 2023

sign

			f(-1,1) = 2^1 - 1 = 1, is not prime and f(1,1) = 2^1 + 1 = 3 is prime, so a(1) = 1.
f(-1,2) = 2^2 - 2 = 2, is prime and f(1,2) = 2^2 + 2 = 6 = 2 * 3 is not prime, so a(2) = -1.
f(-1,3) = 2^3 - 3 = 5, is prime and f(1,3) = 2^3 + 3 = 11 is prime, so a(3) = 2.

Antti Karttunen, Table of n, a(n) for n = 0..10000

Cf. A006127, A048744, A052007, A129962.

f(s,n)=2^n+s*n
a(n)=my(a=isprime(f(-1,n)),b=isprime(f(1,n)),c=a+b); if(c==1&&a==1,return(-1),return(c))

a(n) can be = 2 only if n = 6*m + 3 for m >= 0 and m is not congruent to {0, 4} mod 5, not congruent to {2, 4} mod 7, not congruent to {6, 7} mod 11 and not congruent to {3, 9} mod 13. Does a(n) = 2 for n > 9 exist? - Thomas Scheuerle, Jan 12 2023

cp's OEIS Frontend

A000325 a(n) = 2^n - n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Formula

A052007 Numbers m such that 2^m + m is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A081296 Primes of the form 2^k - k.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A061421 Primes of the form 2^n+n+1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A100361 Numbers k such that 2^k - k + 1 is prime.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A100362 Primes of the form 2^k - k + 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Sage

A100359 Numbers k such that 2^k + k + 1 is prime.

Views

Author

Keywords

Comments

Crossrefs