cp's OEIS Frontend

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.

%I A358094 #72 Jan 18 2025 21:50:52
%S A358094 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,
%T A358094 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,
%U A358094 5,7,9,3,2,13,3,10,11,8,5,19,6,11
%N 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.
%C A358094 We may start either with multiplication or summation. After summation the next step will be multiplication or vice versa.
%C A358094 From _Thomas Scheuerle_, Oct 30 2022: (Start)
%C A358094 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.
%C A358094 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)
%C A358094 Proof of the conjecture: We use the identities in A358095. For n > 145, if a(n) <= 2, A358095(n) <= 2. Therefore, n must be a*3*2^k - 2, where a is in the set {3, 7, 26, 30, 32, 34, 40, 49} and k is a positive integer. However, A358096(a*3*2^k - 2) = A358095(a*3*2^(k-1) - 1) >= 3, a contradiction. Hence all numbers greater than 145 can be reached in at least 3 different ways. If a(n) = 3, the only possibilities are that A358095(n) = 0 and A358096(n) = 3 or A358095(n) = 3 and A358096(n) = 0. For the first one, n must be 9*2^k - 2, so A358096(n) = A358095(9*2^(k-1) - 1) >= 4. For the second one, if n is in the form a*3*2^k - 2, A358096(n) = A358095(a*3*2^(k-1) - 1) >= 4; if n = 108*2^k - 3, A358096(n) = A358095(36*2^k - 1) >= 4; if n is in the form 108*2^k - 5, A358096(n) = 0. Hence a(n) = 3 iff n = 27*2^k - 5 for n > 145. - _Yifan Xie_, Jan 07 2025
%H A358094 Yifan Xie, <a href="/A358094/b358094.txt">Table of n, a(n) for n = 1..10000</a>
%H A358094 Thomas Scheuerle, <a href="/A358094/a358094.png">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.</a>
%H A358094 Thomas Scheuerle, <a href="/A358094/a358094_1.png">The number of ways n may be reached if we allow multiplication in all steps only by the same number. For n = 1..500.</a>
%H A358094 Thomas Scheuerle, <a href="/A358094/a358094_2.png">All possible trajectories for the first ten steps plotted in logarithmic scale.</a>
%F A358094 a(n) = A358095(n) + A358096(n) for n > 1.
%F A358094 From _Thomas Scheuerle_, Oct 30 2022: (Start)
%F A358094 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.
%F A358094 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)
%e A358094 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.
%p A358094 b:= proc(n, t) option remember; `if`(n=1, 1, add(`if`(t=1 and i<n,
%p A358094       b(n-i, 1-t), `if`(t=0 and irem(n, i)=0, b(n/i, 1-t), 0)), i=2..3))
%p A358094     end:
%p A358094 a:= n-> `if`(n=1, 1, add(b(n, i), i=0..1)):
%p A358094 seq(a(n), n=1..80);  # _Alois P. Heinz_, Jan 12 2024
%t A358094 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 *)
%o A358094 (C++) #include <iostream>
%o A358094 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); } }
%o A358094 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; }
%o A358094 (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
%Y A358094 Cf. A005836, A304387, A358095, A358096.
%K A358094 nonn,easy
%O A358094 1,3
%A A358094 _Yifan Xie_ and _Thomas Scheuerle_, Oct 29 2022