cp's OEIS Frontend

A061295 Minimal number of steps to get from 0 to n by (a) adding 1 or (b) subtracting 1 or (c) multiplying by 3.

%I A061295 #9 Jan 03 2017 08:39:52
%S A061295 0,1,2,2,3,4,3,4,4,3,4,5,4,5,6,5,6,5,4,5,6,5,6,6,5,6,5,4,5,6,5,6,7,6,
%T A061295 7,6,5,6,7,6,7,8,7,8,7,6,7,8,7,8,7,6,7,6,5,6,7,6,7,8,7,8,7,6,7,8,7,8,
%U A061295 8,7,8,7,6,7,8,7,8,7,6,7,6,5,6,7,6,7,8,7,8,7,6,7,8,7,8,9,8,9,8,7,8,9,8,9,8
%N A061295 Minimal number of steps to get from 0 to n by (a) adding 1 or (b) subtracting 1 or (c) multiplying by 3.
%C A061295 Records are a(0) = 0, a(1) = 1, a(2) = 2, a(4) = 3, a(5) = 4, a(11) = 5, a(14) = 6, a(32) = 7, a(41) = 8, a(95) = 9, a(122) = 10, a(284) = 11, a(365) = 12, a(851) = 13, a(1094) = 14, a(2552) = 15, a(3281) = 16, a(7655) = 17, a(9842) = 18, a(22964) = 19, .... - _Charles R Greathouse IV_, Jan 03 2017
%H A061295 Charles R Greathouse IV, <a href="/A061295/b061295.txt">Table of n, a(n) for n = 0..10000</a>
%H A061295 <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%F A061295 a(3n)=a(n)+1; a(3n+1)=a(n)+2; a(3n+2)=a(n+1)+2; a(0)=0, a(1)=1, a(2)=2.
%e A061295 a(20) = 6 since 20 = (0 + 1 + 1)*3*3 + 1 + 1 = ((0 + 1 + 1)*3 + 1)*3 - 1.
%o A061295 (PARI) steps(n,mx=3^(n-1))=my(v,s=vector(mx),u=[0],t); for(i=1,n, v=List(); for(j=1,#u, t=u[j]; if(!setsearch(u,3*t), if(t>0 && 3*t<=mx && s[3*t]==0, s[3*t]=i); listput(v,3*t)); if(!setsearch(u,t-1), if(t>1 && t-1<=mx && s[t-1]==0, s[t-1]=i); listput(v,t-1)); if(!setsearch(u,t+1), if(t>=0 && t+1<=mx && s[t+1]==0, s[t+1]=i); listput(v,t+1))); u=select(k->k<1 || k>mx || s[k]==i, Set(v))); for(i=1,#s, if(s[i]==0, return(concat([0], s[1..i-1])))); concat([0], s); \\ _Charles R Greathouse IV_, Jan 03 2017
%Y A061295 Cf. A056792.
%K A061295 nonn
%O A061295 0,3
%A A061295 _Henry Bottomley_, Jun 06 2001