[seqfan] Re: Mapping problem

[israel at math.ubc.ca]

The multiplicative group mod p^e (for prime p) is cyclic of order phi(p^e). 
If the 2-adic order of this is d, the terms that are 2^k'th powers for all 
of the form g^(k*2^d) where g is a generator. Including 0, we should get 
f(p^e) = phi(p^e)/2^d +1. Since the function is multiplicative, the 
following Maple function produces this sequence:

f:= proc(n) local F;
   F:= ifactors(n)[2];
   convert(map(proc(t) local p; p:=numtheory:-phi(t[1]^t[2]); 
1+p/2^padic:-ordp(p,2) end proc,F),`*`) end proc:

For n=1..100, I get

1, 2, 2, 2, 2, 4, 4, 2, 4, 4, 6, 4, 4, 8, 4, 2, 2, 8, 10, 4, 8, 12, 12, 4, 
6, 8, 10, 8, 8, 8, 16, 2, 12, 4, 8, 8, 10, 20, 8, 4, 6, 16, 22, 12, 8, 24, 
24, 4, 22, 12, 4, 8, 14, 20, 12, 8, 20, 16, 30, 8, 16, 32, 16, 2, 8, 24, 
34, 4, 24, 16, 36, 8, 10, 20, 12, 20, 24, 16, 40, 4, 28, 12, 42, 16, 4, 44, 
16, 12, 12, 16, 16, 24, 32, 48, 20, 4, 4, 44, 24, 12

Cheers,
Robert

On Nov 9 2016, Joerg Arndt wrote:

>* David Wilson <davidwwilson at comcast.net> [Nov 09. 2016 10:32]:
>> Let S(n) be the largest subset of Z(n) fixed by the mapping n -> n^2, and
>> let f(n) = |Z(n)|.
>> For example, S(25) = {0, 1, 6, 11, 16, 21} is the largest set of residues
>> modulo 25 fixed by the mapping n -> n^2, so f(25) = |S(25)| = 6.
>> Can you find a formula for f(n) in terms of n?
>>
>
>I speculate that all fourth powers give the set.
>Here I only look at the multiplicative group (units mod n).
>
>The following is a quick shot:
>(PARI) a(n)=my(p=eulerphi(n)); sumdiv(p,d,if((p/d)%4!=0,0,eulerphi(d)))
>
>vector(25,n,a(n))
>gives
>[0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 3, 0, 2, 2, 4, 0, 0, 2, 3, 0, 0, 2, 5]
>The final 5 for all elements you gave, except 0.
>
>The singly generated multiplicative groups (those having a primitive root)
>are isomorphic to additive groups of the same cardinality.
>Squaring in the mult. group maps to doubling in the additive group.
>From the(se) elements (of the form 2*? mod cardinality) we only
>take those that are mapped to from said set via doubling.
>So we are left with all elements 4*? mod cardinality.
>
>That should give the same result.
>
>Example: (mult. group mod 13 isom. to add. group mod 12)
>There are 3 elements that are a multiple of 4:
>m=12; vector(m,j, (4*j)%m )
>[4, 8, 0, 4, 8, 0, 4, 8, 0, 4, 8, 0]
>This checks the value for 13 above.
>
>But for 11 (add. gr. 10) I get 5 elements:
>? m=10; vector(m,j, (4*j)%m )
>[4, 8, 2, 6, 0, 4, 8, 2, 6, 0]
>That does not match the 0 above...
>
>So shurely shome mishtake shomwhere.
>
>Best regards,   jj
>
>
>> 
>> --
>> Seqfan Mailing list - http://list.seqfan.eu/
>
>--
>Seqfan Mailing list - http://list.seqfan.eu/
>
>