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,4

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.

Links

Table of n, a(n) for n=1..86.

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

Example

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

Maple

b:= proc(n, t) option remember; `if`(n=1, 1, add(`if`(t=1 and i<n,
      b(n-i, 1-t), `if`(t=0 and irem(n, i)=0, b(n/i, 1-t), 0)), i=3..5))
    end:
a:= n-> `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 *)

Prog

(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)", "); );

Crossrefs

Cf. A358094.

Sequence in context: A157372 A270559 A231727 * A384931 A382447 A270616

Adjacent sequences: A368873 A368874 A368875 * A368877 A368878 A368879

Keyword

nonn,easy

Author

Yifan Xie, Jan 08 2024

Status

approved