[seqfan] An algorithm for multiplicative order of 2 mod 2n+1 (A002326)

Vladimir Shevelev shevelev at bgu.ac.il
Tue Oct 3 18:53:19 CEST 2017


Dear Seq Fans,

I would like to present an algorithm for A002326(n)
in a form of "finite continued fraction". Example: let
n=8, 2n+1=17. Then consider the fraction =1:

1+17
------- + 17
2
------------- + 17
2
------------------- + 17
2
-------------------------- = 1
32

Here the denominators are A006519 from the numerators:
A006519(1+17)=2, A006519(9+17)=2, A006519(13+17)=2,
A006519(15+17)=32. Summing the exponents of 2, we have
the required result 1+1+1+5=8=A002326(8).
Indeed, (((32*1-17)*2-17)*2-17)*2-17=1
and so 2^(5+1+1+1)-1 is the smallest number of the form 2^m-1
which is divisible by 17.
This algorithm was described in some another form in A179680.

Best regards,
Vladimir


 



More information about the SeqFan mailing list