A006127 -id:A006127 - cp's OEIS frontend

A267112 Permutation of natural numbers: a(1) = 1; a(2n) = A087686(1+a(n)), a(2n+1) = A088359(a(n)), where A088359 and A087686 = numbers that occur only once (resp. more than once) in A004001.

1, 2, 3, 4, 5, 7, 6, 8, 9, 12, 10, 15, 13, 14, 11, 16, 17, 21, 18, 27, 22, 24, 19, 31, 28, 29, 23, 30, 25, 26, 20, 32, 33, 38, 34, 48, 39, 42, 35, 58, 49, 51, 40, 54, 43, 45, 36, 63, 59, 60, 50, 61, 52, 53, 41, 62, 55, 56, 44, 57, 46, 47, 37, 64, 65, 71, 66, 86, 72, 76, 67, 106, 87, 90, 73, 96, 77, 80, 68, 121, 107, 109, 88

Offset: 1

Antti Karttunen, Jan 10 2016

This sequence can be represented as a binary tree. Each left hand child is produced as A087686(1+n), and each right hand child as A088359(n), when their parent contains n:
                                    |
                 ...................1...................
                2                                       3
      4......../ \........5                   7......../ \........6
     / \                 / \                 / \                 / \
    /   \               /   \               /   \               /   \
   /     \             /     \             /     \             /     \
  8       9          12       10         15       13         14       11
16 17   21 18      27  22   24  19     31  28   29  23     30  25   26  20
etc.
The level k of the tree contains all numbers of binary width k, like many base-2 related permutations (A003188, A054429, etc). For a proof, see A267110, which gives the contents of each parent node (for node containing n).
A276442 shows the mirror-image of the same tree.

Antti Karttunen, Table of n, a(n) for n = 1..8192
T. Kubo and R. Vakil, On Conway's recursive sequence, Discr. Math. 152 (1996), 225-252.
Index entries for Hofstadter-type sequences
Index entries for sequences that are permutations of the natural numbers

Inverse: A267111.
Cf. A000079, A000225, A004001, A006127, A087686, A088359, A267110.
Similar or related permutations: A003188, A054429, A276442, A233276, A233278, A276344, A276346, A276446.
Cf. also permutations A266411, A266412 and arrays A265901, A265903.

a(1) = 1; after which, a(2n) = A087686(1+a(n)), a(2n+1) = A088359(a(n)).
As a composition of other permutations:
a(n) = A276442(A054429(n)).
a(n) = A276344(A233276(n)).
a(n) = A276346(A233278(n)).
a(n) = A276446(A003188(n)).
Other identities. For all n >= 0:
a(2^n) = 2^n. [Follows from the properties (3) and (4) of A004001 given on page 227 of Kubo & Vakil paper.]
a(A000225(n)) = A006127(n), i.e., a((2^(n+1)) - 1) = 2^n + n. [Numbers at the right edge.]

A081552 Leading terms of rows in A081551.

Original entry on oeis.org

1, 11, 102, 1003, 10004, 100005, 1000006, 10000007, 100000008, 1000000009, 10000000010, 100000000011, 1000000000012, 10000000000013, 100000000000014, 1000000000000015, 10000000000000016, 100000000000000017, 1000000000000000018

Offset: 1

Amarnath Murthy, Apr 01 2003

More generally, a(n) = B^K + n; K = floor(log_B a(n-1)) + 1. This sequence has B=10, a(0)=1; A006127 has B=2, a(0)=1; A052944 has B=2, a(0)=2; A104743 has B=3, a(0)=1; A104745 has B=5, a(0)=1. - Ctibor O. Zizka, Mar 22 2008

Vincenzo Librandi, Table of n, a(n) for n = 1..300
Index entries for linear recurrences with constant coefficients, signature (12,-21,10).

Cf. A011557, A081551, A081553, A085952 (first differences, after n=2).

[10^(n-1)+n-1: n in [1..20]]; // Vincenzo Librandi, Jun 16 2013

I:=[1, 11, 102]; [n le 3 select I[n] else 12*Self(n-1)-21*Self(n-2)+10*Self(n-3): n in [1..30]]; // Vincenzo Librandi, Jun 16 2013

