From: John P. Linderman <jpl.jpl(AT)gmail.com>
Feb 28 2008

palin.pl [included in this file a135549.txt]
    is the perl script that is used to generate the sequences,
    and also to generate palin.html.  That can be done by running
	pod2html palin.pl > palin.html
    if the documentation changes.

palin.html [now called a135549.html]
    is an HTML description of palin.pl and the options it
    recognizes.  There's a section with a bit of analysis.

------- start of palin.pl -----------------------

#!/usr/bin/perl -w

use strict;

my $HasNoPalins = 0;	# Set to 1 to report only N having no palindromic bases
my $StartAt = 0;	# Least N to consider
my $StopAfter;		# Greatest N to consider.  See STOPAFTER below.
my $Leading0s = 0;	# Set to 1 to allow leading 0s
my $BaseDelta = -1;	# Only consider bases strictly less than N+BaseDelta
my $Verbose = 0;	# Set to 1 for extra detail
my $Sep = ' ';		# What separates terms.  "\n" or ", " might apply

$HasNoPalins = $ENV{HASNOPALINS} if (exists($ENV{HASNOPALINS}));
$StartAt = $ENV{STARTAT} if (exists($ENV{STARTAT}));
$StopAfter = exists($ENV{STOPAFTER}) ? $ENV{STOPAFTER} :
			$HasNoPalins ? 1000 : 100;
$Leading0s = $ENV{LEADING0S} if (exists($ENV{LEADING0S}));
$BaseDelta = $ENV{BASEDELTA}+0 if (exists($ENV{BASEDELTA}));
$Verbose = $ENV{VERBOSE} if (exists($ENV{VERBOSE}));
$Sep = $ENV{SEP} if (exists($ENV{SEP}));

$Verbose = 0 if ($HasNoPalins);	# detail is too ugly

# N as a array of base B numbers.  B > 1
sub NbaseB {
    my $N = shift;
    my $B = shift;
    my @a = ();

    while ($N > 0) {
	push(@a, $N % $B);
	$N = int($N/$B);
    }
    return reverse @a;
}


# Is n a palindrome in base b?  1 if yes, 0 if no
sub is_palin {
    my ($n, $b) = @_;
    my @p = NbaseB($n, $b);
    my ($i, $j);

    if ($Leading0s) {
	pop(@p) while (@p && ($p[-1] == 0));
    }
    for ($i = 0, $j = $#p; $i < $j; ++$i, --$j) {
	return 0 unless ($p[$i] == $p[$j]);
    }
    return 1;
}


sub main {
    my ($i, $j, $p, $t, $topbase);
    my $sep = '';

    for ($i = $StartAt; $i <= $StopAfter; ++$i) {
	$p = 0;
	$topbase = $i + $BaseDelta;
	for ($j = 2; $j < $topbase; ++$j) {
	    $p += $t = is_palin($i, $j);
	    if ($Verbose && $t) {
		print($j, ": ", join(" ", NbaseB($i, $j)), "\n");
	    }
	}
	if ($HasNoPalins) {
	    if ($p == 0) {
		print($sep, $i);
		$sep = $Sep;
	    }
	} elsif ($Verbose) {
	    print($i, ": ", $p, "\n\n");
	} else {
	    print($sep, $p);
	    $sep = $Sep;
	}
    }
    print("\n");
}
main();

=head2 In How Many Bases is B<N> a Palindrome?

This script generates sequences relating to the question
of the number of bases in which a positive integer B<N> is a palindrome.
B<N> will be a palindrome when expressed in unary,
but B<1> is not a legitimate base, so we are concerned
only with integer bases greater than 1.
B<N> will be a "single digit" palindrome in any base
greater than B<N>,
so we will not consider bases greater than B<N>.

