OFFSET
1,4
COMMENTS
Also the number of zeros in the symmetric signed digit expansion of n with q=2 (i.e. the representation of n in the (-1,0,1)_2 number system). - Ralf Stephan, Jun 30 2003
Also the degree of the Stern polynomial B[n,t]. The Stern polynomials B[n,t] are defined by B[0,t]=0, B[1,t]=1, B[2n,t]=tB[n,t], B[2n+1,t]=B[n+1,t]+B[n,t] for n>=1 (see S. Klavzar et al. and A125184). - Emeric Deutsch, Dec 04 2006
In this sequence, n occurs exactly 3^n times. - T. D. Noe, Mar 01 2011
LINKS
T. D. Noe, Table of n, a(n) for n = 1..10000
C. Heuberger and H. Prodinger, On minimal expansions in redundant number systems: Algorithms and quantitative analysis, Computing 66(2001), 377-393.
S. Klavzar, U. Milutinovic and C. Petr, Stern polynomials, Adv. Appl. Math. 39 (2007) 86-95.
G. Manku and J. Sawada, A loopless Gray code for minimal signed-binary representations, 13th Annual European Symposium on Algorithms (ESA), LNCS 3669 (2005), 438-447.
Maciej Ulas and Oliwia Ulas, On certain arithmetic properties of Stern polynomials, arXiv:1102.5109 [math.CO], 2011. See p. 10.
FORMULA
a(1)=0, a(2n)=a(n)+1, a(4n-1)=a(n)+1, a(4n+1)=a(n)+1 for n>=1 (Klavzar et al. Proposition 12). - Emeric Deutsch, Dec 04 2006
a(1)=0, a(2n)=a(n)+1, a(4n+1)=a(2n), a(4n+3)=a(2n+2) for n>=1 (Klavzar et al. Corollary 13). - Emeric Deutsch, Dec 04 2006
a(n) = A277329(n)-1. - Antti Karttunen, Oct 27 2016
EXAMPLE
a(34)=4, which counts these reductions: 34->17->4->2->1.
MAPLE
a:=proc(n) if n=1 then 0 elif n mod 2=0 then a(n/2)+1 elif n mod 4=1 then a((n-1)/2) else a((n+1)/2) fi end: seq(a(n), n=2..91); # Emeric Deutsch, Dec 04 2006
MATHEMATICA
a[n_] := a[n] = Which[n == 1, 0, Mod[n, 2] == 0, a[n/2] + 1, Mod[n, 4] == 1, a[(n-1)/2], True, a[(n+1)/2]];
Array[a, 100] (* Jean-François Alcover, Apr 20 2020 *)
PROG
(PARI)
ep(r, n)=local(t=n/2^(r+2)); floor(t+5/6)-floor(t+4/6)-floor(t+2/6)+floor(t+1/6);
a(n)=sum(r=0, log(3*n)\log(2)-1, !ep(r, n)) ;
(Scheme, with memoization-macro definec)
(definec (A057526 n) (cond ((= 1 n) 0) ((even? n) (+ 1 (A057526 (/ n 2)))) ((= 3 (modulo n 4)) (+ 1 (A057526 (/ (+ 1 n) 4)))) (else (+ 1 (A057526 (/ (+ -1 n) 4))))))
;; Antti Karttunen, Oct 27 2016 after the first recurrence of Klavzar et al. as given by Emeric Deutsch in the Formula section.
CROSSREFS
KEYWORD
nonn
AUTHOR
Clark Kimberling, Sep 03 2000
EXTENSIONS
0 prepended by T. D. Noe, Feb 28 2011
STATUS
approved