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

Comments

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)

Links

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.

Formula

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)

Example

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.

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=2..3))
    end:
a:= n-> `if`(n=1, 1, add(b(n, i), i=0..1)):
seq(a(n), n=1..80);  # 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, 2, 3}]]; a[n_]:=If[n==1, 1, Sum[b[n, i], {i, 0, 1}]]; Table[a[n], {n, 1, 80}] (* James C. McMahon, Jan 29 2024 *)

Prog

(C++) #include <iostream>
using namespace std; int f(int x, bool y) { if(x<0) return 0; if(x==1) return 1; if(y==0) return f(x-2, 1)+f(x-3, 1); if(y==1) { if(x%6==0) return f(x/2, 0)+f(x/3, 0); if(x%6==1||x%6==5) return 0; if(x%6==2||x%6==4) return f(x/2, 0); if(x%6==3) return f(x/3, 0); } }
int n; int main() { cin>>n; cout<<1<<", "; for(int i=2; i<n; i++) cout<<f(i, 0)+f(i, 1)<<", "; cout<<f(n, 0)+f(n, 1); return 0; }
(PARI) { 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

Crossrefs

Cf. A005836, A304387, A358095, A358096.

Sequence in context: A181089 A341894 A171932 * A305629 A214664 A214666

Adjacent sequences: A358091 A358092 A358093 * A358095 A358096 A358097

Keyword

nonn,easy

Author

Yifan Xie and Thomas Scheuerle, Oct 29 2022

Status

approved