A304387 -id:A304387 - cp's OEIS frontend

A358094 a(n) is the number of ways n can be reached in the following method: we start with 1, then add or multiply alternately, and each operand must be 2 or 3.

1, 1, 2, 2, 2, 2, 0, 3, 2, 4, 3, 6, 2, 3, 5, 1, 2, 5, 1, 4, 2, 5, 2, 7, 3, 6, 5, 5, 3, 9, 3, 5, 8, 2, 3, 11, 2, 7, 8, 3, 3, 9, 2, 7, 8, 4, 5, 8, 2, 6, 5, 7, 5, 13, 4, 9, 8, 5, 3, 10, 3, 9, 8, 8, 5, 14, 5, 7, 9, 3, 2, 13, 3, 10, 11, 8, 5, 19, 6, 11

Offset: 1

Yifan Xie and Thomas Scheuerle, Oct 29 2022

We may start either with multiplication or summation. After summation the next step will be multiplication or vice versa.
From Thomas Scheuerle, Oct 30 2022: (Start)
The only zero in this sequence is at a(7). Proof: Let k be any number greater than 1026. If k is even subtract 2, if k is odd subtract 3, then divide by two. Repeat this process until k < 1024. Obviously we will get some number between 511 and 1024. By computation it is known that all these numbers can be reached. They can be reached if we start with multiplication and if we start with addition we can reach all these numbers too.
Conjecture: All numbers greater than 145 can be reached in at least 3 different ways. Numbers greater than 145 which can be reached in only three ways are all of the form 27*2^k - 5 (A304387). This is conjectured to arise from the relation: 27*2^(k+2) - 5 = 3*(27*2^(k+1) - 5) - 2*(27*2^k - 5) which is in some sense here the worst case in between *2 and *3. (End)
Proof of the conjecture: We use the identities in A358095. For n > 145, if a(n) <= 2, A358095(n) <= 2. Therefore, n must be a*3*2^k - 2, where a is in the set {3, 7, 26, 30, 32, 34, 40, 49} and k is a positive integer. However, A358096(a*3*2^k - 2) = A358095(a*3*2^(k-1) - 1) >= 3, a contradiction. Hence all numbers greater than 145 can be reached in at least 3 different ways. If a(n) = 3, the only possibilities are that A358095(n) = 0 and A358096(n) = 3 or A358095(n) = 3 and A358096(n) = 0. For the first one, n must be 9*2^k - 2, so A358096(n) = A358095(9*2^(k-1) - 1) >= 4. For the second one, if n is in the form a*3*2^k - 2, A358096(n) = A358095(a*3*2^(k-1) - 1) >= 4; if n = 108*2^k - 3, A358096(n) = A358095(36*2^k - 1) >= 4; if n is in the form 108*2^k - 5, A358096(n) = 0. Hence a(n) = 3 iff n = 27*2^k - 5 for n > 145. - Yifan Xie, Jan 07 2025

			There are 3 ways reaching 8: (1+3)*2=8, (1*2+2)*2=8 and (1+2)*2+2=8, so a(8)=3.

Yifan Xie, Table of n, a(n) for n = 1..10000
Thomas Scheuerle, Red dots: Number of times n may be reached if we start with addition. Green dots: if we start with multiplication instead. For n = 1..3000.
Thomas Scheuerle, The number of ways n may be reached if we allow multiplication in all steps only by the same number. For n = 1..500.
Thomas Scheuerle, All possible trajectories for the first ten steps plotted in logarithmic scale.

Cf. A005836, A304387, A358095, A358096.

