OFFSET
1,3
COMMENTS
We may start either with multiplication or summation. After summation the next step will be multiplication or vice versa.
From Thomas Scheuerle, Oct 30 2022: (Start)
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.
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)
LINKS
Yifan Xie, Table of n, a(n) for n = 1..10000
Thomas Scheuerle, 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.
FORMULA
From Thomas Scheuerle, Oct 30 2022: (Start)
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.
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)
EXAMPLE
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.
MAPLE
b:= proc(n, t) option remember; `if`(n=1, 1, add(`if`(t=1 and i<n,
b(n-i, 1-t), `if`(t=0 and irem(n, i)=0, b(n/i, 1-t), 0)), i=2..3))
end:
a:= n-> `if`(n=1, 1, add(b(n, i), i=0..1)):
seq(a(n), n=1..80); # Alois P. Heinz, Jan 12 2024
MATHEMATICA
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 *)
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)+f(i, 1)<<", "; cout<<f(n, 0)+f(n, 1); return 0; }
(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
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Yifan Xie and Thomas Scheuerle, Oct 29 2022
STATUS
approved