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

Graeme McRae graememcrae at gmail.com
Fri Aug 26 21:26:07 CEST 2016

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