[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