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