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

Graeme McRae graememcrae at gmail.com
Sat Aug 27 01:58:58 CEST 2016

```Yeah, I agree, Bob S., it's no easy task, for sure. The heart of my idea,
(or the germ of my idea, to be honest), is a function ProductSignature(a,
b, c), which takes as input three prime signatures, and returns as output a
list of all the possible prime signatures that can result from multiplying
three distinct integers with these prime signatures.

So, for example, if the input is (), (1,1), (1,1), then the output should
be (2,1,1), (1,1,1,1)

Notice that (2,2) isn't included in the output. This is because the three
numbers with the input prime signatures must be distinct. This is but one
of the many tricky things needed to write this function.

But then, once the function is written and debugged, then the rest of the
job isn't that hard (or maybe you see something I don't, quite possible!)

My thinking is that I would apply the function to all triples of prime
signatures that are IN the set to generate a list of prime signatures that
are OUT. Then, I would find the "smallest" prime signature not already
known to be IN or OUT, and define it to be IN. Rinse and repeat.

Now, about "smallest", that's pretty easy. I would use a list of integer
partitions in a standard sequence. (I've already written *that* part of the
program!)
()
(1)
(2)
(1,1)
(3)
(2,1)
(1,1,1)
(4)
(3,1)
(2,2)
(2,1,1)
(1,1,1,1)
(5)
(4,1)
(3,2)
(3,1,1)
(2,2,1)
(2,1,1,1)
(1,1,1,1,1)
(6)
(5,1)
(4,2)
(4,1,1)
(3,3)
(3,2,1)
(3,1,1,1)
(2,2,2)
(2,2,1,1)
(2,1,1,1,1)
(1,1,1,1,1,1)
etc.

--Graeme McRae
Palmdale, CA

On Fri, Aug 26, 2016 at 2:21 PM, Bob Selcoe <rselcoe at entouchonline.net>
wrote:

> Hi Graeme and Seqfans,
>
> I submitted a proof yesterday (revised today) on A026477 for Charles'
> initial conjecture, noting that defining which signatures are IN and OUT
> becomes increasingly complex as the sequence progresses; I welcome any
> revisions to make the proof clearer.
>
> Then, find the "smallest" prime signature not previously listed as IN or
>> OUT. This, of course, is the next one IN the sequence. The "smallest"
>> prime
>> signature means the prime signature with the smallest sum, listed in
>> high-to-low collating sequence. (e.g. prime signatures whose sum is 4
>> would
>> be considered in this order: (4), (3,1), (2,2), (2,1,1), (1,1,1,1))
>>
>
> Graeme, if I understand correctly, I think you may encounter some
> difficulty with this approach.  For example, (5,5) is OUT because (3,3) and
> (2) are IN rather than (2,2).   So I think it's more complicated than just
> looking at signature sums.  Am I missing something?
>
> Overall, I suspect coming up with a solution will be quite challenging.
>
> Cheers,
> Bob S.
>
>
> --------------------------------------------------
> From: "Graeme McRae" <graememcrae at gmail.com>
> Sent: Friday, August 26, 2016 2:26 PM
> To: "Sequence Fanatics Discussion list" <seqfan at list.seqfan.eu>
> Subject: [seqfan] Re: Is A026477 determined by prime signatures?
>
>
> I've been reading this thread about A026477 with great interest, and have
>> been trying to think about how I would write a program to build a list of
>> prime signatures representing numbers that are IN (and a list that are
>> OUT)
>> of the sequence.
>>
>> My first thought was to start with the prime signatures of 1, 2, and 3,
>> which are (), (1), and (1), respectively, and then consider the "products"
>> of all triples of prime signatures that are already IN. These products,
>> then, will be OUT.
>>
>> Then, find the "smallest" prime signature not previously listed as IN or
>> OUT. This, of course, is the next one IN the sequence. The "smallest"
>> prime
>> signature means the prime signature with the smallest sum, listed in
>> high-to-low collating sequence. (e.g. prime signatures whose sum is 4
>> would
>> be considered in this order: (4), (3,1), (2,2), (2,1,1), (1,1,1,1))
>>
>> When finding the products of prime signatures, I need to consider that (1)
>> and (1) must represent different primes, so their product can't be (2).
>> However, the prime factors of (1,1) and (1,1) need not be unique, so their
>> products include (2,1,1) and (1,1,1,1) but not (2,2).
>>
>> I'll give this some more thought, and try a little programming using the
>> VBA that comes with MS Excel. Who knows? Maybe some interesting sequences
>> (or a comment on this sequence) might come out of it.
>>
>> --Graeme McRae
>> Palmdale, CA
>>
>> On Fri, Aug 26, 2016 at 11:55 AM, Charles Greathouse <
>> charles.greathouse at case.edu> wrote:
>>
>> I also haven't found a good way of discovering which prime signatures are
>>> in the sequence. In principle this is combanatorial but I don't know of a
>>> good algorithm.
>>>
>>> Charles Greathouse
>>> Case Western Reserve University
>>>
>>> On Fri, Aug 26, 2016 at 7:17 AM, Don Reble <djr at nk.ca> wrote:
>>>
>>> > A026477... a(1) = 1, a(2) = 2, a(3) = 3; and for n > 3,
>>> >> a(n) = smallest number > a(n-1) and not of the form a(i)*a(j)*a(k)
>>> >> for 1 <= i < j < k < n.
>>> >>
>>> >> It seems that if two numbers have the same prime signature (multiset
>>> >> of
>>> >> prime exponents) then either both or neither are in the sequence, but
>>> >> I
>>> >> can't prove this.
>>> >>
>>> >
>>> >    Just do strong induction on the number of prime factors (sum of
>>> >    signature exponents).
>>> >
>>> > ... prime powers p^r can only be r = {1,2,4,8,15,22...}, ...
>>> >>
>>> >
>>> >    Yes: A026474.
>>> >    Also, square-free numbers have 3n+1 prime factors.
>>> >
>>> >    This suggests that A026477 intersect A025487 (least value of each
>>> >    signature) would be a worthy sequence. But I don't see how to easily
>>> >    recognize those signatures.
>>> >
>>> >       value  signature
>>> >           1:
>>> >           2:  1
>>> >           4:  2
>>> >          16:  4
>>> >         120:  3  1 1
>>> >         210:  1  1 1 1
>>> >         216:  3  3
>>> >         256:  8
>>> >         384:  7  1
>>> >        2880:  6  2 1
>>> >        6300:  2  2 2 1
>>> >        7200:  5  2 2
>>> >       15360: 10  1 1
>>> >       15552:  6  5
>>> >       26880:  8  1 1 1
>>> >       27648: 10  3
>>> >       32768: 15
>>> >       49152: 14  1
>>> >       73728: 13  2
>>> >       83160:  3  3 1 1 1
>>> >      120120:  3  1 1 1 1 1
>>> >      189000:  3  3 3 1
>>> >      510510:  1  1 1 1 1 1 1
>>> >      921600: 12  2 2
>>> >     1399680:  7  7 1
>>> >     1966080: 17  1 1
>>> >     2365440: 11  1 1 1 1
>>> >     2822400:  8  2 2 2
>>> >     2985984: 12  6
>>> >     3440640: 15  1 1 1
>>> >     4194304: 22
>>> >     4860000:  5  5 4
>>> >     5670000:  4  4 4 1
>>> >     6291456: 21  1
>>> >     6912000: 11  3 3
>>> >     9437184: 20  2
>>> >    10644480: 10  3 1 1 1
>>> >    15375360: 10  1 1 1 1 1
>>> >    60466176: 10 10
>>> >    65345280:  8  1 1 1 1 1 1
>>> >    71663616: 15  7
>>> >   117964800: 19  2 2
>>> >   127401984: 19  5
>>> >   161243136: 13  9
>>> >   251658240: 24  1 1
>>> >   251942400:  9  9 2
>>> >   302776320: 18  1 1 1 1
>>> >   361267200: 15  2 2 2
>>> >   440401920: 22  1 1 1
>>> >   536870912: 29
>>> >   805306368: 28  1
>>> >   892371480:  3  1 1 1 1 1 1 1 1
>>> >  1109908800:  6  2 2 2 2 1
>>> >  1207959552: 27  2
>>> >  1327104000: 17  4 3
>>> >  1968046080: 17  1 1 1 1 1
>>> >  4232632320: 11 10 1 1
>>> >  6469693230:  1  1 1 1 1 1 1 1 1 1
>>> >  9172942848: 22  7
>>> >  9932482560: 11  1 1 1 1 1 1 1
>>> > 10883911680: 12 12 1
>>> > 12570798240:  5  5 1 1 1 1 1 1
>>> > 13759414272: 21  8
>>> > 13783770000:  4  4 4 1 1 1 1
>>> > 15330615300:  2  2 2 2 2 2 1
>>> > 16307453952: 26  5
>>> > 23279477760: 10 10 1 1 1
>>> > 24461180928: 25  6
>>> > 32212254720: 31  1 1
>>> > 32248627200: 16  9 2
>>> > 38755368960: 25  1 1 1 1
>>> > 39729690000:  4  4 4 3 1 1
>>> > 56371445760: 29  1 1 1
>>> > 68719476736: 36
>>> > 103079215104: 35  1
>>> > 114223549440: 10  1 1 1 1 1 1 1 1
>>> > 154618822656: 34  2
>>> > 156728328192: 15 14
>>> > 169869312000: 24  4 3
>>> > 251909898240: 24  1 1 1 1 1
>>> > 408410100000:  5  5 5 5
>>> > 717001084800:  7  2 2 2 2 1 1 1
>>> > 812665405440: 17 11 1 1
>>> > 828120733440:  8  1 1 1 1 1 1 1 1 1
>>> >
>>> > --
>>> > Don Reble  djr at nk.ca
>>> >
>>> >
>>> >
>>> > --
>>> > Seqfan Mailing list - http://list.seqfan.eu/
>>> >
>>>
>>> --
>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>
>>>
>> --
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>
```