names of functions

Antti Karttunen Antti.Karttunen at
Wed Apr 23 12:13:20 CEST 2003

"y.kohmoto" wrote:

>     to seqfans :
>     No one told me the names of functions:
>     >a function which chooses p power in the factorization of n :
>     >n=product p_i^r_i    ->    f_p (n)=p^r , where p=p_i, r=r_i
>     >ex.    f_3 (720)=f_3 (2^4*3^2*5)=3^2 , f_7 (15)=1
>     >a function which deletes  p power in the factorization of n :
>     >n=product p_i^r_i    ->    g_p (n)=n/p^r , where p=p_i, r=r_i
>     >ex.    g_3 (720)=g_3 (2^4*3^2*5)=2^4*5 , g_7 (15)=15
>     Does it mean they don't exist?
>     If so, let's give them names.
>     fac_p (n) =  p^r,  where p^r is the highest power of p dividing n.
>     cof_p (n) =  n/p^r,  where p^r is the highest power of p dividing n.

Dear Yasutoshi,

A similar function to fac_p occurs as a 2-ary function on the page 37 of the textbook
of mathematical logic I have been browsing,
(Jouko Väänänen: Matemaattinen logiikka, Gaudeamus, Helsinki, 1987. ISBN 951-662-422-7)
with the name and definition:

  exp(m,i) = The exponent of prime p_i in the prime factorization of m.

It is used for the same Gödelization purpose in that book,
as the function "Gl" (see after [182]):

n Gl x is the n-th term of the series of numbers assigned to the number x (for n > 0 and n not greater than the length of this series).

given as the sixth function in the English translation
available at URL:

although of course, it gives the same results only for
integers of the form p1^e1 * p2^e2 * p3^e3 * ... pj^ej
with all exponents e1-ej > 0, i.e. with none of
the primes "in between" missing.

Note how Gödel uses in the fifth definition (function Pr,
the nth Prime number) Pr(n)!+1 as the upper limit
of limited search (minimalization) operator when searching
for Pr(n+1), which makes me wonder whether Bertrand's
postulate wasn't proved yet by then? (I.e. 2*Pr(n) would be enough).
Of course it doesn't change the logical argument, but I
have been actually implementing some of these functions
in Scheme, not straightforwardly, but using the primitive
recursive constructions, so the actual running time
was a bit of concern.

Note also how the eighth operation:
 x * y corresponds to the operation of "joining together" two finite series of numbers.
when modified such a way that it uses exp(m,i) above, instead of Gödel's
own Gl, as to make it well defined on all N, would make a nice

So, about the names?

That's precisely what the EIS is for! In the future one refers to
all 1-ary and 2-ary N -> Z functions as Axxxxxx and Ayyyyyy,
instead of overloading phi, mu and tau the umpteenth time...


Antti Karttunen

More information about the SeqFan mailing list