login
a(n) is the number of ways n can be reached in the algorithm explained in A358094 if the last operation is multiplication.
3

%I #30 Dec 31 2023 13:24:56

%S 1,1,1,0,0,1,0,2,1,2,0,3,0,0,2,1,0,2,0,2,0,3,0,4,0,2,1,3,0,5,0,0,3,2,

%T 0,6,0,1,2,2,0,5,0,2,3,2,0,3,0,3,2,4,0,7,0,2,1,3,0,6,0,3,2,5,0,7,0,0,

%U 2,3,0,8,0,2,3,6,0,10,0,1

%N a(n) is the number of ways n can be reached in the algorithm explained in A358094 if the last operation is multiplication.

%H Yifan Xie, <a href="/A358096/b358096.txt">Table of n, a(n) for n = 1..10000</a>

%F a(n) = A358095(n/2) + A358095(n/3) if n == 0 (mod 6);

%F a(n) = A358095(n/2) if n == 2 or 4 (mod 6);

%F a(n) = A358095(n/3) if n == 3 (mod 6);

%F a(n) = 0 if n == 1 or 5 (mod 6).

%e There are 3 ways to reach 12: (1*3+3)*2=12, (1*2+2)*3=12 and (1+3)*3=12.

%o (C++) #include <iostream>

%o 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, 1)<<", "; cout<<f(n, 1); return 0; }

%Y Cf. A358094, A358095.

%K nonn,easy

%O 1,8

%A _Yifan Xie_, Nov 01 2022