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

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, 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, 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

Offset: 0

Author

Henry Bottomley, Jun 06 2001

Keywords

• nonn

Comments

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

Examples

			a(20) = 6 since 20 = (0 + 1 + 1)*3*3 + 1 + 1 = ((0 + 1 + 1)*3 + 1)*3 - 1.
		

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 0..10000
• Index to sequences related to the complexity of n

Crossrefs

Cf. A056792.

Programs

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

Formula

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.