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

1, 0, 1, 2, 2, 2, 2, 3, 2, 1, 0, 1, 0, 0, 2, 2, 1, 3, 2, 4, 5, 2, 4, 9, 5, 2, 7, 8, 6, 6, 4, 7, 5, 3, 8, 5, 3, 2, 4, 8, 2, 0, 4, 4, 7, 0, 0, 4, 3, 4, 2, 1, 2, 3, 2, 1, 3, 1, 1, 5, 2, 2, 6, 4, 3, 5, 4, 5, 7, 2, 3, 10, 5, 4, 10, 7, 5, 7, 7, 10, 9, 2, 5, 17, 9, 5

Offset: 1

Author

Yifan Xie, Jan 08 2024

Keywords

• nonn
• easy

Comments

We may start either with multiplication or summation. After summation the next step will be multiplication or vice versa.

The only zeros in this sequence are at a(n) where n=2, 11, 13, 14, 42, 46, 47, 142, 146, 442; the only ones in this sequence are at a(n) where n=1, 3, 10, 12, 17, 52, 56, 58, 59, 182.

Proof: (Start) Let k be any number greater than 1334. If k == 0 (mod 3) subtract 3, if k == 1 subtract 4, if k == 2 subtract 5, then divide by 3. Repeat this process until k < 1335. Obviously we will get some number between 443 and 1334. By computation it is known that all these numbers can be reached, so all numbers > 442 can be reached, thus the zeros in this sequence can be verified.

Similarly, if k > 1334 can only be reached in one way, some number between 443 and 1334 can be reached in no more than one way, which is a contradiction, thus the ones in this sequence can also be verified. (End)

The graphs represent a fluctuating upward trend. This is caused by an "outlier" at a(2) = 0, whose effect is amplified with recursion.

Examples

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

Links

• Yifan Xie, Graph of the terms n = 1..10000.

Crossrefs

Cf. A358094.

Programs

Maple

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..86);  # Alois P. Heinz, Jan 12 2024

Mathematica

b[n_, t_] := b[n, t] = If[n == 1, 1, Sum[If[t == 1 && i < n,
   b[n-i, 1-t], If[t == 0 && Mod[n, i] == 0, b[n/i, 1-t], 0]], {i, 3, 5}]];
a[n_] := If[n == 1, 1, Sum[b[n, i], {i, 0, 1}]];
Table[a[n], {n, 1, 86}] (* Jean-François Alcover, Feb 03 2025, after Alois P. Heinz *)

PARI

for (n=1, #a=vector(#m=vector(86)), if (n==1, a[n] = m[n] = 1, if (n-3>0, a[n] += m[n-3]; ); if (n-4>0, a[n] += m[n-4]; ); if (n-5>0, a[n] += m[n-5]; ); if (n%3==0, m[n] += a[n/3]; ); if (n%4==0, m[n] += a[n/4]; ); if (n%5==0, m[n] += a[n/5]; ); ); print1(a[n]+m[n]-(n==1)", "); );