[seqfan] Re: Mapping problem

Don Reble djr at nk.ca
Wed Nov 9 13:03:15 CET 2016

> 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