names of functions

Antti Karttunen Antti.Karttunen at iki.fi
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
of Gödel's "ON FORMALLY UNDECIDABLE PROPOSITIONS OF PRINCIPIA MATHEMATICA AND RELATED SYSTEMS",
available at URL:
http://home.ddc.net/ygg/etext/godel/godel3.htm

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
EIS-table.

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,