login
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.
4

%I #65 Feb 20 2024 13:23:37

%S 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 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 5,7,9,3,2,13,3,10,11,8,5,19,6,11

%N 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 We may start either with multiplication or summation. After summation the next step will be multiplication or vice versa.

%C From _Thomas Scheuerle_, Oct 30 2022: (Start)

%C 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 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)

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

%H 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 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 Thomas Scheuerle, <a href="/A358094/a358094_2.png">All possible trajectories for the first ten steps plotted in logarithmic scale.</a>

%F a(n) = A358095(n) + A358096(n) for n > 1.

%F From _Thomas Scheuerle_, Oct 30 2022: (Start)

%F 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 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 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 b:= proc(n, t) option remember; `if`(n=1, 1, add(`if`(t=1 and i<n,

%p b(n-i, 1-t), `if`(t=0 and irem(n, i)=0, b(n/i, 1-t), 0)), i=2..3))

%p end:

%p a:= n-> `if`(n=1, 1, add(b(n, i), i=0..1)):

%p seq(a(n), n=1..80); # _Alois P. Heinz_, Jan 12 2024

%t 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 (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); } }

%o 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 (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 Cf. A005836, A304387, A358095, A358096.

%K nonn,easy

%O 1,3

%A _Yifan Xie_ and _Thomas Scheuerle_, Oct 29 2022