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

Don Reble djr at nk.ca
Mon Jun 6 09:40:37 CEST 2016

> 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.

    - 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

        S5 is a subset of S1.

    --- S2 ---

    Using Knuth's theorem A, [TAOCP volume 2, second edition,
    section, 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

More information about the SeqFan mailing list