[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