Base B<N> and base B<N>-1 are special cases.
When they are large enough to be legitimate bases,
B<N> is B<1 0> in base B<N>, and B<1 1> in base B<N>-1.
The latter is always a palindrome,
and the former is a palindrome if (and only if) we
allow leading B<0>s, viewing it as B<0 1 0>.
We therefore default to considering only bases B<B>

  1 < B < N-1

when we count the number of bases in which B<N> is a palindrome.
The effect of including bases B<N>-1 or B<N> is simply to increase
the count by a constant amount where they are legitimate bases.

=head2 Options

There are several variables that influence how palindromes are counted
and reported.  They can be set through the use of I<environment
variables>, and it is the names of those environment variables
that we will use in describing the effects.

=head3 HASNOPALINS

By default, we report, for each B<N>, the number of bases B<B>

  1 < B < N-1

in which B<N> is a palindrome.  By setting B<HASNOPALINS=1>,
we report, instead, those B<N> for which the count is B<0>.

The reader might enjoy proving that for B<N> greater than B<6>,
only prime numbers (but not all prime numbers) are reported.
See L</"HASNOPALINS and Composite Numbers">
for a discussion.

=head3 STARTAT

We default to starting with B<N> at B<0>.
But, for B<N> less than B<3>

    1 < B < N-1

includes no bases, so the corresponding count will always be 0.
You can change the initial value of B<N> using B<STARTAT>.
For example (assuming, as we will throughout, that you can
set environment variables on the command line,
and that this script is called B<palin.pl>)

    STARTAT=3 palin.pl

will start at B<N>=B<3>.

=head3 STOPAFTER

By default, the last value of B<N> we consider is B<100>,
B<1000> when B<HASNOPALINS> is B<1>.
If B<STOPAFTER> is defined, it determines the last value of B<N>
to be considered.

=head3 LEADING0S

By default, we do not count bases in which it would be
necessary to supply one or more leading B<0>s to make B<N>
a palindrome.  If B<LEADING0S> is B<1>, we I<will> count such bases.

=head3 VERBOSE

By setting B<VERBOSE=1>, additional information may be printed.
This has no effect when B<HASNOPALINS> is B<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 B<N> is regarded as a palindrome,
as well as B<N> and the count.

=head3 SEP

The counts in the default report are separated by blanks.
You can assign the string you want to use to separate
the counts to B<SEP>.

=head2 BASEDELTA

We default to allowing only bases B<B>

    1 < B < N-1

when counting bases where B<N> is regarded as a palindrome.
The upper limit is determined by adding the B<BASEDELTA> value,
which defaults to B<-1>, to B<N>.  You can expand or contract
the range by modifying the B<BASEDELTA> value.
Expanding it, by making it greater than B<-1>,
has no interesting impact on the counts,
it merely increases them by a constant value
(and any expansion would render the B<HASNOPALINS> report
particularly uninteresting).

=head2 Examples

There follow several examples of using the options discussed above.
Outputs are shown immediately following the commands.

=head3 B<STARTAT=12 STOPAFTER=12 palin.pl>

    1

We use B<STARTAT> and B<STOPAFTER> to limit B<N> to a single value,
B<12>.  All that is reported is B<1>, the number of bases

    1 < B < 12-1

in which B<12> is a palindrome.  If you are interested in more
than the count, you can do

=head3 B<STARTAT=12 STOPAFTER=12 VERBOSE=1 palin.pl>

    5: 2 2
    12: 1

and you now see that B<12> is B<2 2> in base B<5>,
as well as the count for B<12>.

The effect of supplying implied leading B<0>s
is demonstrated by

=head3 B<STARTAT=12 STOPAFTER=12 VERBOSE=1 LEADING0S=1 palin.pl>

    2: 1 1 0 0
    3: 1 1 0
    4: 3 0
    5: 2 2
    6: 2 0
    12: 5

Although B<1 1 0 0> in base B<2> is not a palindrome,
it becomes one if we supply two leading B<0>s
to match the trailing B<0>s.

