login
This site is supported by donations to The OEIS Foundation.

 

Logo


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.

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 July 23 15:58 EDT 2019. Contains 325258 sequences. (Running on oeis4.)