login
A057526
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.
10
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, 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, 4, 4, 4, 5, 4, 4, 3, 4, 3, 4, 4, 5, 4, 4, 3, 4, 3, 4, 4, 5, 4, 4, 4
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
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
Cf. A125184.
One less than A277329.
Sequence in context: A334098 A358371 A263922 * A033265 A096004 A193495
KEYWORD
nonn
AUTHOR
Clark Kimberling, Sep 03 2000
EXTENSIONS
0 prepended by T. D. Noe, Feb 28 2011
STATUS
approved