login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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

REFERENCES

G. Manku, J. Sawada, A loopless Gray code for minimal signed-binary representations, 13th Annual European Symposium on Algorithms (ESA), LNCS 3669 (2005), 438-447.

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.

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

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: A064122 A323424 A263922 * A033265 A096004 A193495

Adjacent sequences:  A057523 A057524 A057525 * A057527 A057528 A057529

KEYWORD

nonn

AUTHOR

Clark Kimberling, Sep 03 2000

EXTENSIONS

0 prepended by T. D. Noe, Feb 28 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 23 07:07 EST 2020. Contains 331168 sequences. (Running on oeis4.)