[seqfan] Re: Mapping problem
M. F. Hasler
seqfan at hasler.fr
Thu Nov 10 14:12:23 CET 2016
Don's and Robert's formulae coïncide (using the usual formula for phi(p^e),
but the sequence seems not yet in OEIS, so I submitted it tentativley (with
due credits) as https://oeis.org/draft/A277847
(Editors, feel free to recycle if already submitted otherwise.)
- M.
On Wed, Nov 9, 2016 at 8:03 AM, Don Reble <djr at nk.ca> wrote:
> 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?
>>
>
> It looks like f(n) is multiplicative.
> f(2^n) = 2,
> f(p^n) = 1 + (p^(n-1) * oddpart(p-1))
> (p is an odd prime, oddpart(x) is the largest odd factor of x)
>
> That makes sense, when you consider the multiplicative (modulo n)
> group of numbers coprime to n.
> If a cyclic subgroup has odd order, it is closed under duplication;
> but if it has even order, it is not closed. (The generators aren't
> duplicates of anything.)
> That "1 +" in f(p^n) accounts for the 0 element of Z(n), which is
> not in any multiplicative group.
>
> Hmm... It could be the limit, as something goes to infinity,
> of A000224, A052273, A085311, ...
>
> --
> Don Reble djr at nk.ca
More information about the SeqFan
mailing list