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

[Bob Selcoe]

Hi Don,

Thanks for the explanation of strong induction.

My proof (or perhaps "explanation" is a better word for it) is based on the 
idea that since all primes appear in the sequence, it's straightforward to 
show which prime powers appear and which do not; and by example, demonstrate 
that the constraints imposed by the appearance of prime and prime-power 
terms lead to the appearance (or not) of all terms with the same signatures.

It seems like your proof is somewhat different, but I'm having a little 
trouble following all of it (owing to my lack of familiarity with some of 
the language used rather than the presentation, I'm sure).  But as I 
understand it...

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

... means, for example, that say signature S = {3,1}, so X = {24, 40, 54, 
56, 88...}, so let X1=54 = 3^3*2 and X2=88 = 2^3*11.   I'm not sure how Z 
applies here.  Are you saying p^k and (Z(q))^k where p and q are prime?? 
Can you give an example of a specific permutation?

Anyway, I would suggest also including your proof on A026477, if you're so 
inclined.

Thanks,
Bob S

--------------------------------------------------
From: "Don Reble" <djr at nk.ca>
Sent: Saturday, August 27, 2016 1:02 AM
To: "Sequence Fanatics Discussion list" <seqfan at list.seqfan.eu>
Subject: [seqfan] Re: Is A026477 determined by prime signatures?

>> [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
>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>