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

[Vladimir Shevelev]

Dear Seq Fans,

Below I present my new comments
in A053446 which generalizes 
the algorithm that I gave in A002326.

Let k, m be any positive numbers not 
divisible by 3. Denote by k<+>m those 
of two numbers k + m, k + 2*m which
is divisible by 3. Finally, for a number t
divisible by 3, let t* = t/3^s be integer
not divisible by 3, i.e., s is 3-adic order 
of t. Let u = u(n) be the n-th number
which is not divisible by 3. Consider
the following algorithm of the calculating
a(n), similar to the algorithm in A002326.
We compute successively r_1=(1 <+> u)*,
r_2 = (r_1 <+> u)*,..., r_h = (r_(h-1) <+> u)*
and we finish as soon as r_h=1. Then a(n) = 
s(1<+>u) + s(r_1<+>u) + ... +  s(r_(h-1)<+>u). 
Example. 7 is the fifth number not divisible by 3. 
According to the algorithm in comment in a form 
of "finite continued fraction" we have

1+14
------ +7
3
---------- + 14
3
----------------- + 7
3^2
---------------------- =1
3^2
Summing the exponents of 3 in denominators, 
we obtain a(5) = 1 + 1 + 2 + 2 = 6.
Note that by a similar algorithm one can compute
arbitrary multiplicative order of a mod b, where gcd(a, b) = 1.

Best regards,
Vladimir
________________________________________
From: SeqFan [seqfan-bounces at list.seqfan.eu] on behalf of Vladimir Shevelev [shevelev at exchange.bgu.ac.il]
Sent: 06 October 2017 00:06
To: Sequence Fanatics Discussion list
Subject: [seqfan] Re: An algorithm for multiplicative order of 2 mod 2n+1 (A002326)

Dear Richard,
thanks, but I did not find
any so close, at least,
direct connection...

In addition, see also the comment
in a submitted by me and Antti
new sequence A292720.
There it is proved that the
number of steps in the algorithm
for the calculation of A002326(n)
required to reach  (the first) 1
does not exceed n. Sometimes
n is reached. For example, for
n=9, 2*n+1=19, we have exactly
9 steps with the advent of a
permutation of all odd residues
(which are partial fractions)
 <= 2*n-1= 17 modulo 19:
5,3,11,15,17,9,7,13,1.

Best regards,
Vladimir
________________________________________
From: SeqFan [seqfan-bounces at list.seqfan.eu] on behalf of Richard J. Mathar [mathar at mpia-hd.mpg.de]
Sent: 04 October 2017 14:19
To: seqfan at seqfan.eu
Subject: [seqfan] Re: An algorithm for multiplicative order of 2 mod 2n+1 (A002326)

The algorithm in http://list.seqfan.eu/pipermail/seqfan/2017-October/017983.html
seems to be closely related to the association between terminating binary
expansions and the multiplicative orders (xi, Haupt-exponent) in Cunningham's
article "on binal fractions" of 1908. The article is cited in A002326:
http://dx.doi.org/10.2307/3602595 .

Richard

--
Seqfan Mailing list - http://list.seqfan.eu/

--
Seqfan Mailing list - http://list.seqfan.eu/