b:= proc(n, t) option remember; `if`(n=1, 1, add(`if`(t=1 and i `if`(n=1, 1, add(b(n, i), i=0..1)):
seq(a(n), n=1..80);  # Alois P. Heinz, Jan 12 2024

b[n_,t_]:=b[n, t]=If[n == 1,1,Sum[If[t == 1 && iJames C. McMahon, Jan 29 2024 *)

{ for (n=1, #a=vector(#m=vector(80)), if (n==1, a[n] = m[n] = 1, if (n-2>0, a[n] += m[n-2];); if (n-3>0, a[n] += m[n-3];); if (n%2==0, m[n] += a[n/2];); if (n%3==0, m[n] += a[n/3];);); print1 (a[n]+m[n]-(n==1)", ");); } \\ Rémy Sigrist, Oct 30 2022

a(n) = A358095(n) + A358096(n) for n > 1.
From Thomas Scheuerle, Oct 30 2022: (Start)
a(n + 2*(2^floor(log_2(n)) - 1) + b) >= 1, with b = {0, 2, 3}. This is the set of numbers which may be reached by only using *2.
a(A005836(n) + 2*(3^floor(log_3(n)) - 1) + b) >= 1, with b = {0, 2, 3}. These numbers can be reached by only using *3. (End)

A250653 Number of (n+1)X(5+1) 0..1 arrays with nondecreasing x(i,j)-x(i,j-1) in the i direction and nondecreasing min(x(i,j),x(i-1,j)) in the j direction.

Original entry on oeis.org

49, 103, 211, 427, 859, 1723, 3451, 6907, 13819, 27643, 55291, 110587, 221179, 442363, 884731, 1769467, 3538939, 7077883, 14155771, 28311547, 56623099, 113246203, 226492411, 452984827, 905969659, 1811939323, 3623878651

Offset: 1

R. H. Hardin, Nov 26 2014

nonn

Column 5 of A250656.

Since one edge length of the array is fixed, and the constraint is a Markov-type correlation between fixed-width lengths of the other edge, the generating function is computable by the usual transfer matrix method and therefore a rational polynomial. That predicts that there is a linear recurrence. - R. J. Mathar, May 25 2018

			Some solutions for n=4
..1..1..1..0..0..0....1..1..1..1..1..1....1..1..1..1..1..1....1..1..1..1..0..0
..0..0..0..0..0..0....1..1..1..1..1..1....1..1..1..1..1..1....0..0..0..0..0..0
..1..1..1..1..1..1....0..0..0..0..0..0....0..0..0..0..0..0....1..1..1..1..1..1
..1..1..1..1..1..1....0..0..0..0..0..0....0..0..0..0..0..0....1..1..1..1..1..1
..0..0..0..0..1..1....1..1..1..1..1..1....0..0..0..0..1..1....0..0..0..1..1..1

R. H. Hardin, Table of n, a(n) for n = 1..210

Cf. A304387.

Empirical: a(n) = 3*a(n-1) - 2*a(n-2); also a(n) = 2^(n-1)*25 + (5*2^(n-1)-1)*5 + 2^(n+1).

It appears that a(n) = 27*2^n-5, which would make this coincide with A304387. - N. J. A. Sloane, May 13 2018

A304388 a(n) = 144*2^n - 20 (n>=1).

Original entry on oeis.org

268, 556, 1132, 2284, 4588, 9196, 18412, 36844, 73708, 147436, 294892, 589804, 1179628, 2359276, 4718572, 9437164, 18874348, 37748716, 75497452, 150994924, 301989868, 603979756, 1207959532, 2415919084, 4831838188, 9663676396, 19327352812, 38654705644, 77309411308

Offset: 1

Emeric Deutsch, May 13 2018

a(n) is the second Zagreb index of the dendrimer nanostar NS1[n], defined pictorially in the Ashrafi et al. reference (Ns1[3] is shown in Fig. 1) or in the Ahmadi et al. reference (Fig. 1).
The second Zagreb index of a simple connected graph is the sum of the degree products d(i)d(j) over all edges ij of the graph.
The M-polynomial of NS1[n] is M(NS1[n]; x,y) = xy^4 + (9*2^n +3)x^2*y^2 + (18*2^n - 12)x^2*y^3 + 3x^3*y^4.

Colin Barker, Table of n, a(n) for n = 1..1000
M. B. Ahmadi and M. Sadeghimehr, Atom bond connectivity index of an infinite class NS1[n] of dendrimer nanostars, Optoelectronics and Advanced Materials, 4(7):1040-1042 July 2010.
Ali Reza Ashrafi and Parisa Nikzad, Kekulé index and bounds of energy for nanostar dendrimers, Digest J. of Nanomaterials and Biostructures, 4, No. 2, 2009, 383-388.
E. Deutsch and Sandi Klavzar, M-polynomial and degree-based topological indices, Iranian J. Math. Chemistry, 6, No. 2, 2015, 93-102.
Index entries for linear recurrences with constant coefficients, signature (3,-2).

Cf. A304386, A304387, A304389.

List([1..40],n->144*2^n-20); # Muniru A Asiru, May 13 2018

Maple
```
seq(144*2^n-20, n = 1 .. 40);
```

LinearRecurrence[{3,-2},{268,556},30] (* Harvey P. Dale, Nov 02 2021 *)

a(n) = 144*2^n - 20; \\ Altug Alkan, May 13 2018

Vec(4*x*(67 - 62*x) / ((1 - x)*(1 - 2*x)) + O(x^40)) \\ Colin Barker, May 18 2018

From Colin Barker, May 18 2018: (Start)
G.f.: 4*x*(67 - 62*x) / ((1 - x)*(1 - 2*x)).
a(n) = 3*a(n-1) - 2*a(n-2) for n>2.
(End)

A304389 a(n) = 126*2^n - 22 (n>=1).

Original entry on oeis.org

230, 482, 986, 1994, 4010, 8042, 16106, 32234, 64490, 129002, 258026, 516074, 1032170, 2064362, 4128746, 8257514, 16515050, 33030122, 66060266, 132120554, 264241130, 528482282, 1056964586, 2113929194, 4227858410, 8455716842, 16911433706, 33822867434, 67645734890, 135291469802, 270582939626, 541165879274

Offset: 1

Emeric Deutsch, May 13 2018

a(n) is the first Zagreb index of the dendrimer nanostar NS1[n], defined pictorially in the Ashrafi et al. reference (Ns1[3] is shown in Fig. 1) or in the Ahmadi et al. reference (Fig. 1).
The first Zagreb index of a simple connected graph is the sum of the squared degrees of its vertices. Alternatively, it is the sum of the degree sums d(i) + d(j) over all edges ij of the graph.
The M-polynomial of NS1[n] is M(NS1[n]; x,y) = xy^4 + (9*2^n + 3)x^2*y^2 + (18*2^n - 12)x^2*y^3 + 3x^3*y^4 .

Colin Barker, Table of n, a(n) for n = 1..1000
M. B. Ahmadi and M. Sadeghimehr, Atom bond connectivity index of an infinite class NS1[n] of dendrimer nanostars, Optoelectronics and Advanced Materials, 4(7):1040-1042 July 2010.
Ali Reza Ashrafi and Parisa Nikzad, Kekulé index and bounds of energy for nanostar dendrimers, Digest J. of Nanomaterials and Biostructures, 4, No. 2, 2009, 383-388.
E. Deutsch and Sandi Klavzar, M-polynomial and degree-based topological indices, Iranian J. Math. Chemistry, 6, No. 2, 2015, 93-102.
Index entries for linear recurrences with constant coefficients, signature (3,-2).

Cf. A304386, A304387, A304388.

List([1..40],n->126*2^n-22); # Muniru A Asiru, May 13 2018

Maple
```
seq(126*2^n-22, n = 1 .. 40);
```

a(n) = 126*2^n - 22; \\ Altug Alkan, May 13 2018

Vec(2*x*(115 - 104*x) / ((1 - x)*(1 - 2*x)) + O(x^40)) \\ Colin Barker, May 18 2018

From Colin Barker, May 18 2018: (Start)
G.f.: 2*x*(115 - 104*x) / ((1 - x)*(1 - 2*x)).
a(n) = 3*a(n-1) - 2*a(n-2) for n>2.
(End)

cp's OEIS Frontend

A358094 a(n) is the number of ways n can be reached in the following method: we start with 1, then add or multiply alternately, and each operand must be 2 or 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A250653 Number of (n+1)X(5+1) 0..1 arrays with nondecreasing x(i,j)-x(i,j-1) in the i direction and nondecreasing min(x(i,j),x(i-1,j)) in the j direction.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A304388 a(n) = 144*2^n - 20 (n>=1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Maple

Mathematica

PARI

PARI

Formula

A304389 a(n) = 126*2^n - 22 (n>=1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Maple

PARI

PARI

Formula