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

Matthew Vandermast ghodges14 at comcast.net
Mon Jun 11 17:13:15 CEST 2012

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.

Matt  Vandermast
----- Original Message -----
From: David Wilson <davidwwilson at comcast.net>
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
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/

More information about the SeqFan mailing list