seq(10^(n-1) +n-1, n=1..40); # G. C. Greubel, May 27 2021

Table[10^(n-1) +n-1, {n,30}] (* or *) CoefficientList[Series[(1-x-9x^2)/((1-10x)(1-x)^2), {x, 0, 30}], x]  (* Vincenzo Librandi, Jun 16 2013 *)

[10^(n-1) +n-1 for n in (1..40)] # G. C. Greubel, May 27 2021

a(n) = 10^(n-1) + n-1.
G.f.: x*(1 -x -9*x^2)/((1-10*x)*(1-x)^2). - Vincenzo Librandi, Jun 16 2013
a(n) = 12*a(n-1) -21*a(n-2) +10*a(n-3). - Vincenzo Librandi, Jun 16 2013
E.g.f.: (1/10)*(9 - 10*(1-x)*exp(x) + exp(10*x)). - G. C. Greubel, May 27 2021

A158879 a(n) = 4^n + n.

Original entry on oeis.org

1, 5, 18, 67, 260, 1029, 4102, 16391, 65544, 262153, 1048586, 4194315, 16777228, 67108877, 268435470, 1073741839, 4294967312, 17179869201, 68719476754, 274877906963, 1099511627796, 4398046511125, 17592186044438, 70368744177687

Offset: 0

Philippe Deléham, Mar 28 2009

			a(0)=4^0+0 = 1, a(1)=4^1+1 = 5, a(2)=4^2+2 = 18, a(3)=4^3+3 = 67, ...

Vincenzo Librandi, Table of n, a(n) for n = 0..300
Index entries for linear recurrences with constant coefficients, signature (6,-9,4).

Cf. A006127, A081552, A104743, A104745.

List([0..30], n-> n+4^n); # G. C. Greubel, Mar 04 2020

[4^n+n: n in [0..30]]; // Vincenzo Librandi, Jun 16 2013

seq( 4^n+n, n=0..30); # G. C. Greubel, Mar 04 2020

Table[4^n+n,{n,0,40}] (* Vladimir Joseph Stephan Orlovsky, May 19 2011 *)
CoefficientList[Series[(1-x-3x^2)/((1-4x)(1-x)^2), {x, 0, 30}], x] (* Vincenzo Librandi, Jun 16 2013 *)
LinearRecurrence[{6,-9,4},{1,5,18},30] (* Harvey P. Dale, Jun 02 2016 *)

a(n)=4^n+n \\ Charles R Greathouse IV, Oct 07 2015

[n+4^n for n in (0..30)] # G. C. Greubel, Mar 04 2020

G.f.: (1 - x - 3*x^2)/((1-4*x)*(1-x)^2). - R. J. Mathar, Mar 29 2009
a(n) = 6*a(n-1) -9*a(n-2) +4*a(n-3). - R. J. Mathar, Mar 29 2009
E.g.f.: x*exp(x) + exp(4*x). - G. C. Greubel, Mar 04 2020

Corrected typo in a(22) from R. J. Mathar, Mar 29 2009

A121270 Prime Sierpinski numbers of the first kind: primes of the form k^k+1.

Original entry on oeis.org

2, 5, 257

Offset: 1

Alexander Adamchuk, Aug 23 2006

Sierpinski proved that k>1 must be of the form 2^(2^j) for k^k+1 to be a prime. All a(n) > 2 must be the Fermat numbers F(m) with m = j+2^j = A006127(j). [Edited by Jeppe Stig Nielsen, Jul 09 2023]

See e.g. pp. 156-157 in M. Krizek, F. Luca & L. Somer, 17 Lectures on Fermat Numbers, Springer-Verlag NY 2001. - Walter Nissen, Mar 20 2010

Eric Weisstein's World of Mathematics, Sierpinski Number of the First Kind

Primes of form b*k^k + 1: this sequence (b=1), A216148 (b=2), A301644 (b=3), A301641 (b=4), A301642 (b=16).

Cf. A014566, A048861, A006127, A000215.

Do[f=n^n+1;If[PrimeQ[f],Print[{n,f}]],{n,1,1000}]

