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

[Charles Greathouse]

I guess you could look at it that way: the prime signature is an
ordered finite collection (i.e., a tuple) and there are different
types of prime signatures, the "OEIS prime signature" and the
"MathWorld prime signature" which are the reverses of each other.  I
prefer to think of it as the multiset, and consider the OEIS and
MathWorld ways as just two different conventions on writing the
multiset.  I can't see any reason to do otherwise, but YMMV.

Charles Greathouse
Analyst/Programmer
Case Western Reserve University


On Mon, Jun 11, 2012 at 12:56 PM, Matthew Vandermast
<ghodges14 at comcast.net> wrote:
>>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/
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/