Exercises 11
P.242: 4.7.2: (a),(c),(d)
附加题：
1、 设当 x 是完全平方时 f(x)=2x，否则 f(x)=2x+1。试证明 f 是原始递归的。
2、 设当 x≠0 时
σ
(x)是 x 的所有因子之和；
σ
(0)＝0。试证明
σ
(x)是原始递归的。
3、 设
π
(x)是小于等于 x 的素数的个数。试证明
π
(x)是原始递归的。
4.7.2: (a) factorial(n)=n!
the recursive equations:
0!=1
(n+1)!=n!·succ(n)
4.7.2: (c) prime(n), the predicate that that is 1 if n is a prime number.
{
}
() 1&( ) 1 ~(| )
t
prime n x t t t n t n
≤
⇔> ∀ = =∪∪
where,
predicate: y|x ( x is divided exactly by y)
4.7.2: (c) p
n
, the nth prime number, where p
0
=0, p
1
=2, p
2
=3, and so on.
For 0<i≤n,
()!1
1
n
ii
p
K
p
+
=+
p
, where K is an integer. i.e. there
must be a prime between p
n
and (p
n
)!+1. Such that we have
p
n
≤ (p
n
)!+1
So, the recursive equations:
p(0)=2
[
]
1min
!1
()&
n
nn
tp
p
tprimettp
+
≤+
=>
- 1
- 2
前往页