cp's OEIS Frontend

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

%I A358095 #43 Jan 19 2025 23:08:24
%S A358095 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,
%T A358095 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,
%U A358095 7,0,2,5,3,8,8,2,5,9,6,10
%N A358095 a(n) is the number of ways n can be reached in the algorithm explained in A358094 if the last operation is summation.
%C A358095 From _Yifan Xie_, Jan 07 2025: (Start)
%C A358095 The following identities can be proved by induction (k, t are nonnegative integers):
%C A358095 a(n) = 0 iff n = 2 or n = 9*2^k - 2.
%C A358095 a(n) = 1 iff n = 1, 3, 6, 8, 9 or n = 21*2^k - 2.
%C A358095 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}.
%C A358095 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.
%C A358095 If n > 60, a(n) = 4 iff n = 114*2^k - 2. (End)
%H A358095 Yifan Xie, <a href="/A358095/b358095.txt">Table of n, a(n) for n = 1..10000</a>
%F A358095 a(n) = A358096(n-2) + A358096(n-3) for n > 3.
%F A358095 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
%e A358095 There are 3 ways to reach 11: (1*2+2)*2+3=11, (1+3)*2+3=11 and (1+2)*3+2=11.
%o A358095 (C++) #include <iostream>
%o A358095 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; }
%Y A358095 Cf. A358094, A358096.
%K A358095 nonn,easy
%O A358095 1,4
%A A358095 _Yifan Xie_, Nov 01 2022