This script generates sequences relating to the question of the number of bases in which a positive integer N is a palindrome. N will be a palindrome when expressed in unary, but 1 is not a legitimate base, so we are concerned only with integer bases greater than 1. N will be a ``single digit'' palindrome in any base greater than N, so we will not consider bases greater than N.
Base N and base N-1 are special cases. When they are large enough to be legitimate bases, N is 1 0 in base N, and 1 1 in base N-1. The latter is always a palindrome, and the former is a palindrome if (and only if) we allow leading 0s, viewing it as 0 1 0. We therefore default to considering only bases B
1 < B < N-1
when we count the number of bases in which N is a palindrome. The effect of including bases N-1 or N is simply to increase the count by a constant amount where they are legitimate bases.
There are several variables that influence how palindromes are counted and reported. They can be set through the use of environment variables, and it is the names of those environment variables that we will use in describing the effects.
By default, we report, for each N, the number of bases B
1 < B < N-1
in which N is a palindrome. By setting HASNOPALINS=1, we report, instead, those N for which the count is 0.
The reader might enjoy proving that for N greater than 6, only prime numbers (but not all prime numbers) are reported. See HASNOPALINS and Composite Numbers for a discussion.
We default to starting with N at 0. But, for N less than 3
1 < B < N-1
includes no bases, so the corresponding count will always be 0. You can change the initial value of N using STARTAT. For example (assuming, as we will throughout, that you can set environment variables on the command line, and that this script is called palin.pl)
STARTAT=3 palin.pl
will start at N=3.
By default, the last value of N we consider is 100, 1000 when HASNOPALINS is 1. If STOPAFTER is defined, it determines the last value of N to be considered.
By default, we do not count bases in which it would be necessary to supply one or more leading 0s to make N a palindrome. If LEADING0S is 1, we will count such bases.
By setting VERBOSE=1, additional information may be printed. This has no effect when HASNOPALINS is 1, because there is not much else to report. It changes the default report to show the bases, and the palindromes in those bases, in which N is regarded as a palindrome, as well as N and the count.
The counts in the default report are separated by blanks. You can assign the string you want to use to separate the counts to SEP.
We default to allowing only bases B
1 < B < N-1
when counting bases where N is regarded as a palindrome. The upper limit is determined by adding the BASEDELTA value, which defaults to -1, to N. You can expand or contract the range by modifying the BASEDELTA value. Expanding it, by making it greater than -1, has no interesting impact on the counts, it merely increases them by a constant value (and any expansion would render the HASNOPALINS report particularly uninteresting).
There follow several examples of using the options discussed above. Outputs are shown immediately following the commands.
1
We use STARTAT and STOPAFTER to limit N to a single value, 12. All that is reported is 1, the number of bases
1 < B < 12-1
in which 12 is a palindrome. If you are interested in more than the count, you can do
5: 2 2
12: 1
and you now see that 12 is 2 2 in base 5, as well as the count for 12.
The effect of supplying implied leading 0s is demonstrated by
2: 1 1 0 0
3: 1 1 0
4: 3 0
5: 2 2
6: 2 0
12: 5
Although 1 1 0 0 in base 2 is not a palindrome, it becomes one if we supply two leading 0s to match the trailing 0s.
0 0 0 0 0 1 0 1 1 1 2 0 1
Counts of the number of bases B
1 < B < N-1
in which N is a palindrome for N between 0 and 12.
0 0 0 1 1 2 1 2 2 2 3 1 2
Counts of the number of bases B
1 < B < N
in which N is a palindrome for N between 0 and 12. Changing BASEDELTA from the default of -1 allows base N-1, and, since N is 1 1 base N-1 for N greater than 2, the counts for those terms increase by 1. Setting BASEDELTA to 1 would allow base N to be considered, but N is 1 0 in base N, and that is not a palindrome (unless we set LEADING0S to 1 as well), so there is no effect on the counts. Above 1, BASEDELTA adds bases in which N is a ``single digit'' palindrome, N, as long as N+BASEDELTA-1 is 2 or more, and therefore a valid base. We don't regard the effects of increased BASEDELTA on the underlying sequence as particularly interesting.
0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 2, 0, 1
Use a comma and a blank to separate terms in the sequence.
0, 0, 0, 0, 1, 1, 2, 1, 3, 2, 4, 0, 5
Allowing leading 0s when counting palindromes can never reduce counts, of course, but it obviously increases the counts for some terms.
0 1 2 3 4 6 11 19 47 53 79 103 137 139 149 163 167 179
After 6, all the terms are prime numbers. This is no accident. Composite numbers greater than 6 have a base in which they appear as a palindrome.
Consider, first, perfect squares, so N is F**2
N = F**2
= F * F
= (F-1 + 1) * (F-1 + 1)
= (F-1)**2 + 2*(F-1) + 1
so N would be 1 2 1 base F-1 as long as F is greater than 3 (so 2 is a ``digit'' base F-1). This means all perfect squares greater than 9 can be represented as a palindrome, and 9 itself is 1 0 0 1 base 2, so all perfect squares greater than 6 have a palindromic base.
Consider next composite numbers N whose least prime factor is P, so N is P*F. We have already disposed of the case where P is equal to F, so we can assume P is strictly less than F. Can P equal F-1? Yes, but then P or F must be even, and P is the least prime factor, so P must be 2 and F must be 3, and we only care about N greater than 6. So we can assume F-1 is strictly greater than P. So
N = P * F
= P * (F-1) + P
so N is P P base F-1. It follows that all composite numbers greater than 6 have a palindromic base.
Incidentally, LEADING0S has no effect on the primes reported by HASNOPALINS. If P has no palindromic base when LEADING0S is on, then it surely had no palindromic base without LEADING0S, so LEADING0S cannot add new primes. And any new base B (less than N) allowed by LEADING0S must have a palindrome ending in 0, which means N is a multiple of B, hence, not a prime. So LEADING0S cannot remove any primes.