[seqfan] Re: A165783 Formula for period of shift register stages

[c.zizka at email.cz]

Richard,

the sequence is a(n)=n+digitsum((2^n)-1))/(2*n-1)). Digitsum(z) in base 2.

My comment :
Given a shift register of the type b(n)=b(n-1)+ X if b(n-1) is not divisible Y , else b(n)=b(n-1)/ Y.
 Gcd(b(0),X))=1,Gcd(X,Y)=1.
 Then the length of the period orbit of such a register is L = n + digitsum(b(L)*((Y^n)-1)/X). 
Digitsum(z) in base X. b(L) a point from period orbit.

Sequence A165783 has Y=2 , b(L)=1 , 
and X=1 for a(1), X=3 for a(2), X=5 for a(3), X=7 for a(4) etc. 

Best Regards,

Ctibor

> ------------ Původní zpráva ------------
> Od: Richard Mathar <mathar at strw.leidenuniv.nl>
> Předmět: [seqfan] A165783 Formula for period of shift register stages
> Datum: 23.11.2009 14:00:44
> ----------------------------------------
> 
> Sequence http://research.att.com/~njas/seuqences/A165783
> shows the period length of a shift register which runs
> through the map s(k)=s(k-1)+2n-1 if s(k-1) is odd, else s(k)=s(k-1)/2.
> (This is obscured in the current OEIS description as
> the variable n is used for two different purposes..)
> This can be used to extend the sequence to 
> 
> 2, 3, 6, 4, 9, 15, 18, 5, 12, 27, 8, 15, 30, 27, 42, 6, 15, 17, 54, 16, 30, 21,
>     17, 32, 31, 10, 78, 28, 27, 87, 90, 7, 18, 99, 33, 49, 12, 29, 45, 56, 81,
>     123, 10, 39, 15, 16, 13, 50, 72, 45, 150, 74, 16, 159, 54, 50, 42, 63, 15,
>     33, 165, 26, 150, 8, 21, 195, 26, 53, 102, 207, 69, 85, 42, 62, 222, 20,
>     34, 28, 78, 73, 48, 243, 27, 119, 234, 27, 258, 89, 87, 267
> 
> I cannot get this to match any formula that one might
> derive from correction of parenthesis in the definition line.
> Note that a(8)=5<8, so a(n)=n+something_digitsum with a positive semi-definit
> digit sum is bothering.
> 
> Can anyone with some knowledge on these register sequences
> come up with a correction of the formula in the definition, or
> is this beyond repair?
> I've not received feedback from the author of the sequence.
> 
> Richard
> # this Maple V9 produces what's shown above:
> A165783 := proc(n)
> 	b := [1] ;
> 	while true do
> 		l := nops(b) ;
> 		if type(op(-1,b),'odd') then
> 			nextb := op(-1,b)+2*n-1 ;
> 		else
> 			nextb := op(-1,b)/2 ;
> 		fi;
> 		if member(nextb,b,'w') then
> 			return nops(b)-w+1 ;
> 		else
> 			b := [op(b),nextb] ;
> 		fi;
> 	end do;
> end:
> seq(A165783(n),n=1..90) ;
> 
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/
> 
> 
>