for(n=1,9,if(ispseudoprime(t=n^n+1),print1(t", "))) \\ Charles R Greathouse IV, Feb 01 2013

Definition rewritten by Walter Nissen, Mar 20 2010

A131520 Number of partitions of the graph G_n (defined below) into "strokes".

Original entry on oeis.org

2, 6, 12, 22, 40, 74, 140, 270, 528, 1042, 2068, 4118, 8216, 16410, 32796, 65566, 131104, 262178, 524324, 1048614, 2097192, 4194346, 8388652, 16777262, 33554480, 67108914, 134217780, 268435510, 536870968, 1073741882, 2147483708

Offset: 1

Yasutoshi Kohmoto, Aug 15 2007

G_n = {V_n, E_n}, V_n = {v_1, v_2, ..., v_n}, E_n = {v_1 v_2, v_2 v_3, ..., v_{n-1} v_n, v_n v_1}
See the definition of "stroke" in A089243.
A partition of a graph G into strokes S_i must satisfy the following conditions, where H is a digraph on G:
- Union_{i} S_i = H,
- i != j => S_i and S_j do not have a common edge,
- i != j => S_i U S_j is not a directed path,
- For all i, S_i is a dipath.
a(n) is also the number of maximal subsemigroups of the monoid of partial order preserving mappings on a set with n elements. - James Mitchell and Wilf A. Wilson, Jul 21 2017

			Figure for G_4: o-o-o-o-o Two vertices on both sides are the same.

G. C. Greubel, Table of n, a(n) for n = 1..1000
James East, Jitender Kumar, James D. Mitchell, and Wilf A. Wilson, Maximal subsemigroups of finite transformation and partition monoids, arXiv:1706.04967 [math.GR], 2017. [_James Mitchell_ and _Wilf A. Wilson_, Jul 21 2017]
Index entries for linear recurrences with constant coefficients, signature (4,-5,2).

Cf. A131518, A173740, A354228.

[2^n + 2*(n-1): n in [1..30]]; // G. C. Greubel, Feb 13 2021

Table[2^n + 2*(n-1), {n, 30}] (* G. C. Greubel, Feb 13 2021 *)

[2^n + 2*(n-1) for n in (1..30)] # G. C. Greubel, Feb 13 2021

a(n) = 2*(n-1) + 2^n = 2*A006127(n-1).
G.f.: 2*x*(1 - x - x^2)/((1-x)^2 * (1-2*x)). - R. J. Mathar, Nov 14 2007
a(n) = 4*a(n-1)-5*a(n-2)+2*a(n-3). - Wesley Ivan Hurt, May 20 2021

More terms from Max Alekseyev, Sep 29 2007

A226199 a(n) = 7^n + n.

Original entry on oeis.org

1, 8, 51, 346, 2405, 16812, 117655, 823550, 5764809, 40353616, 282475259, 1977326754, 13841287213, 96889010420, 678223072863, 4747561509958, 33232930569617, 232630513987224, 1628413597910467, 11398895185373162, 79792266297612021, 558545864083284028, 3909821048582988071

Offset: 0

Vincenzo Librandi, Jun 16 2013

Smallest prime of this form is a(34) = 54116956037952111668959660883.

In general, the g.f. of a sequence of numbers of the form k^n + n is (1-x-(k-1)*x^2)/((1-k*x)*(x-1)^2) with main linear recurrence (k+2)*a(n-1) - (2*k+1)*a(n-2) + k*a(n-3). - Bruno Berselli, Jun 16 2013

Vincenzo Librandi, Table of n, a(n) for n = 0..300
Index entries for linear recurrences with constant coefficients, signature (9,-15,7).

Cf. numbers of the form k^n + n: A006127 (k=2), A104743 (k=3), A158879 (k=4), A104745 (k=5), A226200 (k=6), this sequence (k=7), A226201 (k=8), A226202 (k=9), A081552 (k=10), A226737 (k=11).

Cf. A199483 (first differences), A370657.

Magma
```
[7^n+n: n in [0..20]];
```

I:=[1, 8, 51]; [n le 3 select I[n] else 9*Self(n-1)-15*Self(n-2)+7*Self(n-3): n in [1..30]];

