[seqfan] Re: Is A026477 determined by prime signatures?

[Don Reble]

> [Private e-mail] I'm not sure what "strong induction" means...

    With strong induction, the induction hypothesis refers to all values
    less than some value N. With weak induction, it refers to only N-1.
    The difference is so unimportant, the terms have become disused.


> if two numbers have the same prime signature (multiset of
> prime exponents) then either both or neither are in the sequence ...
> The version with two numbers (A026422) has this property.

    -- Definitions --
    Signature: a finite multiset of positive integers.
    Signature of N: the multiset of exponents in the prime factorization of N.
    Signature-sum: the sum of the values in a signature.
        (For signature {}, the sum is 0.)
    Signature-set: a set of all integers with the same signature.
        (Usually this is an infinite set, but for signature {}, it's {1}.)

    -- Proof --
    Induction hypothesis (N): For any signature with signature-sum
        less than N and signature-set X: all values of X are in
	A026477, or all such values are not in A026477.

    Induction basis (N=1): Only the signature {} has sum less than 1;
        only the number 1 has that signature. That number is in A026477
        or not. (It happens to be in.)

    Induction step: Let X be a signature-set with signature-sum N; let
        X1,X2 be elements of X. Let Z be a permutation of the primes,
        such that p^k divides X1 iff (Z(p))^k divides X2.

        If X1 is not in A026477, then X2 is not in A026477. Proof:

        If X1 is not in A026477, then A026477 has three distinct values
        A1,A2,A3, such that A1*A2*A3 = X1. Let S1,S2,S3 be the
        signatures of those A's. At most one A equals 1, so each
        signature has a signature-sum less than N. By the induction
        hypothesis, A026477 has all values with signatures S1,S2,S3.
        In particular, it has the values B1,B2,B3 obtained by applying
        permutation Z to the prime-factorization-bases of A1,A2,A3.
        B1*B2*B3 = X2, so X2 is not in A026477.

        By symmetry, if X2 is not in A026477, then X1 is not in A026477.

        If follows that A026477 has both or neither of (X1,X2).
        Regarding (X1,X2), (X1,X3), (X1,X4), (X1,X5), ..., pairs of
        values of that signature-set X, one sees that A026477 has all or
        none of X.

    ---

    It is unimportant that there be exactly three A's and three B's.
    An easy variation applies to A026422.

-- 
Don Reble  djr at nk.ca