[seqfan] Re: Mapping problem

[David Wilson]

Let f_k(n) be the number of k-th powers mod n.
Then I believe a(n) = lim k->inf f_(2^k)(n).

> -----Original Message-----
> From: SeqFan [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of
> israel at math.ubc.ca
> Sent: Wednesday, November 09, 2016 5:34 PM
> To: Sequence Fanatics Discussion list
> Subject: [seqfan] Re: Mapping problem
> 
> 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