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

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

Links

Charles R Greathouse IV, Table of n, a(n) for n = 0..10000

Index to sequences related to the complexity of n

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.

Example

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

Prog

(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

Crossrefs

Cf. A056792.

Sequence in context: A165359 A002308 A056796 * A081742 A127432 A199408

Adjacent sequences: A061292 A061293 A061294 * A061296 A061297 A061298

Keyword

nonn

Author

Henry Bottomley, Jun 06 2001

Status

approved