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

Bob Selcoe rselcoe at entouchonline.net
Fri Aug 26 23:21:30 CEST 2016

```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?

> 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/
>
```