{VERSION 5 0 "IBM INTEL NT" "5.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "Emphasis" -1 256 "Times" 1 12 128 0 128 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "Maple Input" -1 257 "Courier" 1 12 255 0 0 1 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 259 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 261 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 262 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 263 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 264 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 265 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 266 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 267 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 268 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 269 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 270 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 271 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 272 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 273 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 274 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 275 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 276 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 277 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 278 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 279 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 280 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 281 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 282 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 283 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 284 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 285 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 286 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 287 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 288 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 289 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 290 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 291 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 292 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 293 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 294 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 295 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 296 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 297 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 298 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 299 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 300 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 301 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 302 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 303 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 304 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 305 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 306 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 307 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 308 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 309 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 310 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 311 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 312 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 313 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 314 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 315 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 316 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 317 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 318 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 319 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 320 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 321 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 322 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 323 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 324 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 325 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 326 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 327 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 328 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 329 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 330 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 331 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 332 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 333 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 334 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 335 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 336 "" 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 337 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 338 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 339 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 340 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 341 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 342 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 343 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 344 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 345 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 346 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 347 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 348 "" 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 349 "" 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 350 "" 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 351 "" 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 352 "" 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 353 "" 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 354 "" 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 355 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 }{CSTYLE "" -1 356 "" 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 357 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 358 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 359 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 360 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 361 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 362 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" 18 363 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 364 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 365 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 366 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 367 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 368 "" 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 369 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 370 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 371 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 372 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 373 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 374 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 375 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 376 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 377 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 378 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 379 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 380 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 381 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 382 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 383 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 384 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 385 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 386 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 387 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 388 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 389 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 390 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 391 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 392 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 393 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 394 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 395 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 396 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 397 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 398 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 399 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 400 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 401 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 402 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 403 "" 0 1 0 0 0 0 0 2 1 0 0 0 0 0 0 1 } {CSTYLE "" -1 404 "" 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 405 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 406 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 407 "" 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 408 "" 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 409 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 410 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 411 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 412 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 413 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 414 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 415 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 416 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 417 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 418 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 419 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 420 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 421 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 422 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 423 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 424 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 425 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 426 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 427 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 428 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 429 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 430 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 431 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 432 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 433 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 434 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 435 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 436 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 437 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 438 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 439 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 440 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 441 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 442 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 443 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 444 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 445 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 446 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 447 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 448 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 449 "" 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 450 "" 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 451 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 452 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 453 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 454 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{PSTYLE "Normal " -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 1" -1 3 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8 4 1 0 1 0 2 2 0 1 }{PSTYLE "Title" -1 18 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 1 2 2 2 1 1 1 1 }3 1 0 0 12 12 1 0 1 0 2 2 19 1 }{PSTYLE "Author" -1 19 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 1 0 0 8 8 1 0 1 0 2 2 0 1 }{PSTYLE "Title" -1 256 1 {CSTYLE "" -1 -1 " Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }3 1 0 0 12 12 1 0 1 0 2 2 19 1 }{PSTYLE "Normal" -1 257 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Normal" -1 258 1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Normal" -1 259 1 {CSTYLE "" -1 -1 "T imes" 1 12 0 0 0 1 2 2 1 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 } } {SECT 0 {EXCHG {PARA 256 "" 0 "" {TEXT -1 9 "Lecture 6" }}{PARA 19 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 33 "The General Syntax of a Procedure" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 48 "The general syntax of a procedure is as f ollows:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{PARA 0 "" 0 "" {TEXT 269 4 "name" }{TEXT -1 2 ":=" }{TEXT 270 4 "proc" }{TEXT -1 17 "(P1, P2, . .., Pn)" }}{PARA 0 "" 0 "" {TEXT -1 2 " " }{TEXT 271 5 "local" } {TEXT -1 21 " L1, L2, ..., Lu; \n " }{TEXT 272 6 "global" }{TEXT -1 21 " G1, G2, ..., Gv; \n " }{TEXT 273 7 "options" }{TEXT -1 21 " O1, \+ O2, ..., Ow; \n " }{TEXT 274 11 "description" }{TEXT -1 78 " \"someth ing here to describe the procedure\"; \n S1;\n S2;\n \+ ----" }}{PARA 0 "" 0 "" {TEXT -1 12 " Sm; \n" }{TEXT 275 8 "end \+ proc" }{TEXT -1 1 ";" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 35 "In the above: \n\n" }{TEXT 260 4 "na me" }{TEXT -1 29 " is the name of the procedure" }}{PARA 0 "" 0 "" {TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 33 "P1, P2, ..., Pn is a seq uence of " }{TEXT 258 9 "arguments" }{TEXT -1 6 " (aka " }{TEXT 259 10 "parameters" }{TEXT -1 71 ") that represent the input to the proced ure. As we shall see later the " }{TEXT 414 19 "type of a parameter" } {TEXT -1 4 " P " }{TEXT 415 69 "may be declared by replacing a parame ter by an expression of the form" }{TEXT -1 19 " \n\n P:: " }{TEXT 268 4 "type" }{TEXT -1 45 ", \n\nfor example, we could have \+ \n\n P1::" }{TEXT 265 7 "integer" }{TEXT -1 6 ", P2::" }{TEXT 266 6 "matrix" }{TEXT -1 6 ", P3::" }{TEXT 267 7 "numeric" }{TEXT -1 9 ", etc...\n" }}{PARA 0 "" 0 "" {TEXT -1 187 "This means, for example , that the parameter P1 must be an integer, if it is not you will get a warning message when you attempt to use the procedure. Examples bel ow will make this clear." }}{PARA 0 "" 0 "" {TEXT -1 41 "\nL1, L2, ... , Lu represent a sequence of " }{TEXT 261 5 "local" }{TEXT -1 53 " var iables.\n\nG1, G2, ..., Gv represent a sequence of " }{TEXT 262 6 "glo bal" }{TEXT -1 58 " variables.\n\nO1, O2, . . . , Ow represent options such as " }{TEXT 334 6 "trace " }{TEXT -1 3 "and" }{TEXT 335 10 " rem ember." }{TEXT -1 32 " We will discuss these below.\n" }}{PARA 0 "" 0 "" {TEXT -1 6 "After " }{TEXT 263 11 "description" }{TEXT -1 150 " y ou may write anything enclosed in \" \". This is to help document wh at the purpose of the procedure is. \n\nS1; S2; ... , Sm represents a \+ sequence of " }{TEXT 264 10 "statements" }{TEXT -1 67 " which tell the procedure what to do. These may or may not contain " }{TEXT 383 6 "re turn" }{TEXT -1 57 " statements which provide the output of the proced ure. \n\n" }{TEXT 410 68 "Note that the last thing to be computed is r eturned unless previous " }{TEXT 336 6 "return" }{TEXT 411 106 " state ments are executed. So if the output is computed on the last line befo re end; then that is returned." }{TEXT -1 69 "\n\nAs we have seen a pr ocedure need not contain all of these elements." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 22 "For more details see ?" } {TEXT 337 9 "procedure" }{TEXT -1 4 ", ?" }{TEXT 338 7 "options" } {TEXT -1 4 ", ?" }{TEXT 339 10 "parameters" }{TEXT -1 6 ", etc." }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 "" 0 " " {TEXT -1 50 "Example of a Procedure (Member with error warning)" }} {EXCHG {PARA 0 "" 0 "" {TEXT -1 48 "We have seen that Maple has a buil t-in program " }{TEXT 276 7 "member " }{TEXT -1 104 "to test whether \+ or not x is an element of a list or set. Here we construct such a proc edure and call it " }{TEXT 277 6 "Member" }{TEXT -1 41 " to distinguis h it from Maple's built-in " }{TEXT 278 6 "member" }{TEXT -1 12 ". Not e that " }{TEXT 412 10 "x::integer" }{TEXT -1 41 " declares that x mus t be an integer, and " }{TEXT 413 7 "L::list" }{TEXT -1 32 " declares \+ that L must be a list." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 236 " Member:=proc(x::integer, L::list)\n local i;\n description \"this pr ocedure returns true if x is an integer, L is a list and x is in L\"; \n for i from 1 to nops(L) do\n if x = L[i] then return true; end \+ if;\n end do;\n false;\nend proc:\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 26 "Now lets see how it works." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "Member(5,[1,2,3]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "Member(5,5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "Member(5,[1,2,3,4,5]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "Member(5, \{1,2,3,4,5\});" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "Member(2.2,[2.3,2.2]);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 126 "We can correct this by changing Member as follows. This time we \+ leave off the type checking. We do type checking another way:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart:" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 319 "Member:=proc(x,Y)\nlocal i;\ndescription \" this procedure returns true if x is anything, Y is a set or list and x is in Y\";\nif not(type(Y, set) or type(Y,list)) then \n error \"the second argument must be a set or a list\";\nend if;\nfor i from 1 to \+ nops(Y) do\n if x = Y[i] then return true; end if;\nend do;\nfalse; \nend proc:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "Member(2.2, \+ \{1,2,z,sqrt(2), 2.2\});" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "A:=matrix([[1,2],[3,4]]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "Member(1,A);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 59 "Alternative w e could have written the procedure as follows:" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 235 "Member:=proc(x::anything,Y::\{set,list\})\nlo cal i;\ndescription \"this procedure returns true if x is anything, Y \+ is a set or list and x is in Y\";\nfor i from 1 to nops(Y) do\n if x = Y[i] then return true; end if;\nend do;\nfalse;\nend proc:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "Member(2,\{1,2,3\});" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "Member(2,[1,2,3]);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "Member(2,2*x^3+3);" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 106 "Note Well: You don't have to cons truct your own member procedure. You may use the Maple builtin procedu re " }{TEXT 416 7 "member " }{TEXT -1 38 "or for more general uses the procedure" }{TEXT 418 5 " has." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}}}{SECT 1 {PARA 3 " " 0 "" {TEXT -1 41 "Recursive Procedures: (Fibonacci Numbers)" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 2 "A \+ " }{TEXT 285 9 "recursive" }{TEXT -1 48 " procedure is a procedure whi ch \"calls itself\". " }{TEXT 340 85 "This means that the name of the \+ procedure is used in the definition of the procedure." }{TEXT -1 64 " \+ In this section we give examples of such. First a definition. " }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 4 "The " } {TEXT 312 17 "Fibonacci numbers" }{TEXT -1 181 ": The Fibonacci numbe rs form a sequence 0, 1, 2, 3, 5, 8, 13, ... It starts with 0, 1 and thereafter the n-th term is the sum of the (n-2)-nd and (n-1)-st term s in the sequence. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 136 "We will show several ways to produce Fibonacci numbers . Each procedure will give the n-th Fibonacci number. We call the firs t procedure " }{TEXT 286 4 "fib1" }{TEXT -1 12 ". Note that " }{TEXT 287 4 "fib1" }{TEXT -1 36 " is used twice in the definition of " } {TEXT 288 4 "fib1" }{TEXT -1 2 ". " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "restart;\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 93 "fib1:=proc(n)\nif n = 0 or n = 1 then \n return n; \nend if;\nfib1(n-2) + fib1(n-1);\nend proc:\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "fib1(2);" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 8 "fib1(3);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "seq(fib1(i),i=0..20);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 24 "Note from n = 2 onward, " }{TEXT 289 4 "fib1" }{TEXT -1 16 "(n) is equal t o " }{TEXT 290 4 "fib1" }{TEXT -1 8 "(n-2) + " }{TEXT 292 3 "fib" } {TEXT -1 0 "" }{TEXT 291 1 "1" }{TEXT -1 28 "(n-1). Note that to compu te " }{TEXT 293 4 "fib1" }{TEXT -1 6 "(20), " }{TEXT 294 4 "fib1" } {TEXT -1 20 " must first compute " }{TEXT 295 4 "fib1" }{TEXT -1 9 "(1 9) and " }{TEXT 296 4 "fib1" }{TEXT -1 52 "(18), but to compute each \+ of these it must compute " }{TEXT 297 4 "fib1" }{TEXT -1 9 "(18) and \+ " }{TEXT 298 4 "fib1" }{TEXT -1 9 "(17) and " }{TEXT 299 4 "fib1" } {TEXT -1 9 "(17) and " }{TEXT 300 4 "fib1" }{TEXT -1 54 "(16), and so \+ on. This takes a lot of time and storage." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 14 "By putting in " } {TEXT 283 15 "option remember" }{TEXT -1 30 ", as we now do, the proce dure " }{TEXT 417 9 "remembers" }{TEXT -1 65 " the values already comp uted --it puts them in a table, called a " }{TEXT 440 14 "remember tab le" }{TEXT -1 140 "-- and does not have to recompute them. The only pr oblem with this is it sometimes uses a lot of memory to store the comp uted values in the " }{TEXT 282 15 "remember table." }{TEXT -1 20 " We illustrate with " }{TEXT 301 4 "fib2" }{TEXT -1 2 ":\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 110 "fib2:=proc(n)\noption remember:\ni f n = 0 or n = 1 then \n return n; \nend if;\nfib2(n-2) + fib2(n-1); \nend proc:\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 284 28 "Comparison of r unning times." }{TEXT -1 11 " Note that " }{TEXT 279 6 "time()" } {TEXT -1 188 "; gives the total CPU time used since the start of the \+ Maple session your computer in seconds. So the following method gives \+ the time used for the given computation. Note how much faster " } {TEXT 419 4 "fib2" }{TEXT -1 4 " is." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 62 "starttime:=time():\n fib 1(25);\nelapsedtime:=time()-starttime;\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 62 "starttime:=time():\n fib2(25);\nelapsedtime:=time()- starttime;\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 65 " Here's how we fi nd the values stored in the remember table. For " }{TEXT 384 4 "fib1" }{TEXT -1 31 " there is no remember table: " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "op(4,eval(fib1));" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 4 "But " }{TEXT 385 4 "fib2" }{TEXT -1 46 " has a large remem ber table after calculating " }{TEXT 386 8 "fib2(25)" }{TEXT -1 1 ":" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "op(4,eval(fib2)); " }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 21 "Let's try to compute " }{TEXT 441 10 "fib2(4000)" }{TEXT -1 58 ". I suppress the output since it is a ra ther large number." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 61 "start time:=time():\nfib2(4000):\nelapsedtime:=time()-starttime;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 17 "Now the value of " }{TEXT 387 10 "fib2(40 00)" }{TEXT -1 95 " is in the remember table so it doesn't have to be \+ recomputed. Thus it is returned immediately:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 61 "starttime:=time():\nfib2(4000):\nelapsedtime:=ti me()-starttime;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 10 "Note that " } {TEXT 302 4 "fib2" }{TEXT -1 22 "(4000) is quicker the " }{TEXT 303 6 "second" }{TEXT -1 50 " time you call it since it has already calculat ed " }{TEXT 304 4 "fib2" }{TEXT -1 35 "(4000) and just looks it up in \+ its " }{TEXT 280 16 "remember table. " }{TEXT -1 88 "Such tables can c log up one's memory so to clear it out when no longer needed using the " }{TEXT 281 6 "forget" }{TEXT -1 20 " command as follows:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "forget(fib2);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 57 "See that the remember table for fib2 is r eally empty now:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "op(4,ev al(fib2));\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 276 "Recursive proced ures can be written as non-recursive procedures--although usually with more effort. For example, here is a way to generate the Fibonacci nu mbers by a procedure which doesn't call itself. It is a little harder \+ to understand, but requires much less memory that " }{TEXT 388 6 "fib2 . " }{TEXT -1 9 "I call it" }{TEXT 421 7 " fib3. " }{TEXT 420 50 "Read it carefully and try to see what it is doing." }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 212 "fib3:=proc(n)\nlocal minus1,minus2,temp,i;\ni f n = 0 or n = 1 then \n return n; \nend if;\nminus2:=0;\nminus1:=1: \nfor i from 2 to n do\n temp:=minus2 + minus1;\n minus2:=minus1;\n \+ minus1:=temp;\nend do;\ntemp;\nend proc:" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 21 "seq(fib3(i),i=0..20);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 37 "Compare the time it takes to compute " }{TEXT 422 10 "fib 3(1000)" }{TEXT -1 35 " with the time it takes to compute " }{TEXT 423 8 "fib1(20)" }{TEXT -1 5 " and " }{TEXT 424 10 "fib2(1000)" } {TEXT -1 71 ": Notice which is the fastest. Note that we don't dare t ry to compute " }{TEXT 442 10 "fib1(1000)" }{TEXT -1 23 " due to how s low it is." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 63 "starttime:=ti me():\nfib3(1000);\nelapsedtime:=time() - starttime;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "starttime:=time():\nfib1(0);\nelapsedtime :=time() - starttime;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 63 "st arttime:=time():\nfib2(1000);\nelapsedtime:=time() - starttime;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 "" 0 " " {TEXT -1 22 "Remember table for sin" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 14 "The procedure " }{TEXT 443 3 "sin" }{TEXT -1 239 " will give sl ightly different output for Maple V and Maple 6,7, or 8 due to a chang ed remember table for sin. In particular in Maple 6, 7, or 8 it does \+ not contain the value for sin(Pi/12). But this value may be obtained w ith the command " }{TEXT 331 27 "convert(sin(Pi/12),radical)" }{TEXT -1 129 "; We first look at the remember table for sin. Note that any \+ procedure may have a remember table not just a recursive procedure." } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "op(4, eval(sin));" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 98 "sin(0),sin(infinity), sin(I) , sin(Pi/6), sin(-infinity), sin(Pi/2), sin(Pi/4), sin(Pi), sin(Pi/3); " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "sin(Pi/12);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "convert(%,radical);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 52 "But this doesn't work for all rational mu ltiples of " }{XPPEDIT 18 0 "pi;" "6#%#piG" }{TEXT -1 1 "." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "sin(Pi/17);" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 19 "convert(%,radical);" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 57 "We could add it to the remember table for sin as follow s:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "sin(Pi/12) := sqrt(2) /4 *(sqrt(3) -1):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "sin(Pi /12);" }{TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 52 "Note that this is now in the remember table for sin." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "op(4, eval(sin));" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 1 "\n" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 41 "Two More Examples of Recursive Procedures" }} {EXCHG {PARA 0 "" 0 "" {TEXT -1 67 "Study carefully the procedures ADD and MUL defined in this section." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 204 "ADD:=proc(f::procedure, n::nonnegint)\noption remember;\ndescript ion `this computes the sum f(0) + f(1) + f(2) +...+f(n)`;\nif n = 0 th en \n return f(0); \nelse \n return ADD(f,n-1)+f(n); \nend if;\nen d proc:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "ADD(cos,4);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "ADD(cos,-4);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 204 "MUL:=proc(f::procedure, n::nonnegi nt)\noption remember;\ndescription `this computes the product f(0)*f(1 )*f(2)*...*f(n)`;\nif n = 0 then \n return f(0); \nelse \n return \+ MUL(f,n-1)*f(n); \nend if; \nend proc:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "MUL(exp,4);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "MUL(g,5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "ADD(g,5); " }}}{EXCHG {PARA 259 "" 0 "" {TEXT -1 77 "We can make Maple think g i s a procedure if we execute the following command:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "g(-1):=2;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 112 "Note that this not only makes g into a procedure, but sets up \+ a remember table for it containing the entry -1=2." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "op(4,eval(g));" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 9 "MUL(g,5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "ADD(g,5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 114 "Both procedures can also be written with a do loop as we have seen before. Actually Maple has built-in procedu res " }{TEXT 389 3 "sum" }{TEXT -1 2 ", " }{TEXT 390 3 "add" }{TEXT -1 2 ", " }{TEXT 391 7 "product" }{TEXT -1 5 " and " }{TEXT 392 3 "mul " }{TEXT -1 181 " which do more or less what these procedures do (and are more efficiently) as we will discuss in the next lecture. These two procedures were just for the purpose of illustration." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 448 4 "NOTE" }{TEXT -1 34 ": Executing a command of the form " }{TEXT 444 11 "name(x):=y " } {TEXT -1 5 "make " }{TEXT 445 4 "name" }{TEXT -1 58 " into a procedure whereas executing a command of the form " }{TEXT 446 10 "name[x]:=y" }{TEXT -1 7 " makes " }{TEXT 447 4 "name" }{TEXT -1 14 " into a table. " }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 25 "Viewing Maple Source Code" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 114 "For programme rs, a tremendous benefit of Maple is its \"open-architecture\". You ca n access the source code to over " }{TEXT 256 3 "95%" }{TEXT -1 217 " \+ of the math routines available. This allows you to see what's going o n and in some cases you may want to change procedures to make them mor e suitable for your needs. One way to view the code is to use the co mmand " }{TEXT 426 8 "showstat" }{TEXT -1 95 " as follows. This is als o useful for debugging. Note that it numbers the lines of the program. " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "showstat(rand);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 27 "\nAnother way is to use the " }{TEXT 425 10 "interface " }{TEXT -1 37 "command as follows. First we execute:" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "interface(verboseproc=2); " }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 96 "Then we can view the code for various procedures. For example, le t's look at isprime. Applying " }{TEXT 305 5 "eval " }{TEXT -1 4 " or \+ " }{TEXT 306 6 "print " }{TEXT -1 25 "returns the source code. " }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "print(isprime);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 95 "You may find it difficult to copy and paste from \+ the output above. If so use use the command " }{TEXT 427 22 "lprint( eval(isprime));" }{TEXT -1 88 " as follows. Then you should be able to select, copy and paste into Maple input regions." }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 22 "lprint(eval(isprime));" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 156 "Now selecting the first large number in the progr am, we paste it in and factor it using ifactor. We see that it is the \+ product of all primes from 2 to 100. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "ifactor(2305567963945518424753102147331756070);" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 94 "Notice that this procedure used th e procedure igcd as well as other procedures. The procedure " }{TEXT 307 4 "igcd" }{TEXT -1 120 " is \"builtin\" and not available--as you \+ see if you try the following command. A few of the more basic commands are like " }{TEXT 308 4 "igcd" }{TEXT -1 44 " and the code is not ava ilable to the user. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "eva l(igcd);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "eval(seq);" }}} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 65 "Wh en done looking at the source code it is a good idea to reset " } {TEXT 309 11 "verboseproc" }{TEXT -1 29 " to the default output level. " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "interface(verboseproc=1);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 "" 0 " " {TEXT -1 12 "Option trace" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 310 14 "option trace: " } {TEXT -1 164 "This option causes maple to print out more details about the behavior of the procedure and may be useful during debugging. It seems to have the same effect as the " }{TEXT 428 14 "debug, undebug " }{TEXT -1 5 " and " }{TEXT 429 5 "trace" }{TEXT -1 3 ", " }{TEXT 430 7 "untrace" }{TEXT -1 55 " command mentioned previously. Here's a \+ simple example." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 116 "test:=p roc(n)\nlocal i,S;\noption trace;\nS:=0:\nfor i from 1 to n do\nif i > 2 then S:=S+i; end if;\nend do;\nS;\nend proc:" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 8 "test(4);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 31 "Remove or comment out the line " }{TEXT 311 12 "option trace" } {TEXT -1 56 "; and Re-enter the procedure to get back in normal mode. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 117 "test:=proc(n)\nlocal i ,S;\n#option trace;\nS:=0:\nfor i from 1 to n do\nif i > 2 then S:=S+i ; end if;\nend do;\nS;\nend proc:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "test(4);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 " " }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 15 " args and nargs" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 55 "The variables used as input for a procedure are called " }{TEXT 319 10 "parameters" }{TEXT -1 4 " or " }{TEXT 320 9 "arguments " }{TEXT -1 56 ". For example, in the procedure whose definition begin s " }{TEXT 313 19 "f:=proc(A,s,t,n), " }{TEXT -1 28 "A, s,t and n are called the " }{TEXT 393 9 "arguments" }{TEXT -1 4 " or " }{TEXT 394 10 "parameters" }{TEXT -1 45 " of the procedure. By using the special \+ name " }{TEXT 314 5 "args " }{TEXT -1 4 "and " }{TEXT 315 5 "nargs" } {TEXT -1 65 " one need not declare any parameters when defining a proc edure. " }{TEXT 316 8 "args[1] " }{TEXT -1 23 "is the first argument, " }{TEXT 317 8 "args[2] " }{TEXT -1 57 "is the second argument, etc., The number of arguments is " }{TEXT 318 6 "nargs." }{TEXT -1 25 " On e advantage in using " }{TEXT 381 4 "args" }{TEXT -1 5 " and " }{TEXT 382 5 "nargs" }{TEXT -1 88 " is that we don't have to specify in advan ce the number of arguments. Here's an example:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 53 "In this procedure we use the builtin Maple procedure " }{TEXT 321 3 "add" }{TEXT 395 2 ".\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 254 "Avg:=proc()\n loc al i,A,N;\n description \"this computes the average of the arguments- -all assumed to be numbers\";\n if nargs = 0 then \n error \"there \+ are no numbers to average\"; \n end if;\n A:=add(args[i],i=1..nargs) ;\n return evalf(A/nargs);\nend proc:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "Avg(1,2,1,2,1,2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "Avg(10.8,2,3,3,4,5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "Avg();" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 123 "Next w e show how to create a procedure to find the maximum of a sequence of \+ numbers. Actually Maple has a builtin function " }{TEXT 332 3 "max" } {TEXT -1 94 " to do this, but it is useful to know how it is construct ed for other purposes. Our procedure " }{TEXT 397 3 "Max" }{TEXT -1 27 " returns the largest entry " }{TEXT 396 3 "and" }{TEXT -1 95 " the index of the first occurrence of this entry. It does a little more th an Maple's procedure " }{TEXT 333 4 "max " }{TEXT -1 28 "does, but it \+ is not as fast." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 314 "Max:=pr oc()\nlocal M,w,i;\ndescription `this procedure returns the list [M,w] where M is the largest element in the input sequence and w is the ind ex of the first occurrence of M`;\n M:=args[1];\n w:=1;\n for i from 2 to nargs do\n if args[i] > M then\n M:=args[i];\n w:=i;\n \+ end if;\n end do;\n[M,w];\nend proc:\n\n" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 27 "Max(10, 110 , 445, 78, 34);" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 32 "Loca l and Global Variables Again" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 31 "We first illustrat e the use of " }{TEXT 322 16 "global variables" }{TEXT -1 52 " and som e strange things that can happen when using " }{TEXT 323 16 "local var iables." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "x:=10;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 66 "f:=proc(s)\nlocal b;\nglobal x;\nx:=s*x;\nb:=x^2;\nreturn b;\nend proc:\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "f(5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "x;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "b;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 57 "Compare the above procedure with the foll owing procedure:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart; " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "x:=10;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 58 "g:=proc(s)\nlocal b,x;\nx:=s*x;\nb:=x^2; \nreturn b;\nend proc:\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 " g(5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "x;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "b;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 18 "Another example: (" }{TEXT 324 32 "\"When local variables leave home" }{TEXT -1 3 ".\")" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 " restart;\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "w:=x;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "h:=proc()\nlocal x;\nx;\nend proc:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "z:=h();" }}} {EXCHG {PARA 259 "" 0 "" {TEXT -1 173 "It appears that both w and z ar e equal to x. But w is equal to the global variable x\nand z is equal to the local variable created inside the procedure h. So maple consid ers" }}{PARA 259 "" 0 "" {TEXT -1 57 "them to be different even though they both look the same;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "z,w;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "evalb(x=z);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "evalb(x=w);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "2*(z+w);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 60 "But notice that Maple automatically simplifies 2(x+x) to \+ 4x:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "2*(x+x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "r:=h();" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 11 "evalb(r=z);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 71 "Now z, w, r are all equal to x, but these are different x's, as we se e:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "\{z,w,r\};" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 27 "Compare with the following:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "\{x,x,x\};" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 48 "We can create yet a 4-th distinct x, as follows:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "s:=h();" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "\{z,w,r,s\};" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "2*(z+w+r+s);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "2*(x+x+x+x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}} {SECT 1 {PARA 3 "" 0 "" {TEXT -1 10 "Iteration " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 32 "Given a function f : X -> Y let " }{XPPEDIT 18 0 "x[0];" "6#&%\"xG6#\"\"!" }{TEXT -1 29 " be any element of X. Define " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {XPPEDIT 18 0 "x[1] := f(x[0]);" "6#>&%\"xG6#\"\"\"-% \"fG6#&F%6#\"\"!" }{TEXT -1 4 ", " }{XPPEDIT 18 0 "x[2] := f(x[1]); " "6#>&%\"xG6#\"\"#-%\"fG6#&F%6#\"\"\"" }{TEXT -1 3 ", " }{XPPEDIT 18 0 "x[3] := f(x[2]);" "6#>&%\"xG6#\"\"$-%\"fG6#&F%6#\"\"#" }{TEXT -1 8 ", . . . " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 16 "and, in general " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {XPPEDIT 18 0 "x[n+1] := f(x[n]);" "6#>&%\"xG6#,&%\"nG \"\"\"F)F)-%\"fG6#&F%6#F(" }{TEXT -1 13 " for n > 0. " }}{PARA 0 "" 0 "" {TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 13 "The sequence " } {XPPEDIT 18 0 "x[0],x[1],x[2];" "6%&%\"xG6#\"\"!&F$6#\"\"\"&F$6#\"\"# " }{TEXT -1 19 ", . . ., is called " }{TEXT 362 13 "the orbit of " } {XPPEDIT 363 0 "x[0];" "6#&%\"xG6#\"\"!" }{TEXT 364 35 " under the act ion of the function f" }{TEXT -1 33 ". This process is also called \+ " }{TEXT 341 40 "iteration of the function f starting at " }{XPPEDIT 18 0 "x[0];" "6#&%\"xG6#\"\"!" }{TEXT -1 23 " and is an example of a" }{TEXT 342 19 " dynamical system. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 4 "The " }{TEXT 398 47 "composition of a func tion f with itself n times" }{TEXT -1 25 " is sometimes called the " } {TEXT 343 12 "n-th iterate" }{TEXT -1 33 " of f. In Maple it is denote d by " }{TEXT 399 4 "f@@n" }{TEXT -1 92 ". Recall that if f and g are \+ functions, f@g is the composition of r and g. So, for example, " } {TEXT 400 36 "(f@@3 )(x) = (f@f@f)(x) = f(f(f(x)))" }{TEXT -1 12 ". No te that " }{TEXT 401 13 "(f@@0)(x) = x" }{TEXT -1 26 ". The parenthes es around " }{TEXT 431 7 "(f@@3) " }{TEXT -1 11 "are needed." }{TEXT 433 1 " " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "restart:\n" }}} {PARA 0 "" 0 "" {TEXT -1 155 "Here are some procedures that one may u se to investigate the dynamics of a given function. First we define a function f that we want to experiment with." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "f:=x->(25*x) mod 197;" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 25 "The following procedure, " }{TEXT 432 3 "it1" }{TEXT -1 38 ", will produce the list of the fi rst " }{TEXT 344 1 "n" }{TEXT -1 28 " iterations of any function " } {TEXT 345 4 "func" }{TEXT -1 25 " starting with the value " }{TEXT 346 5 "start" }{TEXT -1 2 ":\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 76 "it1:=proc(start,func,n)\nlocal i;\n[seq((func@@i)(start),i=0.. n)];\nend proc:\n " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 54 "We first se e what the output is for undefined g and x:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "it1(x,g,5);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 37 "Let's try the function defined above." }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 11 "it1(1,f,5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "it1(1,f,100);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 14 "\nNote t hat in " }{TEXT 434 3 "it1" }{TEXT -1 22 " each computation of " } {TEXT 402 7 "func@@n" }{TEXT -1 98 " starts from the beginning and req uires n steps. A better way to write the program is as follows:\n" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 142 "it2:=proc(start,func,n)\n l ocal i,x,SEQ;\n x:=start;\n SEQ:=x; \n for i from 1 to n do\n x:=fun c(x);\n SEQ:= SEQ, x;\n end do;\n [SEQ];\nend proc:\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "it1(x,g,5);" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 11 "it2(x,g,5);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 57 "We can also write a recursive version of this procedure:\n" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 146 "it3:=proc(start,func,n)\n o ption remember:\n if n = 0 then return [start]; fi;\n return [op(it3(s tart,func,n-1)),func(it3(start,func,n-1)[n])];\nend:\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "it3(x,g,5);" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 11 "it1(x,g,5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "it2(x,g,5);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 75 "H ere's another way to time a procedure--without getting the output howe ver:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "time(it1(1,f,300)); " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "time(it2(1,f,300));" }} }{EXCHG {PARA 0 "" 0 "" {TEXT -1 17 "For small values " }{TEXT 347 3 " it3" }{TEXT -1 70 " is fast, but for really large values it will requi re too much memory." }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "time(it3(1,f,300));" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 25 "The Famous 3x + 1 Problem" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "" 0 "" {TEXT 356 119 "This is a famous open problem in mathem atics which involves iteration of a particular function.\n\nConsider t he function " }{TEXT -1 1 "f" }{TEXT 353 41 " defined on positive inte gers by the rule" }{TEXT -1 123 " \n\n f (k) = k/2, if k is even, \n f(k) = 3k+ 1, if k is odd. \n " }{TEXT 348 48 "\nIt appears that if one starts w ith any integer " }{XPPEDIT 18 0 "n[0];" "6#&%\"nG6#\"\"!" }{TEXT -1 0 "" }{TEXT 449 14 " and iterates " }{TEXT -1 1 "f" }{TEXT 354 88 ", o ne always eventually reaches the number 1. This has been verified for \+ many values of " }{XPPEDIT 18 0 "n[0]" "6#&%\"nG6#\"\"!" }{TEXT 450 2 ", " }{TEXT 403 40 "but has not yet been proved or disproved" }{TEXT 404 22 ". It was verified for " }{XPPEDIT 18 0 "n[0]" "6#&%\"nG6#\"\"! " }{TEXT 349 24 " up to approximately 2*" }{XPPEDIT 18 0 "10^16;" "6# *$\"#5\"#;" }{TEXT -1 0 "" }{TEXT 350 86 " in 1999 and apparently the \+ computer is still running. (Search the internet for the " }{TEXT 405 12 "3x+1 problem" }{TEXT 351 8 " or the " }{TEXT 406 15 "collatz p roblem" }{TEXT 352 89 " (as it is sometimes called)--if you want more \+ up-to-date information about the problem.)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 27 "For example, starting with " } {XPPEDIT 18 0 "n[0] = 6;" "6#/&%\"nG6#\"\"!\"\"'" }{TEXT -1 105 " we h ave\n \n f(6)=3, f(3)=10, f(10)=5, f(5)=16, f(1 6)=8, f(8)=4, f(4)=2, f(2)=1. \n\n" }}{PARA 0 "" 0 "" {TEXT 355 47 "Th us in 8 steps we reach 1 if we start from 6. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 60 "Let's define a procedure \+ to implement the \"3x + 1 function\"." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 91 "f:=proc(n)\n if n mod 2 = 0 then \n return n/2 ; \n else\n return 3*n+1; \n end if;\nend proc:" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 37 "Now let's iterate it starting with 3:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "S:=[seq((f@@n)(3), n =1..10)]; " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 106 "Note that we quick ly reach 1 and then the sequence of iterates begins repeating 1, 4, 2, 1, 4, 2, 1, . . ." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 29 "We use the builtin procedure " }{TEXT 451 6 "memb er" }{MPLTEXT 1 0 0 "" }{TEXT -1 103 " as follows to determine whether or not and if so what the first value of n is for which (f@@n)(3) = 1 :" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "member(1,S,'n'); \nn; " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 199 "This shows that for n = 7 we get 1. So 1 is reached starting from 3 in 7 steps. \n\nLet's write a \+ procedure that tells us how many steps are required to reach 1 startin g with any positive integer n0: (" }{TEXT 435 36 "We could use the abo ve method using " }{TEXT 407 6 "member" }{TEXT 436 5 " and " }{TEXT 408 3 "seq" }{TEXT 437 102 ", but that's not very efficient and anyhow we don't know how far we might have to go before getting 1." }{TEXT -1 2 ")\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 158 "steps:=proc(n 0)\nlocal x,i;\n if n0 = 1 then return 0; end if;\n x:=n0;\n for i \+ from 1 do\n x:=f(x);\n if x = 1 then return i; end if;\n end do ;\nend proc:\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "steps(3); " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 23 "Let's see which number " } {XPPEDIT 18 0 "n[0] <= 1000;" "6#1&%\"nG6#\"\"!\"%+5" }{TEXT -1 35 " t akes the largest number of steps:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "max(seq(steps(n0),n0=1..1000));" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "member(178,[seq(steps(n0),n0=1..1000)],'n0'); n0;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 43 "Let's check that in fact \+ steps(871) is 178:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "steps (871);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 66 "Let's see what the larg est number reached is if we start with 871:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "L:=seq((f@@n)(871), n=1..178);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "max(L);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}} {SECT 1 {PARA 3 "" 0 "" {TEXT -1 28 "Assignment 6 -- Due Tuesday." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "" 0 "" {TEXT 325 11 "P roblem 1. " }{TEXT 366 214 "If n people (numbered 1 to n) stand in a c ircle and someone starts going around the circle and eliminating every other person till only one person is left, the number J(n) of the per son left at the end is given by " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 156 " J(n) = 1 i f n = 1\n J(n) = 2*J(n/2) - 1 if n > 1 and n is even\n \+ J(n) = 2*J((n-1)/2) + 1 if n > 1 and n is odd" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 12 "(i) Write a " }{TEXT 367 9 "recursive" }{TEXT 368 1 " " }{TEXT 369 9 "procedure" }{TEXT -1 150 " to compute J. [As a check the first 16 values (starting with 1) of J (n) are 1,1,3,1,3,5,7,1,3,5,7,9,11,13,15,1]. \n(ii)Compute the value o f J(10000). " }}{PARA 0 "" 0 "" {TEXT -1 115 "(iii) Can you explain wh y this is so much faster than our recursive procedure to compute the n -th Fibonacci number?" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 1 "[" }{TEXT 373 6 "Remark" }{TEXT -1 45 ". T he problem above is a special case of the " }{TEXT 374 16 "Josephus Pr oblem" }{TEXT -1 170 ". Instead of eliminating ever other person, one \+ could eliminate every 3rd person, every 4th person, etc. For more on \+ the history and generalizations of this problem see " }{TEXT 375 8 "Co ncrete" }{TEXT -1 1 " " }{TEXT 376 11 "Mathematics" }{TEXT -1 4 " -- \+ " }{TEXT 377 33 "A Foundation for Computer Science" }{TEXT -1 149 ", b y Graham, Knuth and Patashnik, Chapter 1. You will also find a number \+ of webpages and mathematics papers devoted to this problem if you sear ch on " }{TEXT 378 16 "Josephus Problem" }{TEXT -1 28 " via a search e ngine or via " }{TEXT 380 10 "MathSciNet" }{TEXT -1 13 " -- click on \+ " }{TEXT 379 30 "Interesting Mathematical Links" }{TEXT -1 92 " at the bottom of the USF Mathematics Department's home page -- from a USF co mputer--to use " }{TEXT 409 10 "MathSciNet" }{TEXT -1 2 ".]" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 326 11 "P roblem 2. " }{TEXT -1 37 "Write a procedure using the variable " } {TEXT 329 4 "args" }{TEXT -1 57 " that will take an unspecified finite number of numbers, " }{TEXT 370 35 "delete the smallest and the large st" }{TEXT -1 2 ", " }{TEXT 371 62 "and return the average of the rest as a floating point number." }{TEXT -1 264 " If there are fewer than \+ 3 arguments have an error message say: \"There are not enough argumen ts. There should be at least three.\" \n\nYou should have no input par ameters in the definition of the procedure. You may write it directly \+ or you may use the Maple command " }{TEXT 327 5 "sort " }{TEXT -1 30 " as a part of your program. Do " }{TEXT 328 6 "?sort " }{TEXT -1 11 "to see how " }{TEXT 330 4 "sort" }{TEXT -1 171 " works. Test your proced ure with the each of following argument sequences: \n\n 50,40,40, 4 0, 40, 10\n\n 1,2\n\n seq(100 - i, i = 1..100)\n\n seq(modp(n,11 1), n=1..1000);" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 358 9 "Problem 3" }{TEXT -1 3 ". " }{TEXT 452 13 "Happy numbers " }{TEXT -1 216 " are positive integers which end up at 1 under iterat ion of the \"sum of squares of digits map\". That is, if one defines f (x) to be the sum of the squares of the decimal digits of the positiv e integer x, then x is " }{TEXT 453 5 "happy" }{TEXT -1 56 " if for \+ some positive integer n we have (f@@n)(x) = 1. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 13 "For example, " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 16 "f(7) = 7^2=49, \+ " }}{PARA 0 "" 0 "" {TEXT -1 21 "f(49) = 4^2+9^2=97, " }}{PARA 0 "" 0 "" {TEXT -1 22 "f(97) = 9^2+7^2=130, " }}{PARA 0 "" 0 "" {TEXT -1 26 "f(130) = 1^2+3^2+0^2 = 10," }}{PARA 0 "" 0 "" {TEXT -1 21 "f(10) = 1^2+0^2 = 1. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 14 "So 7 is happy." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 33 "The first few happy numbers are \n" }}{PARA 0 " " 0 "" {TEXT -1 61 "1,7,10,13,19,23,28,31,32,44,49,68,70,79,82,86,91,9 4,97,100. \n" }}{PARA 0 "" 0 "" {TEXT -1 86 "Write a procedure that w ill declare a positive integer x to be happy (i.e., returns " }{TEXT 438 4 "true" }{TEXT -1 50 ") if the n-th iterate of f starting with x \+ gives 1" }{TEXT 357 10 " for some " }{XPPEDIT 18 0 "n <= 20;" "6#1%\"n G\"#?" }{TEXT -1 16 " --else returns " }{TEXT 439 5 "false" }{TEXT -1 65 ". Find the first 50 happy numbers. Print them out in a sequence. \+ " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 361 5 "Hints " }{TEXT -1 1 ":" }{TEXT 360 1 " " }{TEXT -1 10 " Note that" }{TEXT 359 20 " convert(x,base,10) " }{TEXT -1 138 "will give you the decimal digits of x in a list. It should help if you first write a procedure \+ to compute f(x) for any positive integer x." }}{PARA 0 "" 0 "" {TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 365 11 "Problem 4. " }{TEXT -1 152 "Show that if \+ you increase the upper bound for n in Problem 3 from 20 to a higher v alue you will not obtain any additional happy numbers less than 320? \+ " }{TEXT 372 4 "Hint" }{TEXT -1 31 ": Show that if in the sequence " } }{PARA 0 "" 0 "" {TEXT -1 51 "\n n, f(n), (f@@2)(n), . . . , (f@@20)(n)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 104 "a 4 is reached before a 1 is reached then a 1 will nev er be reached, so the number n will not be happy. " }{TEXT 454 6 "Hint : " }{TEXT -1 145 "What happens to the sequence once 4 is reached? Loo k at some examples. Then show that in 20 iterations a 1 or a 4 is reac hed for n less than 320." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 3 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 1 "." }}}{EXCHG {PARA 18 "" 0 "" {TEXT -1 0 "" }}{PARA 19 "" 0 "" {TEXT -1 0 "" }}{PARA 19 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}}{MARK "12 0 0" 28 }{VIEWOPTS 0 0 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 1 1 2 33 1 1 }