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

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

Offset

1,4

Comments

From Yifan Xie, Jan 07 2025: (Start)

The following identities can be proved by induction (k, t are nonnegative integers):

a(n) = 0 iff n = 2 or n = 9*2^k - 2.

a(n) = 1 iff n = 1, 3, 6, 8, 9 or n = 21*2^k - 2.

If n > 71, a(n) = 2 iff n = m*3*2^k - 2, where m is in the set {26, 30, 32, 34, 40, 49}.

If n > 85, a(n) = 3 iff n = 108*2^k - 2, 108*2^k - 3, 108*2^k - 4, 108*2^k - 5, 123*2^k - 2, 126*2^k - 2, 132*2^k - 2, 150*2^k - 2, 174*2^k - 2, 210*2^k - 2, (108*2^t - 3)*2^k - 2.

If n > 60, a(n) = 4 iff n = 114*2^k - 2. (End)

Links

Yifan Xie, Table of n, a(n) for n = 1..10000

Formula

a(n) = A358096(n-2) + A358096(n-3) for n > 3.

a(6k) = a(2k-1) + a(3k-1); a(6k+1) = a(3k-1); a(6k+2) = a(6k+3) = a(2k) + a(3k); a(6k+4) = a(3k+1); a(6k+5) = a(2k+1) + a(3k+1). - Yifan Xie, Jan 07 2025

Example

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

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

Crossrefs

Cf. A358094, A358096.

Sequence in context: A055800 A060572 A163543 * A180009 A341907 A180010

Adjacent sequences: A358092 A358093 A358094 * A358096 A358097 A358098

Keyword

nonn,easy

Author

Yifan Xie, Nov 01 2022

Status

approved