A030017 -id:A030017 - cp's OEIS frontend

A340991 Triangle T(n,k) whose k-th column is the k-fold self-convolution of the primes; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 2, 0, 3, 4, 0, 5, 12, 8, 0, 7, 29, 36, 16, 0, 11, 58, 114, 96, 32, 0, 13, 111, 291, 376, 240, 64, 0, 17, 188, 669, 1160, 1120, 576, 128, 0, 19, 305, 1386, 3121, 4040, 3120, 1344, 256, 0, 23, 462, 2678, 7532, 12450, 12864, 8288, 3072, 512, 0, 29, 679, 4851, 16754, 34123, 44652, 38416, 21248, 6912, 1024

Offset: 0

Alois P. Heinz, Feb 01 2021

			Triangle T(n,k) begins:
  1;
  0,  2;
  0,  3,   4;
  0,  5,  12,    8;
  0,  7,  29,   36,   16;
  0, 11,  58,  114,   96,    32;
  0, 13, 111,  291,  376,   240,    64;
  0, 17, 188,  669, 1160,  1120,   576,  128;
  0, 19, 305, 1386, 3121,  4040,  3120, 1344,  256;
  0, 23, 462, 2678, 7532, 12450, 12864, 8288, 3072, 512;
  ...

Alois P. Heinz, Rows n = 0..200, flattened

Columns k=0-4 give (offsets may differ): A000007, A000040, A014342, A014343, A014344.
Main diagonal gives A000079.
Row sums give A030017(n+1).
T(2n,n) gives A340990.
Cf. A030018, A030281.

T:= proc(n, k) option remember; `if`(k=0, `if`(n=0, 1, 0),
      `if`(k=1, `if`(n=0, 0, ithprime(n)), (q->
       add(T(j, q)*T(n-j, k-q), j=0..n))(iquo(k, 2))))
    end:
seq(seq(T(n, k), k=0..n), n=0..12);
# Uses function PMatrix from A357368.
PMatrix(10, ithprime); # Peter Luschny, Oct 09 2022

T[n_, k_] := T[n, k] = If[k == 0, If[n == 0, 1, 0],
     If[k == 1, If[n == 0, 0, Prime[n]], With[{q = Quotient[k, 2]},
     Sum[T[j, q] T[n - j, k - q], {j, 0, n}]]]];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Feb 10 2021, after Alois P. Heinz *)

T(n,k) = [x^n] (Sum_{j>=1} prime(j)*x^j)^k.
Sum_{k=0..n} k * T(n,k) = A030281(n).
Sum_{k=0..n} (-1)^k * T(n,k) = A030018(n).
Conjecture: row polynomials are x*R(n,1) for n > 0 where R(n,k) = R(n-1,k+1) + x*R(n-1,1)*R(1,k) for n > 1, k > 0 with R(1,k) = prime(k) for k > 0. The same recursion seems to work for self-convolution of any other sequence. - Mikhail Kurkov, Apr 05 2025

A060801 Invert transform of odd numbers: a(n) = Sum_{k=1..n} (2k+1)a(n-k), a(0)=1.

Original entry on oeis.org

1, 3, 14, 64, 292, 1332, 6076, 27716, 126428, 576708, 2630684, 12000004, 54738652, 249693252, 1138988956, 5195558276, 23699813468, 108107950788, 493140127004, 2249484733444, 10261143413212, 46806747599172, 213511451169436

Offset: 0

Vladeta Jovovic, Apr 27 2001

a(n) is the number of generalized compositions of n when there are 2*i+1 different types of i, (i=1,2,...). - Milan Janjic, Sep 24 2010

Colin Barker, Table of n, a(n) for n = 0..1000
Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, (an + b)-color compositions, arXiv:1707.07798 [math.CO], 2017.
Stéphane Ouvry and Alexios P. Polychronakos, Signed area enumeration for lattice walks, Séminaire Lotharingien de Combinatoire (2023) Vol. 87B.
N. J. A. Sloane, Transforms
Index entries for linear recurrences with constant coefficients, signature (5,-2).

