1/* 2 * palindrome - palindrome utilities 3 * 4 * Copyright (C) 2021 Landon Curt Noll 5 * 6 * Calc is open software; you can redistribute it and/or modify it under 7 * the terms of the version 2.1 of the GNU Lesser General Public License 8 * as published by the Free Software Foundation. 9 * 10 * Calc is distributed in the hope that it will be useful, but WITHOUT 11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 12 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General 13 * Public License for more details. 14 * 15 * A copy of version 2.1 of the GNU Lesser General Public License is 16 * distributed with calc under the filename COPYING-LGPL. You should have 17 * received a copy with calc; if not, write to Free Software Foundation, Inc. 18 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 19 * 20 * Under source code control: 2021/11/06 14:35:37 21 * File existed as early as: 2021 22 * 23 * Share and enjoy! :-) http://www.isthe.com/chongo/tech/comp/calc/ 24 */ 25 26 27/* 28 * digitof - return the a digit of a value 29 * 30 * NOTE: We assume base 10 digits and place 1 is the units digit. 31 * 32 * given: 33 * val value to find a digit of 34 * place digit place 35 * 36 * returns: 37 * value (>= 0 and < 10) that is the place-th digit of val 38 * or 0 if place is not a digit of val 39 */ 40define digitof(val, place) 41{ 42 local d; /* length of val in digits */ 43 44 /* determine length */ 45 d = digits(val); 46 47 /* firewall - return 0 if digit place doesn't exist */ 48 if (place < 1 || place > d) { 49 return 0; 50 } 51 52 /* return the place-th digit of val as a single digit */ 53 return (val // (10^(place-1))) % 10; 54} 55 56 57/* 58 * copalplace - determine the other place in a palindrome 59 * 60 * NOTE: We assume base 10 digits and place 1 is the units digit. 61 * 62 * given: 63 * d digits of a value 64 * place digit place 65 * 66 * returns: 67 * given palindrome val, the other digit paired with place 68 * or 0 if place is not a digit of val 69 */ 70define copalplace(d, place) 71{ 72 /* firewall - return 0 if digit place doesn't exist */ 73 if (d < 1 || place < 1 || place > d) { 74 return 0; 75 } 76 77 /* return digit coplace */ 78 return d+1 - place; 79} 80 81 82/* 83 * upperhalf - return the upper half of a palindrome 84 * 85 * NOTE: We assume base 10 digits and place 1 is the units digit. 86 * 87 * NOTE: When the value has an odd number of digits, the upper half 88 * includes the middle digit. 89 * 90 * given: 91 * val a value 92 * 93 * returns: 94 * the upper half digits of a value 95 */ 96define upperhalf(val) 97{ 98 local d; /* length of val in digits */ 99 local halfd; /* length of upper hand of val */ 100 101 /* determine length */ 102 d = digits(val); 103 halfd = d // 2; 104 105 /* return upper half */ 106 return (val // 10^halfd); 107} 108 109 110/* 111 * mkpal - make a value into a palindrome 112 * 113 * NOTE: We assume base 10 digits and place 1 is the units digit. 114 * 115 * given: 116 * val a value 117 * 118 * returns: 119 * val as a palindrome with lower half being reverse digits of val 120 */ 121define mkpal(val) 122{ 123 local d; /* length of val in digits */ 124 local i; /* counter */ 125 local ret; /* palindrome being formed */ 126 127 /* determine length */ 128 d = digits(val); 129 130 /* insert digits in reverse order at the bottom */ 131 ret = val; 132 for (i=0; i < d; ++i) { 133 ret = ret*10 + digit(val, i); 134 } 135 return ret; 136} 137 138 139/* 140 * mkpalmiddigit - make a value into a palindrome with a middle digit 141 * 142 * NOTE: We assume base 10 digits and place 1 is the units digit. 143 * 144 * given: 145 * val a value 146 * digit the digit to put into the middle of the palindrome 147 * 148 * returns: 149 * val as a palindrome with lower half being reverse digits of val 150 * and digit as a middle digit 151 */ 152define mkpalmiddigit(val, digit) 153{ 154 local d; /* length of val in digits */ 155 local i; /* counter */ 156 local ret; /* palindrome being formed */ 157 158 /* determine length */ 159 d = digits(val); 160 161 /* insert digits in reverse order at the bottom */ 162 ret = val*10 + digit; 163 for (i=0; i < d; ++i) { 164 ret = ret*10 + digit(val, i); 165 } 166 return ret; 167} 168 169 170/* 171 * ispal - determine if a value is a palindrome 172 * 173 * NOTE: We assume base 10 digits and place 1 is the units digit. 174 * 175 * given: 176 * val a value 177 * 178 * returns: 179 * 1 ==> val is a palindrome 180 * 0 ==> val is NOT a palindrome 181 */ 182define ispal(val) 183{ 184 local half; /* upper half of digits of val */ 185 local digit; /* middle digit */ 186 187 /* case: val has an even number of digits */ 188 if (iseven(digits(val))) { 189 190 /* test palindrome-ness */ 191 return (val == mkpal(upperhalf(val))); 192 193 /* case: val can an odd number of digits */ 194 } else { 195 196 /* test palindrome-ness */ 197 half = upperhalf(val); 198 digit = half % 10; 199 half //= 10; 200 return (val == mkpalmiddigit(half, digit)); 201 } 202} 203 204 205/* 206 * palnextpal - return next palindrome from a known palindrome 207 * 208 * NOTE: We assume base 10 digits and place 1 is the units digit. 209 * 210 * given: 211 * pal a palindrome 212 * 213 * returns: 214 * next palindrome > pal 215 */ 216define palnextpal(pal) 217{ 218 local paldigits; /* digits in pal */ 219 local half; /* upper half of newval */ 220 local newhalf; /* half+1 */ 221 local newpal; /* new palindrome */ 222 223 /* case: negative palindrome */ 224 if (pal < 0) { 225 return -(palprevpal(-pal)); 226 } 227 228 /* 229 * start with upper half 230 */ 231 half = upperhalf(pal); 232 233 /* 234 * prep to find a larger palindrome 235 */ 236 newhalf = half+1; 237 238 /* 239 * form palindrome from new upper half 240 * 241 * We need to watch for the corner case where changing the 242 * half changes the number of digits as this will impact 243 * or even/odd number of digits processing. 244 */ 245 paldigits = digits(pal); 246 if (digits(newhalf) == digits(half)) { 247 /* no change in half digits: process as normal */ 248 if (iseven(paldigits)) { 249 newpal = mkpal(newhalf); 250 } else { 251 newpal = mkpalmiddigit(newhalf // 10, newhalf % 10); 252 } 253 } else { 254 /* change in half digits: process as opposite */ 255 if (iseven(paldigits)) { 256 newpal = mkpalmiddigit(newhalf // 10, newhalf % 10); 257 } else { 258 newpal = mkpal(newhalf); 259 } 260 } 261 262 /* 263 * return the new palindrome 264 */ 265 return newpal; 266} 267 268 269/* 270 * nextpal - return next palindrome from a value 271 * 272 * NOTE: We assume base 10 digits and place 1 is the units digit. 273 * 274 * given: 275 * val a value 276 * 277 * returns: 278 * next palindrome > val 279 */ 280define nextpal(val) 281{ 282 local newval; /* val+1 */ 283 local newvaldigits; /* digits in newval */ 284 local half; /* upper half of newval */ 285 local pal; /* palindrome test value */ 286 local newpal; /* new palindrome */ 287 288 /* case: negative value */ 289 if (val < 0) { 290 return -(prevpal(-val)); 291 } 292 293 /* 294 * start looking from a larger value 295 */ 296 newval = val+1; 297 newvaldigits = digits(newval); 298 299 /* case: single digit palindrome */ 300 if (newvaldigits < 2) { 301 return newval; 302 } 303 304 /* 305 * start with next upper half 306 */ 307 half = upperhalf(newval); 308 309 /* 310 * form palindrome from upper half 311 * 312 * We need to deal with even vs. odd digit counts 313 * when forming a palindrome from a half as the 314 * half may not or may include the middle digit. 315 */ 316 if (iseven(newvaldigits)) { 317 pal = mkpal(half); 318 } else { 319 pal = mkpalmiddigit(half // 10, half % 10); 320 } 321 322 /* 323 * case: we found a larger palindrome, we are done 324 */ 325 if (pal > val) { 326 return pal; 327 } 328 329 /* 330 * we need to find an even larger palindrome 331 */ 332 newpal = palnextpal(pal); 333 334 /* 335 * return the new palindrome 336 */ 337 return newpal; 338} 339 340 341/* 342 * palprevpal - return previous palindrome from a palindrome 343 * 344 * NOTE: We assume base 10 digits and place 1 is the units digit. 345 * 346 * given: 347 * pal a palindrome 348 * 349 * returns: 350 * previous palindrome < pal 351 */ 352define palprevpal(pal) 353{ 354 local paldigits; /* digits in pal */ 355 local half; /* upper half of newval */ 356 local newhalf; /* half+1 */ 357 local newpal; /* new palindrome */ 358 359 /* case: negative value */ 360 if (pal < 0) { 361 return -(palnextpal(-pal)); 362 } 363 364 /* case: single digit palindrome */ 365 if (pal < 10) { 366 newpal = pal-1; 367 return newpal; 368 } 369 370 /* case: 10 or 11 */ 371 if (pal < 12) { 372 newpal = 9; 373 return newpal; 374 } 375 376 /* 377 * start with upper half 378 */ 379 half = upperhalf(pal); 380 381 /* 382 * prep to find a smaller palindrome 383 */ 384 newhalf = half-1; 385 386 /* 387 * form palindrome from new upper half 388 * 389 * We need to watch for the corner case where changing the 390 * half changes the number of digits as this will impact 391 * or even/odd number of digits processing. 392 */ 393 paldigits = digits(pal); 394 if (digits(newhalf) == digits(half)) { 395 /* no change in half digits: process as normal */ 396 if (iseven(paldigits)) { 397 newpal = mkpal(newhalf); 398 } else { 399 newpal = mkpalmiddigit(newhalf // 10, newhalf % 10); 400 } 401 } else { 402 /* change in half digits: process as opposite */ 403 if (iseven(paldigits)) { 404 newpal = mkpalmiddigit(newhalf // 10, newhalf % 10); 405 } else { 406 newpal = mkpal(newhalf); 407 } 408 } 409 410 /* 411 * return the new palindrome 412 */ 413 return newpal; 414} 415 416 417/* 418 * prevpal - return previous palindrome from a value 419 * 420 * NOTE: We assume base 10 digits and place 1 is the units digit. 421 * 422 * given: 423 * val a value 424 * 425 * returns: 426 * previous palindrome < val 427 */ 428define prevpal(val) 429{ 430 local newval; /* val-1 */ 431 local newvaldigits; /* digits in newval */ 432 local half; /* upper half of newval */ 433 local pal; /* palindrome test value */ 434 local newpal; /* new palindrome */ 435 436 /* case: negative value */ 437 if (val < 0) { 438 return -(nextpal(-val)); 439 } 440 441 /* 442 * start looking from a smaller value 443 */ 444 newval = val-1; 445 newvaldigits = digits(newval); 446 447 /* case: single digit palindrome */ 448 if (newvaldigits < 2) { 449 return newval; 450 } 451 452 /* 453 * start with previous upper half 454 */ 455 half = upperhalf(newval); 456 457 /* 458 * form palindrome from upper half 459 * 460 * We need to deal with even vs. odd digit counts 461 * when forming a palindrome from a half as the 462 * half may not or may include the middle digit. 463 */ 464 if (iseven(newvaldigits)) { 465 pal = mkpal(half); 466 } else { 467 pal = mkpalmiddigit(half // 10, half % 10); 468 } 469 470 /* 471 * case: we found a smaller palindrome, we are done 472 */ 473 if (pal < val) { 474 return pal; 475 } 476 477 /* 478 * we need to find an even smaller palindrome 479 */ 480 newpal = palprevpal(pal); 481 482 /* 483 * return the new palindrome 484 */ 485 return newpal; 486} 487 488 489/* 490 * nextprimepal - return next palindrome that is a (highly probable) prime 491 * 492 * NOTE: We assume base 10 digits and place 1 is the units digit. 493 * 494 * given: 495 * val a value 496 * 497 * returns: 498 * next palindrome (highly probable) prime > val 499 */ 500define nextprimepal(val) 501{ 502 local pal; /* palindrome test value */ 503 local dpal; /* digits in pal */ 504 505 /* 506 * pre-start under the next palindrome 507 */ 508 pal = nextpal(val-1); 509 510 /* 511 * loop until we find a (highly probable) prime or 0 512 */ 513 do { 514 515 /* case: negative values and tiny values */ 516 if (pal < 2) { 517 return 2; 518 } 519 520 /* 521 * compute the next palindrome 522 */ 523 pal = palnextpal(pal); 524 dpal = digits(pal); 525 526 /* case: 11 is the only prime palindrome with even digit count */ 527 if (pal == 11) { 528 return 11; 529 } 530 531 /* case: even number of digits and not 11 */ 532 if (iseven(dpal)) { 533 534 /* 535 * Except for 11 (which is handled above already), there are 536 * no prime palindrome with even digits. So we need to 537 * increase the digit count and work with that larger palindrome. 538 */ 539 pal = nextpal(10^dpal); 540 } 541 542 /* case: palindrome is even or ends in 5 */ 543 if (iseven(pal % 10) || (pal%10 == 10/2)) { 544 545 /* 546 * we need to increase the bottom and top digits 547 * so that we have a chance to be prime 548 */ 549 pal += (1 + 10^(dpal-1)); 550 } 551 if (config("resource_debug") & 0x8) { 552 print "DEBUG: nextprimepal:", pal; 553 } 554 } while (ptest(pal) == 0 && pal > 0); 555 556 /* return palindrome that his (highly probable) prime or 0 */ 557 return pal; 558} 559 560 561/* 562 * prevprimepal - return prev palindrome that is a (highly probable) prime 563 * 564 * NOTE: We assume base 10 digits and place 1 is the units digit. 565 * 566 * given: 567 * val a value 568 * 569 * returns: 570 * prev palindrome (highly probable) prime < val or 0 571 */ 572define prevprimepal(val) 573{ 574 local pal; /* palindrome test value */ 575 local dpal; /* digits in pal */ 576 577 /* 578 * pre-start over the previous palindrome 579 */ 580 pal = prevpal(val+1); 581 582 /* 583 * loop until we find a (highly probable) prime or 0 584 */ 585 do { 586 587 /* 588 * case: single digit values are always palindromes 589 */ 590 if (val < 10) { 591 /* 592 * The prevcand() call will return 0 if there is no previous prime 593 * such as the case when val < 2. 594 */ 595 return prevcand(pal); 596 } 597 598 /* 599 * compute the previous palindrome 600 */ 601 pal = palprevpal(pal); 602 dpal = digits(pal); 603 604 /* case: 11 is the only prime palindrome with even digit count */ 605 if (pal == 11) { 606 return 11; 607 } 608 609 /* case: 2 digit palindrome and not 11 */ 610 if (dpal == 2) { 611 return 7; 612 } 613 614 /* case: even number of digits */ 615 if (iseven(dpal)) { 616 617 /* 618 * Except for 11 (which is handled above already), there are 619 * no prime palindrome with even digits. So we need to 620 * decrease the digit count and work with that smaller palindrome. 621 */ 622 pal = prevpal(10^(dpal-1)); 623 } 624 625 /* case: palindrome is even or ends in 5 */ 626 if (iseven(pal % 10) || (pal%10 == 10/2)) { 627 628 /* 629 * we need to decrease the bottom and top digits 630 * so that we have a chance to be prime 631 */ 632 pal -= (1 + 10^(dpal-1)); 633 } 634 if (config("resource_debug") & 0x8) { 635 print "DEBUG: prevprimepal:", pal; 636 } 637 } while (ptest(pal) == 0 && pal > 0); 638 639 /* return palindrome that his (highly probable) prime or 0 */ 640 return pal; 641} 642