[seqfan] Re: Relationship between A002093 & A036913

[Christian G.Bower]

Joe Crump wrote:

> I came across an interesting sequence, whose increasing
> values are the same as A036913, and the index into the sequence
> for each new value is A002093 (almost). Perhaps some of you
> can provide an analysis.

> Here is the rule I followed to generate the sequence...

> f(n) = Maximum m where we can find (x,y), 0<x<m, 0<y<m, satisfying 0 < xy
> mod m <= n

> Running a quick program generated the solutions...
> ======================================================
>  m =   6, n= 1
>  m =  12, n= 2
>  m =  18, n= 3
...
> All of the m's match A036913, and the first n's where
> a new m occurs matches the first 12 entries of A002093.
> So it would appear at first f( A002093(n) ) = A036913(n+1).
> However, after 12 entries A002093 seems to lose focus.

Joe's function (as clarified in a later post) can be described as follows:

Let n be a positive integer.
Let k be an integer 0<=k<n.
Let G(n,k) be the set of all unordered pairs {a,b} a*b==k (mod n).
Let g(n,k) = |G(n,k)| the number of sets in G(n,k).
Let h(n) = min {g(n,k) | 0<=k<n} the least value of g(n,k).

Joe's m=f(n) is the greatest m such that h(m) <= n.
You might call it the indices of the record low values of h.

Anyway I evaluated several values of h and got:
1 1 1 1 2 1 3 2 3 2 5 2 6 3 4 4 8 3 9 4 6 5 11 4 10 6...

I looked them up in the EIS and got:

%I A023022
%S A023022 
1,1,1,2,1,3,2,3,2,5,2,6,3,4,4,8,3,9,4,6,5,11,4,10,6,9,6,14,4,15,8,10,8,
%T A023022 
12,6,18,9,12,8,20,6,21,10,12,11,23,8,21,10,16,12,26,9,20,12,18,14,29,8,
%U A023022 
30,15,18,16,24,10,33,16,22,12,35,12,36,18,20,18,30,12,39,16,27,20,41,12
%N A023022 Partitions of n into 2 ordered relatively prime parts.
%O A023022 2,4
%K A023022 nonn
%A A023022 wilson at ctron.com
%F A023022 phi(n)/2 for n >= 3.

Suggesting that h(n) is just phi(n)/2 when n>=3.
This would explain the connection to A036913 which is just the indices of
record low values of phi(n).

(BTW, Dave Wilson calls ordered what I would call unordered.)

Theorem: h(n)=phi(n)/2 for n>=3.

Lemma: g(n,k) >= phi(n)/2 for n>1 and 0<=k<n.

If (a,n)=1 (a is relatively prime to n) then there is a b such that
a*b==k (mod n). In fact, since a has period n, there is a unique
b: 0<=b<n such that a*b==k (mod n).

So let a_1, a_2, ... , a_phi(n) be the numbers < and relatively prime to n.

We have products a_1*b_1=k, a_2*b_2=k, ... , a_phi(n)*b_phi(n)=k (mod n).

phi(n) products.

However, it may be that b_1 is one of the a's, b_2, etc.

So each product may appear at most twice on the list.

Thus we have at least phi(n)/2 products.

The lemma is shown.
This also shows that h(n)>=phi(n)/2.

Now all that remains is to show there is a k: 0<=k<n such that
g(n,k)=phi(n)/2.

It is easy to show that if (k,n)=1 and if a*b==k (mod n) that
(a,n)=(b,n)=1. (If c|a then c|a*b.)

Thus if (k,n)=1 then the only products a*b==k (mod n) are:
a_1*b_1, a_2*b_2, ... , a_phi(n)*b_phi(n) where a_i is the ith
positive integer <n: (a_i,n)=1.
Since the b's are also relatively prime to n each b_i=a_j for some j.
If it is always the case that i != j (not equal) then the number
of products will be exactly phi(n)/2.

Thus if we can find a k such that (k,n)=1 and there is no a: a^2==k (mod n)
Then g(n,k)=phi(n)/2 and h(n)=phi(n)/2.

If (k,n)=1 and a^2==k (mod n) then (a,n)=1. Thus the relatively prime
squares are just a_1^2, a_2^2, ... , a_phi(n)^2. If there are any repeats
on the list, then there is at least one relatively prime nonsquare.
If n>=3 there will be a repeat because a^2==(n-a)^2 (mod n) and for
n>=3 it is never the case that a==-a (mod n) if (a,n)=1.

Thus there is at least one k: (k,n)=1 and there is no a: a^2==k (mod n)
and the theorem is proved.

Christian

P.S.
I don't know what connection (if any) there is to A002093.


____________________________________________________________________
Get free e-mail and a permanent address at http://www.netaddress.com/?N=1