# [seqfan] A165783 Formula for period of shift register stages

c.zizka at email.cz c.zizka at email.cz
Mon Nov 23 17:11:14 CET 2009

```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/
>
>
>

```