Cf. A001906, A052530, A033453, A030017, A052913 (partial sums).

Join[{1}, LinearRecurrence[{5, -2}, {3, 14}, 22]] (* Jean-François Alcover, Aug 07 2018 *)

Vec((1 - x)^2 / (1 - 5*x + 2*x^2) + O(x^25)) \\ Colin Barker, Mar 19 2019

G.f.: (x^2-2*x+1)/(2*x^2-5*x+1).
G.f.: 1 / (1 - 3*x - 5*x^2 - 7*x^3 - 9*x^4 - 11*x^5 - ...). - Gary W. Adamson, Jul 27 2009
a(n) = 5*a(n-1) - 2*a(n-2) with a(1) = 3, a(2) = 14, for n >= 3. - Taras Goy, Mar 19 2019
a(n) = (2^(-2-n)*((5-sqrt(17))^n*(-7+sqrt(17)) + (5+sqrt(17))^n*(7+sqrt(17)))) / sqrt(17) for n > 0. - Colin Barker, Mar 19 2019
a(n) = A052913(n)-A052913(n-1). - R. J. Mathar, Sep 20 2020

A300662 Expansion of 1/(1 - x - Sum_{k>=2} prime(k-1)*x^k).

Original entry on oeis.org

1, 1, 3, 8, 22, 59, 160, 429, 1155, 3105, 8354, 22474, 60457, 162636, 437509, 1176941, 3166097, 8517138, 22912002, 61635707, 165806564, 446037175, 1199887133, 3227823181, 8683185454, 23358686444, 62837334885, 169039070970, 454732963567, 1223279724439, 3290751724917

Offset: 0

Ilya Gutkovskiy, Mar 10 2018

nonn

Invert transform of A008578.

Alois P. Heinz, Table of n, a(n) for n = 0..2327
N. J. A. Sloane, Transforms

Cf. A000040, A008578, A023626, A030011, A030012, A030013, A030014, A030015, A030016, A030017, A030018, A292744, A300632.

a:= proc(n) option remember; `if`(n=0, 1, add(
     `if`(j=1, 1, ithprime(j-1))*a(n-j), j=1..n))
    end:
seq(a(n), n=0..35);  # Alois P. Heinz, Mar 10 2018

nmax = 30; CoefficientList[Series[1/(1 - x - Sum[Prime[k - 1] x^k, {k, 2, nmax}]), {x, 0, nmax}], x]
p[1] = 1; p[n_] := p[n] = Prime[n - 1]; a[n_] := a[n] = Sum[p[k] a[n - k], {k, 1, n}]; a[0] = 1; Table[a[n], {n, 0, 30}]

G.f.: 1/(1 - Sum_{k>=1} A008578(k)*x^k).

A382255 Heinz number of the partition corresponding to run lengths in the bits of n.

Original entry on oeis.org

1, 2, 4, 3, 6, 8, 6, 5, 10, 12, 16, 12, 9, 12, 10, 7, 14, 20, 24, 18, 24, 32, 24, 20, 15, 18, 24, 18, 15, 20, 14, 11, 22, 28, 40, 30, 36, 48, 36, 30, 40, 48, 64, 48, 36, 48, 40, 28, 21, 30, 36, 27, 36, 48, 36, 30, 25, 30, 40, 30, 21, 28, 22, 13, 26, 44, 56, 42

Offset: 0

M. F. Hasler and Ali Sada, Mar 19 2025

