mersenneforum.org Palindrome prime number of digits is always odd (except 11, and this is true in any base)
 Register FAQ Search Today's Posts Mark Forums Read

 2021-09-17, 17:06 #1 bur     Aug 2020 79*6581e-4;3*2539e-3 2·199 Posts Palindrome prime number of digits is always odd (except 11, and this is true in any base) 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: Code: 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?
 2021-09-17, 17:21 #2 Viliam Furik     "Viliam Furík" Jul 2018 Martin, Slovakia 23·5·17 Posts 10^1 has 2 digits, thus 10^(n) has n+1 digits
2021-09-17, 17:32   #3
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

2,141 Posts

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

In Pari-gp
Quote:
 p = 10^1234567 - 20342924302 * 10^617278 - 1; print(p) length(Str(p))
Code:
%4 = 1234567
There is a clever explanation in the Other-Primes thread why the decimal digit count can not be an even number.

2021-09-17, 17:41   #4
Viliam Furik

"Viliam Furík"
Jul 2018
Martin, Slovakia

23·5·17 Posts

Quote:
 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.

2021-09-17, 17:49   #5
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

956210 Posts

Quote:
 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.

 2021-09-17, 21:37 #6 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2,141 Posts 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.
 2021-09-21, 19:31 #7 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·7·683 Posts 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). $\qed$ 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).
 2021-09-21, 19:46 #8 paulunderwood     Sep 2002 Database er0rr 3,853 Posts Mod 11 is used to get the check digit of ISBNs https://en.wikipedia.org/wiki/Intern...r#Check_digits
 2021-09-21, 19:53 #9 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2×7×683 Posts Credit (and SIM-) card numbers have the similar (not the same) protection from typos and transpositions.
2021-09-21, 20:25   #10
Dr Sardonicus

Feb 2017
Nowhere

497110 Posts

Quote:
 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). $\qed$ 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.* * 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.
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

$N\;=\;\sum_{j=0}^{k-1}d_{j}$$b^{2k-2j-1}\;+\;1$$$

where the dj 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 d0 is nonzero because it is also the lead digit.

For k > 1, b2k - 1 + 1 > b + 1, so N/(b + 1) > 1.

Last fiddled with by Dr Sardonicus on 2021-09-21 at 20:27 Reason: xingif optsy

 2021-09-22, 19:06 #11 bur     Aug 2020 79*6581e-4;3*2539e-3 2×199 Posts 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post ONeil Information & Answers 2 2020-12-13 13:35 sweety439 sweety439 73 2019-08-02 10:18 MathDoggy Miscellaneous Math 37 2019-04-15 23:42 a1call Miscellaneous Math 179 2015-11-12 14:59 jasong Conjectures 'R Us 36 2010-08-03 06:25

All times are UTC. The time now is 15:08.

Sun Oct 17 15:08:27 UTC 2021 up 86 days, 9:37, 1 user, load averages: 1.68, 1.20, 1.10