mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > And now for something completely different

Reply
 
Thread Tools
Old 2021-09-17, 17:06   #1
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

401 Posts
Default 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?
bur is offline   Reply With Quote
Old 2021-09-17, 17:21   #2
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

2·11·31 Posts
Default

10^1 has 2 digits, thus 10^(n) has n+1 digits
Viliam Furik is offline   Reply With Quote
Old 2021-09-17, 17:32   #3
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

1000011010002 Posts
Default

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.
a1call is online now   Reply With Quote
Old 2021-09-17, 17:41   #4
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

2AA16 Posts
Default

Quote:
Originally Posted by Viliam Furik View Post
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.
Viliam Furik is offline   Reply With Quote
Old 2021-09-17, 17:49   #5
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

17·563 Posts
Default

Quote:
Originally Posted by Viliam Furik View Post
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.
Batalov is offline   Reply With Quote
Old 2021-09-17, 21:37   #6
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

86816 Posts
Default

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.
a1call is online now   Reply With Quote
Old 2021-09-21, 19:31   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

17×563 Posts
Lightbulb

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).
Batalov is offline   Reply With Quote
Old 2021-09-21, 19:46   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

53×73 Posts
Default

Mod 11 is used to get the check digit of ISBNs https://en.wikipedia.org/wiki/Intern...r#Check_digits
paulunderwood is offline   Reply With Quote
Old 2021-09-21, 19:53   #9
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

17×563 Posts
Default

Credit (and SIM-) card numbers have the similar (not the same) protection from typos and transpositions.
Batalov is offline   Reply With Quote
Old 2021-09-21, 20:25   #10
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·11·227 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.*
<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

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
Dr Sardonicus is offline   Reply With Quote
Old 2021-09-22, 19:06   #11
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

401 Posts
Default

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.
bur is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
How to determine if a large number is prime? Is this True? ONeil Information & Answers 2 2020-12-13 13:35
Add repeated digits after a number until it is prime sweety439 sweety439 73 2019-08-02 10:18
I Think The Twin Prime Conjecture Is True MathDoggy Miscellaneous Math 37 2019-04-15 23:42
The "one billion minus 999,994,000" digits prime number a1call Miscellaneous Math 179 2015-11-12 14:59
Base-6 speed for prime testing vs. base-2 jasong Conjectures 'R Us 36 2010-08-03 06:25

All times are UTC. The time now is 00:59.


Sun Oct 24 00:59:39 UTC 2021 up 92 days, 19:28, 0 users, load averages: 1.36, 1.21, 1.15

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.