Table[7^n + n, {n, 0, 30}] (* or *) CoefficientList[Series[(1 - x - 6 x^2) / ((1 - 7 x) (1 - x)^2), {x, 0, 20}], x]
LinearRecurrence[{9,-15,7},{1,8,51},30] (* Harvey P. Dale, Jun 16 2025 *)

a(n)=7^n+n \\ Charles R Greathouse IV, Oct 07 2015

G.f.: (1-x-6*x^2)/((1-7*x)*(1-x)^2).
a(n) = 9*a(n-1) - 15*a(n-2) + 7*a(n-3).
E.g.f.: exp(x)*(exp(6*x) + x). - Elmo R. Oliveira, Mar 05 2025

A218577 Triangle read by rows: T(n,k) is the number of ascent sequences of length n with maximal element k-1.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 7, 6, 1, 1, 15, 25, 11, 1, 1, 31, 90, 74, 20, 1, 1, 63, 301, 402, 209, 37, 1, 1, 127, 966, 1951, 1629, 590, 70, 1, 1, 255, 3025, 8869, 10839, 6430, 1685, 135, 1, 1, 511, 9330, 38720, 65720, 56878, 25313, 4870, 264, 1

Offset: 1

Joerg Arndt, Nov 03 2012

Row sums are A022493.
Second column is A000225 (2^n - 1).
Third column appears to be A000392 (Stirling numbers S(n,3)).
Second diagonal (from the right) appears to be A006127 (2^n + n).

			Triangle starts:
