[seqfan] Re: A046790, A046791 obscure, need clarification

[Don Reble]

> A046790 and A046791 from 1999 could use some clarification.

> %K A046790 nonn,uned,obsc

    A046790 may have begun in obscurity, but now we have three helpful
    definitions in the comments,

D1: Numbers n such that A008475(n) is different from A001414(n).
    - Benoit Cloitre, Jan 11 2003
D2: moduli n for which there exist affine maps f:x->a*x + b modulo n,
    with a>1, such that f has order n in the affine group.
    - Emmanuel Amiot, Jul 28 2007
D3: Numbers n such that A005361(n)/A003557(n) < 1. - Anthony Browne,
    Jun 03 2016

    a proposed definition from njas,

D4: numbers i such that there is a smaller positive number j such that
    (i+j)/2 and sqrt(i*j) are integers  (I inserted "positive".)

    and if I may join the chorus du jour,

D5: positive numbers divisible by 8 or by the square of an odd prime.

    Let S1,...,S5 be the integer sets defined by D1,...,D5.


    Definitions:
    - component of n: for any prime p, the highest power of p which divides n.
    - big component: any composite component, except 4

    The point of a big component p^k, is that p^k > p*k, while for other
    components, p^1 = p*1, and 2^2 = 2*2. Also, D5 can be written,
    "Positive numbers with a big component."


    --- S1 ---

    A008475 maps n = product(p^k) to a(n) = sum(p^k).
    A001414 sums the prime factors of n (including repetitions);
            a(n) = sum(p*k).

    If sum(p^k) isn't sum(p*k), then for some component, p^k isn't p*k,
    so p^k is a big component.

        S1 is a subset of S5.

    If n has a big component, that component makes A008475 bigger than
    A001414.

        S5 is a subset of S1.


    --- S2 ---

    Using Knuth's theorem A, [TAOCP volume 2, second edition,
    section 3.2.1.2, p16], we see that there is such an affine map
    f:x->a*x + b modulo n, iff
        - each prime dividing n also divides a-1, and
        - if 4 divides n, then 4 also divides a-1.
        (Also, b must be coprime to n; b=1 suffices.)
    We may take a to be within [2,n-1].
    (a=1 works, but it's forbidden: "with a>1".)
    If n is square-free, then n divides a-1: all a-values in [2,n-1]
    fail, and there is no such map.
    So n is not square-free. If the only composite component of n is 4,
    then again n divides a-1.
    Therefore n is divisible by 8 or by the square of an odd prime.

        S2 is a subset of S5.

    If n is divisible by 8, let d be the highest odd factor of n,
    let a=4d+1. 1 < a=4d+1 < 8d <= n.
    If n is divisible by odd p^2, let a=(n/p)+1.
    1 <= n/(p^2) < a=(n/p)+1 < n.
    Either way, Knuth's theorem shows that there is a suitable affine
    map using that a-value.

        S5 is a subset of S2.


    --- S3 ---

    Dr. Brown could simply write A005361(n) < A003557(n), since both
    sequences are positive.
    A005361 has the product of the exponents in n = product(p^k).
    A003557 has n divided by its largest square-free divisor.

    If n is square-free, than A003557(n) = 1 = A005361(n).
    If n is 4 times an odd square-free number, then
    A003557(n) = 2 = A005361(n).
    So if A003557(n) > A005361(n), n must be divisible by 8 or by the
    square of an odd prime.

        S3 is a subset of S5.

    First, show that A005361(n) <= A003557(n) always.
    Let n = product(p^k); then A005361(n) = product(k),
    A003557(n) = product(p^(k-1)).
    If p^k is a big component, then p^k > p*k, and p^(k-1) > k.
    If p^k is not big, then p^k = p*k, and p^(k-1) = k.
    Each factor of A003557 is >= the corresponding factor of A005361,
    so the product is >=.

    Let n be a element of S5; let c=p^k be a big component of n.
    Then p*A005361(n) = p*k*A005361(n/c) <= p*k*A003557(n/c)
        < (p^k)*A003557(n/c) = p*(c/p)*A003557(n/c) = p*A003557(n).
    Therefore A005361(n) < A003557(n) and n is in S3.

        S5 is a subset of S3.


    --- S4 ---

    If i is divisible by 8, then let j=i/4; if i is divisible by an odd p^2,
    let j=i/(p^2). Then 0<j<i, and (i+j)/2 and sqrt(ij) are integers.

        S5 is a subset of S4.

    Let i, an element of S4, equal (a^2)*b, where b is square-free.
    If (i*j) is a square, then j=b*(c^2), for some value of c. D4 says
    0<j<i; therefore 0<c<a and 1<a.
    If a=2, then c=1, and (i+j)/2 = 5b/2: that is an integer,
    so b is even, and 8 divides i.
    If a is a higher power of two, then 8 divides i.
    Otherwise a is divisible by an odd prime p, and p^2 divides i.

        S4 is a subset of S5.


    -----

    Phew. If that's all right, then we have five good definitions of
    A046790. I like D2, because of the connection with LCM pseudorandom
    generators. For ease of computation, D5 is pretty good. (Yes, the
    %STU values agree.) But D4 seems closest to the author's intent.

    Maybe the sequence isn't "core", but it's surely "nice".
    Thanks, David.

-- 
Don Reble  djr at nk.ca