The run lengths (number of consecutive bits that are equal) in the binary numbers in [2^(L-1), 2^L-1], i.e., of bit length L, yield all possible compositions of L, i.e., the partitions with any possible order of the parts.
Associated to any composition (p1, ..., pK) is their Heinz number prime(p1)*...*prime(pK) which depends only on the partition, i.e., not on the order of the parts.
The sequence can also be read as a table with row lengths 1, 1, 2, 4, 8, 16, 32, ... (= A011782), where row L = 0, 1, 2, 3, ... lists the 2^(L-1) compositions of L through their Heinz numbers (which will appear more than once if they contain at least two distinct parts).

			   n | binary | partition | a(n) = Heinz number
  ---+--------+-----------+--------------------
   0 |   (0)  | empty sum | 1 = empty product
   1 |     1  |     1     | 2 = prime(1)
   2 |    10  |    1+1    | 4 = prime(1) * prime(1)
   3 |    11  |     2     | 3 = prime(2)
   4 |   100  |    1+2    | 6 = prime(1) * prime(2)
   5 |   101  |   1+1+1   | 8 = 2^3 = prime(1) * prime(1) * prime(1)
   6 |   110  |    2+1    | 6 = prime(2) * prime(1)
   7 |   111  |     3     | 5 = prime(3)
   8 |  1000  |    1+3    | 10 = 2*5 = prime(1) * prime(3)
   9 |  1001  |   1+2+1   | 12 = 2^2*3 = prime(1) * prime(2) * prime(1)
  ...|   ...  |    ...    | ...
For example, n = 4 = 100[2] (in binary) has run lengths (1, 2), namely: one bit 1 followed by two bits 0. This gives a(4) = prime(1)*prime(2) = 6.
Next, n = 5 = 101[2] (in binary) has run lengths (1, 1, 1): one bit 1, followed by one bit 0, followed by one bit 1. This gives a(4) = prime(1)^3 = 8.
Then, n = 6 = 110[2] (in binary) has run lengths (2, 1): first two bits 1, then one bit 0. This is the same as for 4, just in reverse order, so it yields the same Heinz number a(6) = prime(2)*prime(1) = 6.
Then, n = 7 = 111[2] (in binary) has run lengths (3), namely: three bits 1. This gives a(5) = prime(3) = 5.
Sequence written as irregular triangle:
   1;
   2;
   4,  3;
   6,  8,  6,  5;
  10, 12, 16, 12,  9, 12, 10,  7;
  14, 20, 24, 18, 24, 32, 24, 20, 15, 18, 24, 18, 15, 20, 14, 11;
  ...

Alois P. Heinz, Table of n, a(n) for n = 0..32768

Cf. A112798 and A296150 (partitions sorted by Heinz number).
Cf. A185974, A334433, A334435, A334438, A334434, A129129, A334436 (partitions given as Heinz numbers, in Abramowitz-Stegun, Maple, Mathematica order).
For "constructive" lists of partitions see A036036 (Abramowitz and Stegun order), A036036 (reversed), A080576 (Maple order), A080577 (Mathematica order).
Row sums of triangle give A030017(n+1).
Cf. A007088 (the binary numbers).
Cf. A011782, A001747, A001749, A008578.
Cf. A101211 (the run lengths as rows of a table).

a:= proc(n) option remember; `if`(n<2, 1+n, (p->
      a(iquo(n, 2^p))*ithprime(p))(padic[ordp](n+(n mod 2), 2)))
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Mar 20 2025

