# [seqfan] Re: Prime signature of 1, and second signature

Matthew Vandermast ghodges14 at comcast.net
Mon Jun 11 18:56:35 CEST 2012

```>I'm not sure what you mean by a list as distinct from a multiset.
Normally I would take this to mean a tuple, but that can't be the
right definition here since you want the signature of 18 to be the
same as the signature of 12.

Let me address this question as best I can starting with MathWorld.  MathWorld defines n's prime signature (when n >1) as a "sorted list of nonzero exponents."  MathWorld (and A118914) sorts these exponents in nondecreasing order. In that version of prime signature, the prime signature of both 12 and 18 is the list (1,2). The exponents could also be sorted (and in the OEIS, I believe they conventionally have been sorted) in nonincreasing order.  In that version, the prime signature of both 12 and 18 is the list (2,1).

It's my understanding that the lists (1,2) and (2,1) qualify as different lists (even though 12 and 18 correspond to the same list in each version of prime signature).  But the two seemingly-different lists express the same multiset.  Therefore, it's my understanding that a list is, in principle, conceptually different from the multiset it represents. (Note: This doesn't depend on whether one accepts or rejects MathWorld's definition of a prime signature as a list and not a multiset.)  If this is an error, I hope it's at least an understandable one.

I'm not sure I feel up to defining the concept "list" at the moment, but it's my understanding that the makeup of a specific list depends not only on the multiset it represents, but the way that multiset is ordered in the list.  I could be wrong about this. On the other hand, perhaps sources (if any) that imply otherwise could be wrong.  On the third hand, maybe it's an unsettled terminological question at this point.

Thanks,
Matt Vandermast

----- Original Message -----
From: Charles Greathouse <charles.greathouse at case.edu>
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
Sent: Mon, 11 Jun 2012 15:30:02 -0000 (UTC)
Subject: [seqfan] Re: Prime signature of 1, and second signature

> I don't want to base too much on MathWorld's prime signature page (as great as that site usually is). But what I'm respectfully wondering at the moment is:  Is it possible that, from early on, there were variant understandings of what prime signature meant?  Perhaps some people understood the prime signature to be the multiset itself, and others understood it to be something (a list of exponents, when n > 1) that *signified* that multiset?

I'm not sure what you mean by a list as distinct from a multiset.
Normally I would take this to mean a tuple, but that can't be the
right definition here since you want the signature of 18 to be the
same as the signature of 12.

Charles Greathouse
Analyst/Programmer
Case Western Reserve University

On Mon, Jun 11, 2012 at 11:13 AM, Matthew Vandermast
wrote:
> Thanks. In a paper by Jean-Louis Nicolas in the 1987 book Ramanujan Revisited ("On Highly Composite Numbers"), Nicolas refers to the least integers of each prime signature as "w.n.i.e." (with nonincreasing exponent) integers.  I wonder if the phrase "prime signature" had been coined by then.  It's a nice phrase, anyway.
>
> The earliest written definition of prime signature of which I am personally aware was written for the MathWorld site in (I think) 2006. I'd really appreciate seeing references to earlier ones, if anyone knows of any.
>
> For what it's worth, MathWorld defines the prime signature of  n>1 as a "sorted list of nonzero exponents."  I.e., *not* the multiset itself, but a list that *signifies* that multiset.  MathWorld also chose 1 to signify the empty multiset, whereas I think 0 would have been a better choice, and a more OEIS-traditional choice, too.
>
> I don't want to base too much on MathWorld's prime signature page (as great as that site usually is). But what I'm respectfully wondering at the moment is:  Is it possible that, from early on, there were variant understandings of what prime signature meant?  Perhaps some people understood the prime signature to be the multiset itself, and others understood it to be something (a list of exponents, when n > 1) that *signified* that multiset?
>
> Take this familiar OEIS comment (found under A008966 and dozens of other sequences; originally written by Neil unless I'm mistaken):
>
>
> a(n) depends only on prime signature of n (cf. A025487). So a(24) = a(375) since 24=2^3*3 and 375=3*5^3 both have prime signature (3,1).
>
> I believe that parentheses are usually used for a list, and brackets are usually used for a set or multiset. Again, having the prime signature not be the multiset itself is fine with me. I also think the "depends only on" phrase is probably justifiable even if the prime signature is a list, rather than a multiset that that list signifies. To me, "a(n) depends only on prime signature of n" seems an essentially OK way of expressing the idea: "If you know the prime signature of n, you know a(n) with certainty."
>
> I'm not usually as fond of splitting semantic hairs as I may seem in some earlier paragraphs.  I just think it would be nice for the OEIS to have a way to "signify" the prime signature of as many n as possible - and that this is even more key for the second signature. "Kludge" is a fun word for the conventional 0s denoting the absence of other suitable a(n)s, but I still like it that the OEIS usually tries to have a(n) for as many n as possible.  And again, for anyone who may have missed my response to Marc LeBrun's comments: In any case, I'll be submitting the second signature of non-squarefree numbers so people can find that if they look for it. But I suspect that the complete version would be helpful, too.
>
> Regards,
> Matt  Vandermast
> ----- Original Message -----
> From: David Wilson
> To: Sequence Fanatics Discussion list
> Sent: Sun, 10 Jun 2012 22:00:35 -0000 (UTC)
> Subject: [seqfan] Re: Prime signature of 1, and second signature
>
> I did not invent the phrase "prime signature," nor do I remember where I
> heard it. At the time I submitted A025487, I understood it to be the
> correct terminology.
>
> I certainly did not define the concept. The term "prime signature of n"
> is shorthand for "the exponents in the prime factorization of n counted
> with multiplicity," an idea that has been around for centuries. At least
> as far back as the 1700's it has been known how to compute the number of
> divisors of n from the exponents in the prime factorization of n
> (without knowing the primes). Today we might say "tau(n) is a function
> of the prime signature of n" but this is mere semantics, not a
> conceptual leap.
>
> On 6/10/2012 3:06 PM, Matthew Vandermast wrote:
>> Thanks, David.  I've been curious about the history of the phrase "prime signature." Did you invent the phrase and/or first define the concept? If so, my hat is off to you (if not, my hat is still off just for submitting the sequence, which is perhaps my favorite in the database).  I was also influenced by your A001055 comment when writing my original e-mail about this.
>>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/

_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/

```