Palindrome prime number of digits is always odd (except 11, and this is true in any base)

[bur]

This newly discovered largest known Palindrome prime was reported by Propper & Batalov:

10^1234567 - 20342924302 · 10^617278 - 1

It's shown as having 1234568 decimal digits which I thought was odd. It should be a nice 1234567 decimal digits, or not? I noticed PARI apparently has a rounding problem:

gp > log(10^73-323*10^35-1)/log(10)
%2362 = 72.999999999999999999999999999999999998
gp > log(10^75-323*10^36-1)/log(10)
%2351 = 75.000000000000000000000000000000000000

The latter number definitely has 75 digits (I counted). Did a similar problem happen at the Prime Pages? Or is it really 1234568 digits for some reason?

[Viliam Furik]

10^1 has 2 digits, thus 10^(n) has n+1 digits

[a1call]

I learned this from ScienceMan. I wonder what ever happned to him.

In Pari-gp

p = 10^1234567 - 20342924302 * 10^617278 - 1;
print(p)
length(Str(p))

%4 = 1234567

There is a clever explanation in the Other-Primes thread why the decimal digit count can not be an even number.

[Viliam Furik]

Originally Posted by Viliam Furik

10^1 has 2 digits, thus 10^(n) has n+1 digits

Oh, never mind. I didn't realize the subtracting decreases the number of digits.

[Batalov]

Originally Posted by Viliam Furik

10^1 has 2 digits, thus 10^(n) has n+1 digits

...but 10^(n)-epsilon has n digits

And of course, the only palindrome prime that has an even number of digits (in any base, actually) is "11"! (And even "11" can be composite; then none.)
All others are divisible by "11" (in that base).

So of course this number has 1234567 decimal digits. The server-calculated number is in error.

The path of least resistance that I did suggest to Prof.Caldwell is - just run pfgw -od input |awk '{print length($2)}' .
(His server runs pfgw for verification on most inputs except most arcane ones.)
There is no use making an ad hoc "yet another" calculator with ~million digit precision, when one already has Pari/GP and pfgw.

[a1call]

Apologies for spamming the mods. I think I finally understand that in any other base only 11 (in that base) can be an even-numbered-digits-counted prime. Generally any prime p will equal 11 in base p-1 and any other palindromes with even digits count will be divisible by p.
No there is no fire, it's just the smoke coming out my ears.

[Batalov]

I've actually been asked, so I could repost here exactly why every "even-length" palindrome is divisible by "11" (think decimal, but it is true for any base b).
We could simply say that order of mod(b,b+1) is 2, and residues are -1,+1. (and everything follows)

In other words:

First, quick Lemma: 10^n = { +1 (mod 11) if n is even | -1 (mod 11) if n is odd }.
Proof:
For even n, 10^2k = 100^k = +1 (mod 11), because 100 = 1 (mod 11). And more generally for any base b, b^2k = (b^2)^k = 1^k = 1 (mod b+1), because b^2 -1 = 0 (mod b+1).
For odd n, 10^(2k+1) = 100^k * 10 = 1 * (-1) = -1 (mod 11).

Now this leads to the (known to some from school) divisibility-by-11 criterion:
You sum up all digits jumping by 2, let's call it A. (In other words all odd-positioned digits.)
Then you add up all even-positioned digits, let's call it B.
Now, if A-B is divisible by 11, then the whole number is divisible by 11.*

We used to have bus tickets (in the USSR), with six-digit numbers on them, obtained from a machine (that had a rubber belt so that others could see that you really dropped your 5 cents there), and so, we added those digits and called those where A==B lucky tickets. So those were incidentally divisible by 11.

So if you do the above summation for a palindrome with even length, it will be surely lucky (because they will be the same set of digits, because of palindrome-ness). So it will be divisible by 11.

____
* note that every one knows the divisibility-by-3 and 9: "the digital root". This is only one step up from that.
One step below that in simplicity is divisibility-by-2 and 5.
Two steps up is divisibility-by-7 and 13. (for it, you would split the long number in 3-digit groups and sum them up in your head as groups A and B, then the same as with 11. Why? because 1001 is divisible by 7 and 13 (and 11, again; so you can do all three in one weird sweep).

[paulunderwood]

Mod 11 is used to get the check digit of ISBNs https://en.wikipedia.org/wiki/Intern...r#Check_digits

[Batalov]

Credit (and SIM-) card numbers have the similar (not the same) protection from typos and transpositions.

[Dr Sardonicus]

Originally Posted by Batalov

I've actually been asked, so I could repost here exactly why every "even-length" palindrome is divisible by "11" (think decimal, but it is true for any base b).
We could simply say that order of mod(b,b+1) is 2, and residues are -1,+1. (and everything follows)

In other words:

First, quick Lemma: 10^n = { +1 (mod 11) if n is even | -1 (mod 11) if n is odd }.
Proof:
For even n, 10^2k = 100^k = +1 (mod 11), because 100 = 1 (mod 11). And more generally for any base b, b^2k = (b^2)^k = 1^k = 1 (mod b+1), because b^2 -1 = 0 (mod b+1).
For odd n, 10^(2k+1) = 100^k * 10 = 1 * (-1) = -1 (mod 11).

Now this leads to the (known to some from school) divisibility-by-11 criterion:
You sum up all digits jumping by 2, let's call it A. (In other words all odd positioned digits.)
Then you add up all even numbered digits, let's call it B.
Now, if A-B is divisible by 11, then the whole number is divisible by 11.*
<snip>
* note that every one knows the divisibility-by-3 and 9: "the digital root". This is only one step up from that.
One step below that in simplicity is divisibility-by-2 and 5.
<snip>

That is a nice way of looking at it. I actually test for divisibility by 11 in my head this way sometimes.

An alternate approach is as follows: To any integer base b >1, a base-b palindrome N with 2k digits may be written



where the d_j are the base-b digits. Since the exponents of b in the sum are all odd, the terms in parentheses are all divisible by b + 1. The digit d₀ is nonzero because it is also the lead digit.

For k > 1, b^{2k - 1} + 1 > b + 1, so N/(b + 1) > 1.

[bur]

The length has been corrected, now I can sleep peacefully.


Thanks for the explanations about the necessity of an odd number of digits. It's always fascinating how much can be deduced about numbers by using modulus. It never played a big role at school or my two math courses at university.