1;
1,    1;
1,    3,     1;
1,    7,     6,      1;
1,   15,    25,     11,      1;
1,   31,    90,     74,     20,      1;
1,   63,   301,    402,    209,     37,      1;
1,  127,   966,   1951,   1629,    590,     70,     1;
1,  255,  3025,   8869,  10839,   6430,   1685,   135,     1;
1,  511,  9330,  38720,  65720,  56878,  25313,  4870,   264,   1;
1, 1023, 28501, 164676, 376114, 444337, 292695, 99996, 14209, 521, 1;
...
The 53 ascent sequences of length 5 are (dots for zeros):
[ #]     ascent-seq.   #max digit
[ 1]    [ . . . . . ]   0
[ 2]    [ . . . . 1 ]   1
[ 3]    [ . . . 1 . ]   1
[ 4]    [ . . . 1 1 ]   1
[ 5]    [ . . . 1 2 ]   2
[ 6]    [ . . 1 . . ]   1
[ 7]    [ . . 1 . 1 ]   1
[ 8]    [ . . 1 . 2 ]   2
[ 9]    [ . . 1 1 . ]   1
[10]    [ . . 1 1 1 ]   1
[11]    [ . . 1 1 2 ]   2
[12]    [ . . 1 2 . ]   2
[13]    [ . . 1 2 1 ]   2
[14]    [ . . 1 2 2 ]   2
[15]    [ . . 1 2 3 ]   3
[16]    [ . 1 . . . ]   1
[17]    [ . 1 . . 1 ]   1
[18]    [ . 1 . . 2 ]   2
[19]    [ . 1 . 1 . ]   1
[20]    [ . 1 . 1 1 ]   1
[21]    [ . 1 . 1 2 ]   2
[22]    [ . 1 . 1 3 ]   3
[23]    [ . 1 . 2 . ]   2
[24]    [ . 1 . 2 1 ]   2
[25]    [ . 1 . 2 2 ]   2
[26]    [ . 1 . 2 3 ]   3
[27]    [ . 1 1 . . ]   1
[28]    [ . 1 1 . 1 ]   1
[29]    [ . 1 1 . 2 ]   2
[...]
[49]    [ . 1 2 3 . ]   3
[50]    [ . 1 2 3 1 ]   3
[51]    [ . 1 2 3 2 ]   3
[52]    [ . 1 2 3 3 ]   3
[53]    [ . 1 2 3 4 ]   4
There is 1 sequence with maximum zero, 15 with maximum one, etc.,
therefore the fifth row is 1, 15, 25, 11, 1.

Joerg Arndt and Alois P. Heinz, Rows n = 1..141, flattened (first 15 rows from Joerg Arndt)
Mireille Bousquet-Mélou, Anders Claesson, Mark Dukes, Sergey Kitaev, (2+2)-free posets, ascent sequences and pattern avoiding permutations, arXiv:0806.0666 [math.CO], 2008-2009.
William Y. C. Chen, Alvin Y.L. Dai, Theodore Dokos, Tim Dwyer and Bruce E. Sagan, On 021-Avoiding Ascent Sequences, The Electronic Journal of Combinatorics Volume 20, Issue 1 (2013), #P76.

Cf. A022493 (number of ascent sequences), A137251 (ascent sequences with k ascents), A175579 (ascent sequences with k zeros).

Cf. A218579 (ascent sequences with last zero at position k-1), A218580 (ascent sequences with first occurrence of the maximal value at position k-1), A218581 (ascent sequences with last occurrence of the maximal value at position k-1).

A226201 a(n) = 8^n + n.

Original entry on oeis.org

1, 9, 66, 515, 4100, 32773, 262150, 2097159, 16777224, 134217737, 1073741834, 8589934603, 68719476748, 549755813901, 4398046511118, 35184372088847, 281474976710672, 2251799813685265, 18014398509482002, 144115188075855891, 1152921504606846996, 9223372036854775829

Offset: 0

Vincenzo Librandi, Jun 16 2013

Smallest prime of this form is a(101). - Bruno Berselli, Jun 17 2013

Vincenzo Librandi, Table of n, a(n) for n = 0..300
Index entries for linear recurrences with constant coefficients, signature (10,-17,8).

Cf. numbers of the form k^n+n: A006127 (k=2), A104743 (k=3), A158879 (k=4), A104745 (k=5), A226200 (k=6), A226199 (k=7), this sequence (k=8), A226202 (k=9), A081552 (k=10), A226737 (k=11).

Cf. A199555 (first differences).

Magma
```
[8^n+n: n in [0..30]];
```

I:=[1, 9, 66]; [n le 3 select I[n] else 10*Self(n-1)-17*Self(n-2)+8*Self(n-3): n in [1..30]];

Table[8^n + n, {n, 0, 30}] (* or *) CoefficientList[Series[(-1 + x + 7 x^2) / ((8 x - 1) (x - 1)^2), {x, 0, 30}], x]
LinearRecurrence[{10,-17,8},{1,9,66},30] (* Harvey P. Dale, Aug 11 2015 *)

a(n)=8^n+n \\ Charles R Greathouse IV, Oct 07 2015

G.f.: (-1+x+7*x^2)/((8*x-1)*(x-1)^2).
a(n) = 10*a(n-1) - 17*a(n-2) + 8*a(n-3).
E.g.f.: exp(x)*(exp(7*x) + x). - Elmo R. Oliveira, Mar 05 2025

A226202 a(n) = 9^n + n.

Original entry on oeis.org

1, 10, 83, 732, 6565, 59054, 531447, 4782976, 43046729, 387420498, 3486784411, 31381059620, 282429536493, 2541865828342, 22876792454975, 205891132094664, 1853020188851857, 16677181699666586, 150094635296999139, 1350851717672992108, 12157665459056928821, 109418989131512359230

Offset: 0

Vincenzo Librandi, Jun 16 2013

After 83, the next prime of this form is a(76). - Bruno Berselli, Jun 18 2013

Vincenzo Librandi, Table of n, a(n) for n = 0..300
Index entries for linear recurrences with constant coefficients, signature (11,-19,9).

Cf. numbers of the form k^n + n: A006127 (k=2), A104743 (k=3), A158879 (k=4), A104745 (k=5), A226200 (k=6), A226199 (k=7), A226201 (k=8), this sequence (k=9), A081552 (k=10), A226737 (k=11).

Cf. A199677 (first differences).

Magma
```
[9^n+n: n in [0..30]];
```

I:=[1, 10, 83]; [n le 3 select I[n] else 11*Self(n-1)-19*Self(n-2)+9*Self(n-3): n in [1..30]];

Table[9^n + n, {n, 0, 30}] (* or *) CoefficientList[Series[(- 1 + x + 8 x^2) / ((9 x - 1) (x - 1)^2), {x, 0, 30}], x]
LinearRecurrence[{11,-19,9},{1,10,83},20] (* Harvey P. Dale, Feb 03 2016 *)

a(n)=9^n+n \\ Charles R Greathouse IV, Oct 07 2015

G.f.: (-1+x+8*x^2)/((9*x-1)*(x-1)^2).
a(n) = 11*a(n-1) - 19*a(n-2) + 9*a(n-3).
E.g.f.: exp(x)*(exp(8*x) + x). - Elmo R. Oliveira, Sep 09 2024

A053221 Row sums of triangle A053218.

Original entry on oeis.org

1, 5, 16, 43, 106, 249, 568, 1271, 2806, 6133, 13300, 28659, 61426, 131057, 278512, 589807, 1245166, 2621421, 5505004, 11534315, 24117226, 50331625, 104857576, 218103783, 452984806, 939524069, 1946157028, 4026531811, 8321499106

Offset: 1

Asher Auel, Jan 01 2000

Considered as a vector, the sequence = A074909 * [1, 2, 3, ...], where A074909 is the beheaded Pascal's triangle as a matrix. - Gary W. Adamson, Mar 06 2012
a(n) is the sum of the upper left n X n subarray of A052509 (viewed as an infinite square array). For example (1+1+1) + (1+2+2) + (1+3+4) = 16. - J. M. Bergot, Nov 06 2012
Number of ternary strings of length n that contain at least one 2 and at most one 0. For example, a(3) = 16 since the strings are the 6 permutations of 201, the 3 permutations of 211, the 3 permutations of 220, the 3 permutations of 221, and 222. - Enrique Navarrete, Jul 25 2021

			a(4) = 4 + 7 + 12 + 20 = 43.

Michael De Vlieger, Table of n, a(n) for n = 1..3311
Index entries for linear recurrences with constant coefficients, signature (6,-13,12,-4).

Cf. A053218, A053219, A053220.

Cf. A006127, A074909.

[(n+2)*2^(n-1)-n-1: n in [1..50]]; // G. C. Greubel, Sep 03 2018

A053221 := proc(n) (n+2)*2^(n-1)-n-1 ; end proc: # R. J. Mathar, Sep 02 2011

Table[(n + 2)*2^(n - 1) - n - 1, {n, 29}] (* or *)
Rest@ CoefficientList[Series[-x (-1 + x + x^2)/((2 x - 1)^2*(x - 1)^2), {x, 0, 29}], x] (* Michael De Vlieger, Sep 22 2017 *)
LinearRecurrence[{6,-13,12,-4},{1,5,16,43},30] (* Harvey P. Dale, Jun 28 2021 *)

vector(50,n, (n+2)*2^(n-1)-n-1) \\ G. C. Greubel, Sep 03 2018

a(n) = (n+2)*2^(n-1)-n-1. - Vladeta Jovovic, Feb 28 2003
G.f.: -x*(-1+x+x^2) / ( (2*x-1)^2*(x-1)^2 ). - R. J. Mathar, Sep 02 2011
a(n) = (1/2) * Sum_{k=1..n} Sum_{i=1..n} C(k,i) + C(n,k). - Wesley Ivan Hurt, Sep 22 2017
E.g.f.: exp(x)*(exp(x)-1)*(1+x). - Enrique Navarrete, Jul 25 2021
a(n+1) = 2*a(n) + A006127(n). - Ya-Ping Lu, Jan 01 2024

cp's OEIS Frontend

A267112 Permutation of natural numbers: a(1) = 1; a(2n) = A087686(1+a(n)), a(2n+1) = A088359(a(n)), where A088359 and A087686 = numbers that occur only once (resp. more than once) in A004001.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A081552 Leading terms of rows in A081551.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Magma

Maple

Mathematica

Sage

Formula

A158879 a(n) = 4^n + n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A121270 Prime Sierpinski numbers of the first kind: primes of the form k^k+1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A131520 Number of partitions of the graph G_n (defined below) into "strokes".

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Sage

Formula

Extensions

A226199 a(n) = 7^n + n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Magma

Mathematica

PARI

Formula

A218577 Triangle read by rows: T(n,k) is the number of ascent sequences of length n with maximal element k-1.

Views