Heinz(p)=vecprod([ prime(k) | k <- p ])
RL(v) = if(#v, v=Vec(select(t->t,concat([1,v[^1]-v[^-1],1]),1)); v[^1]-v[^-1])
apply( {A382255(n) = Heinz(RL(binary(n)))}, [0..99] )

a(2^n) = A001747(n+1).
a(2^n-1) = A008578(n+1).
a(2^n+1) = A001749(n-1) for n>=2.

A030281 COMPOSE natural numbers with primes.

Original entry on oeis.org

2, 11, 53, 237, 1013, 4196, 16992, 67647, 265743, 1032827, 3979023, 15217248, 57835016, 218636365, 822691425, 3083074193, 11512489353, 42851360088, 159043175322, 588767623587, 2174488780469, 8013945343961, 29477541831841, 108233492257428, 396751988675780

Offset: 1

Christian G. Bower

Alois P. Heinz, Table of n, a(n) for n = 1..1823
N. J. A. Sloane, Transforms

Cf. A000040, A030017, A030282, A340991.

b:= proc(n) option remember; `if`(n=0, [1, 0], (p->
      p+[0, p[1]])(add(ithprime(j)*b(n-j), j=1..n)))
    end:
a:= n-> b(n)[2]:
seq(a(n), n=1..27);  # Alois P. Heinz, Sep 11 2019

b[n_] := b[n] = If[n==0, {1, 0}, #+{0, #[[1]]}&[Sum[Prime[j] b[n-j], {j, 1, n}]]];
a[n_] := b[n][[2]];
Array[a, 27] (* Jean-François Alcover, Nov 09 2020, after Alois P. Heinz *)

G.f.: Sum_{j>=1} j*(Sum_{k>=1} prime(k)*x^k)^j. - Ilya Gutkovskiy, Apr 21 2019

a(n) = Sum_{k=0..n} k * A340991(n,k). - Alois P. Heinz, Feb 01 2021

A289847 p-INVERT of the primes (A000040), where p(S) = 1 - S - S^2.

Original entry on oeis.org

2, 11, 53, 253, 1205, 5740, 27336, 130200, 620129, 2953634, 14067934, 67004505, 319137367, 1520027050, 7239773429, 34482491204, 164237487721, 782250685197, 3725800625523, 17745705518523, 84521448139914, 402569240665810, 1917406730442806, 9132462688572345

Offset: 0

Clark Kimberling, Aug 14 2017

Suppose s = (c(0), c(1), c(2), ...) is a sequence and p(S) is a polynomial. Let S(x) = c(0)*x + c(1)*x^2 + c(2)*x^3 + ... and T(x) = (-p(0) + 1/p(S(x)))/x. The p-INVERT of s is the sequence t(s) of coefficients in the Maclaurin series for T(x). Taking p(S) = 1 - S gives the "INVERT" transform of s, so that p-INVERT is a generalization of the "INVERT" transform (e.g., A033453).

See A289780 for a guide to related sequences.

Cf. A000040, A030017 ("INVERT" applied to the primes), A289928.

z = 60; s = Sum[Prime[k] x^k, {k, 1, z}]; p = 1 - s - s^2;
Drop[CoefficientList[Series[s, {x, 0, z}], x], 1]  (* A000040 *)
Drop[CoefficientList[Series[1/p, {x, 0, z}], x] , 1](* A289847 *)

A292744 a(0) = 1; a(n) = Sum_{k=1..n} prime(k+1)*a(n-k).

Original entry on oeis.org

1, 3, 14, 64, 294, 1346, 6166, 28242, 129362, 592538, 2714096, 12431808, 56943398, 260826950, 1194707382, 5472309246, 25065693008, 114812401444, 525893599720, 2408834540066, 11033569993066, 50538824799712, 231491059896394, 1060335514811206, 4856824295820082, 22246488881086116

Offset: 0

Ilya Gutkovskiy, Sep 22 2017

nonn

Invert transform of the odd primes.

Number of compositions (ordered partitions) of n where there are prime(k+1) sorts of part k.

M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72. Erratum 320 (2000), 210. [Link to arXiv version]
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
N. J. A. Sloane, Transforms
Index entries for sequences related to compositions

Cf. A030017, A060801, A065091.

a[0] = 1; a[n_] := a[n] = Sum[Prime[k + 1] a[n - k], {k, 1, n}]; Table[a[n], {n, 0, 25}]
nmax = 25; CoefficientList[Series[1/(1 - Sum[Prime[k + 1] x^k, {k, 1, nmax}]), {x, 0, nmax}], x]

t=26; Vec(1/(1-sum(k=1, t, prime(k+1)*x^k)) + O(x^t)) \\ Felix Fröhlich, Sep 22 2017

G.f.: 1/(1 - Sum_{k>=1} prime(k+1)*x^k).

A307770 Expansion of e.g.f. 1/(1 - Sum_{k>=1} prime(k)*x^k/k!).

Original entry on oeis.org

1, 2, 11, 89, 957, 12871, 207717, 3910931, 84155053, 2037195551, 54795228241, 1621233039941, 52328310410427, 1829742961027269, 68901415049874055, 2779901582389463177, 119635322278784511015, 5470390958849723994819, 264850557367286330886261, 13535194864326763053170325

Offset: 0

Ilya Gutkovskiy, Apr 27 2019

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..386

Cf. A000040, A007446, A030017, A302191, A302192, A302194.

a:= proc(n) option remember; `if`(n=0, 1, add(
      binomial(n, j)*ithprime(j)*a(n-j), j=1..n))
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Jun 24 2021

nmax = 19; CoefficientList[Series[1/(1 - Sum[Prime[k] x^k/k!, {k, 1, nmax}]), {x, 0, nmax}], x] Range[0, nmax]!

A307898 Expansion of 1/(1 - x * Sum_{k>=1} prime(k)*x^k).

Original entry on oeis.org

1, 0, 2, 3, 9, 19, 48, 107, 258, 594, 1405, 3277, 7693, 18004, 42203, 98834, 231592, 542497, 1271003, 2977529, 6975674, 16342011, 38285178, 89691782, 210124363, 492265243, 1153247379, 2701752062, 6329489153, 14828313076, 34738805240, 81383803849, 190660665579, 446667359857, 1046423138962

Offset: 0

Ilya Gutkovskiy, May 04 2019

nonn

Antidiagonal sums of square array, in which row m equals the m-fold convolution of primes with themselves.

Cf. A000040, A030017, A030018, A300662, A307899.

nmax = 34; CoefficientList[Series[1/(1 - x Sum[Prime[k] x^k, {k, 1, nmax}]), {x, 0, nmax}], x]
a[0] = 1; a[n_] := a[n] = Sum[Prime[k] a[n - k - 1], {k, 1, n - 1}]; Table[a[n], {n, 0, 34}]

Recurrence: a(n+1) = Sum_{k=1..n} prime(k)*a(n-k).

A307899 Expansion of 1/(1 + x * Sum_{k>=1} prime(k)*x^k).

Original entry on oeis.org

1, 0, -2, -3, -1, 5, 10, 9, -4, -26, -43, -33, 35, 148, 219, 98, -316, -857, -983, 23, 2296, 4501, 3712, -2906, -14257, -21771, -10811, 28282, 81209, 97292, 7960, -207185, -431595, -386033, 219344, 1322141, 2134126, 1226554, -2443765, -7684081, -9726127, -1791806, 18712361, 41428590, 39753658

Offset: 0

Ilya Gutkovskiy, May 04 2019

sign

Alternating antidiagonal sums of square array, in which row m equals the m-fold convolution of primes with themselves.

Cf. A000040, A030017, A030018, A307898.

nmax = 44; CoefficientList[Series[1/(1 + x Sum[Prime[k] x^k, {k, 1, nmax}]), {x, 0, nmax}], x]
a[0] = 1; a[n_] := a[n] = -Sum[Prime[k] a[n - k - 1], {k, 1, n - 1}]; Table[a[n], {n, 0, 44}]

Recurrence: a(n+1) = -Sum_{k=1..n} prime(k)*a(n-k).

cp's OEIS Frontend

A340991 Triangle T(n,k) whose k-th column is the k-fold self-convolution of the primes; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A060801 Invert transform of odd numbers: a(n) = Sum_{k=1..n} (2*k+1)*a(n-k), a(0)=1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A300662 Expansion of 1/(1 - x - Sum_{k>=2} prime(k-1)*x^k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A382255 Heinz number of the partition corresponding to run lengths in the bits of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

A030281 COMPOSE natural numbers with primes.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A289847 p-INVERT of the primes (A000040), where p(S) = 1 - S - S^2.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A292744 a(0) = 1; a(n) = Sum_{k=1..n} prime(k+1)*a(n-k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A307770 Expansion of e.g.f. 1/(1 - Sum_{k>=1} prime(k)*x^k/k!).

Views

Author

Keywords

Links

A060801 Invert transform of odd numbers: a(n) = Sum_{k=1..n} (2k+1)a(n-k), a(0)=1.