=head3 B<STOPAFTER=12 palin.pl>

    0 0 0 0 0 1 0 1 1 1 2 0 1

Counts of the number of bases B<B>

    1 < B < N-1

in which B<N> is a palindrome for B<N> between B<0> and B<12>.

=head3 B<STOPAFTER=12 BASEDELTA=0 palin.pl>

    0 0 0 1 1 2 1 2 2 2 3 1 2

Counts of the number of bases B<B>

    1 < B < N

in which B<N> is a palindrome for B<N> between B<0> and B<12>.
Changing B<BASEDELTA> from the default of B<-1> allows base B<N>-1,
and, since B<N> is B<1 1> base B<N>-1 for B<N> greater than B<2>,
the counts for those terms increase by B<1>.
Setting B<BASEDELTA> to B<1> would allow base B<N> to be
considered, but B<N> is B<1 0> in base B<N>,
and that is not a palindrome
(unless we set B<LEADING0S> to B<1> as well),
so there is no effect on the counts.
Above B<1>, B<BASEDELTA> adds bases in which B<N>
is a "single digit" palindrome, B<N>,
as long as B<N>+B<BASEDELTA>-B<1> is B<2> or more,
and therefore a valid base.
We don't regard the effects of increased B<BASEDELTA> on the
underlying sequence as particularly interesting.

=head3 B<STOPAFTER=12 SEP=', ' palin.pl>

    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.

=head3 B<STOPAFTER=12 SEP=', ' LEADING0S=1 palin.pl>

    0, 0, 0, 0, 1, 1, 2, 1, 3, 2, 4, 0, 5

Allowing leading B<0>s when counting palindromes
can never I<reduce> counts, of course,
but it obviously increases the counts for some terms.

=head2 HASNOPALINS and Composite Numbers

=head3 B<STOPAFTER=200 HASNOPALINS=1 palin.pl>

    0 1 2 3 4 6 11 19 47 53 79 103 137 139 149 163 167 179

After B<6>, all the terms are prime numbers.
This is no accident.
Composite numbers greater than B<6> have a base
in which they appear as a palindrome.

Consider, first, perfect squares, so B<N> is B<F>**B<2>

    N = F**2
      = F * F
      = (F-1 + 1) * (F-1 + 1)
      = (F-1)**2 + 2*(F-1) + 1

so B<N> would be B<1 2 1> base B<F>-1
as long as B<F> is greater than B<3>
(so B<2> is a "digit" base B<F>-1).
This means all perfect squares greater than B<9>
can be represented as a palindrome,
and B<9> itself is B<1 0 0 1> base B<2>,
so all perfect squares greater than B<6>
have a palindromic base.

Consider next composite numbers B<N> whose least prime factor is B<P>,
so B<N> is B<P>*B<F>.  We have already disposed of the case where
B<P> is equal to B<F>, so we can assume B<P> is strictly less than B<F>.
Can B<P> equal B<F>-1?  Yes, but then B<P> or B<F> must be even,
and B<P> is the I<least> prime factor, so B<P> must be B<2> and
B<F> must be B<3>, and we only care about B<N> greater than B<6>.
So we can assume B<F>-1 is strictly greater than B<P>.  So

    N = P * F
      = P * (F-1) + P

so B<N> is B<P P> base B<F>-1.
It follows that B<all> composite numbers greater than B<6>
have a palindromic base.

Incidentally, B<LEADING0S> has no effect on the primes
reported by B<HASNOPALINS>.  If B<P> has no palindromic base
when B<LEADING0S> is on, then it surely had no palindromic base
without B<LEADING0S>, so B<LEADING0S> cannot add new primes.
And any I<new> base B<B> (less than B<N>) allowed by B<LEADING0S>
must have a palindrome ending in B<0>,
which means B<N> is a multiple of B<B>,
hence, not a prime.  So B<LEADING0S> cannot remove any primes.