|
%I #44 Apr 20 2020 09:53:20
%S 0,1,1,2,1,2,2,3,2,2,2,3,2,3,3,4,3,3,2,3,2,3,3,4,3,3,3,4,3,4,4,5,4,4,
%T 3,4,3,3,3,4,3,3,3,4,3,4,4,5,4,4,3,4,3,4,4,5,4,4,4,5,4,5,5,6,5,5,4,5,
%U 4,4,4,5,4,4,3,4,3,4,4,5,4,4,3,4,3,4,4,5,4,4,4
%N Number of applications of f to reduce n to 1, where f(k) is the integer among k/2,(k-1)/4, (k+1)/4.
%C 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
%C 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
%C In this sequence, n occurs exactly 3^n times. - _T. D. Noe_, Mar 01 2011
%H T. D. Noe, <a href="/A057526/b057526.txt">Table of n, a(n) for n = 1..10000</a>
%H C. Heuberger and H. Prodinger, <a href="http://dx.doi.org/10.1007/s006070170021">On minimal expansions in redundant number systems: Algorithms and quantitative analysis</a>, Computing 66(2001), 377-393.
%H S. Klavzar, U. Milutinovic and C. Petr, <a href="http://dx.doi.org/10.1016/j.aam.2006.01.003">Stern polynomials</a>, Adv. Appl. Math. 39 (2007) 86-95.
%H G. Manku and J. Sawada, <a href="http://www.cis.uoguelph.ca/~sawada/papers/esa-loopless.pdf">A loopless Gray code for minimal signed-binary representations</a>, 13th Annual European Symposium on Algorithms (ESA), LNCS 3669 (2005), 438-447.
%H Maciej Ulas and Oliwia Ulas, <a href="http://arxiv.org/abs/1102.5109">On certain arithmetic properties of Stern polynomials</a>, arXiv:1102.5109 [math.CO], 2011. See p. 10.
%F 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
%F 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
%F a(n) = A277329(n)-1. - _Antti Karttunen_, Oct 27 2016
%e a(34)=4, which counts these reductions: 34->17->4->2->1.
%p 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
%t 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]];
%t Array[a, 100] (* _Jean-François Alcover_, Apr 20 2020 *)
%o (PARI)
%o 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);
%o a(n)=sum(r=0, log(3*n)\log(2)-1, !ep(r, n)) ;
%o (Scheme, with memoization-macro definec)
%o (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))))))
%o ;; _Antti Karttunen_, Oct 27 2016 after the first recurrence of Klavzar et al. as given by _Emeric Deutsch_ in the Formula section.
%Y Cf. A125184.
%Y One less than A277329.
%K nonn
%O 1,4
%A _Clark Kimberling_, Sep 03 2000
%E 0 prepended by _T. D. Noe_, Feb 28 2011
|
