mersenneforum.org Pattern in composite palindrome numbers
 Register FAQ Search Today's Posts Mark Forums Read

 2022-02-13, 10:14 #1 hunson   Feb 2020 Germany 2·52 Posts Pattern in composite palindrome numbers Hi, currently I am interested in writing small programs for prime number generation for fun. My newest project is a program to generate candidates for palindrome prime numbers of the form 10^n+a*10^(n-len(a)/2)+1. The candidates were checked via trial division for small factors and potential primes finally written to an output file. While testing the program I noticed a pattern in the list of eliminated candidates. E.g for Code: 10^n+777*10^(n-3)+1 n = 100002 eliminated, p = 42283 n = 100004 eliminated, p = 13 n = 100006 eliminated, p = 1453 n = 100008 eliminated, p = 29 n = 100010 eliminated, p = 17 n = 100012 eliminated, p = 13 n = 100014 eliminated, p = 283 n = 100016 eliminated, p = 13 n = 100018 eliminated, p = 47 n = 100022 eliminated, p = 17 n = 100024 eliminated, p = 13 n = 100026 eliminated, p = 2593 n = 100028 eliminated, p = 13 n = 100030 eliminated, p = 23 n = 100032 eliminated, p = 113 n = 100036 eliminated, p = 13 n = 100038 eliminated, p = 23 n = 100040 eliminated, p = 13 n = 100042 eliminated, p = 17 n = 100048 eliminated, p = 13 n = 100050 eliminated, p = 89 n = 100052 eliminated, p = 13 [...] Every 4th and 8th number is mod 13 = 0 (100004, 100012, 100016, ...). Mathematics is not my strong side, so I did not find the reason for this. My approach was a bit more simple. After indexing the numbers starting with 0, I got a sequence of indices where the corresponding number is mod 13 = 0 (0, 2, 6, 8, 12, 14, 18,...). A quick check in the OEIS showed that the indices are congruent {0,2} % 6 (https://oeis.org/A047238). I further tested other factors than 777 and found similar periodic patterns (e.g. 10^n+8787878*10^(n-7)+1 with pattern 4,8,4,8, prime factor 7, indices are congruent {3,5} % 6 and 10^n+642939246*10^(n-9)+1 with pattern 12,24,12,24,12, prime factor 19, indices are congruent {1,7} % 18). Although this is a nice result and I could optimize the generator for these particular palindrome forms and avoid some exponentiation. I am curious why these patterns occur in the first place. I am certain that the 'middle' factor 777,8787878, etc. dictates the prime factor (e.g. 13 from the example above) and period. An explanation or hint in the right direction is very much appreciated. hunson
2022-02-13, 12:43   #2
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

30478 Posts

Quote:
 Originally Posted by hunson I am interested in writing small programs for prime number generation for fun. My newest project is a program to generate candidates for palindrome prime numbers of the form 10^n+a*10^(n-len(a)/2)+1. 10^n+777*10^(n-3)+1 n = 100002 eliminated, p = 42283 ...
Do you know that for a=777 it is giving palindrome number only if n=4 ? (Generalize it for any "a" number) Inspect the numbers:
Code:
(13:38) gp > f(n)=10^n+777*10^(n-3)+1
%3 = (n)->10^n+777*10^(n-3)+1
(13:38) gp > for(n=0,10,print(n" "f(n)))
0 2777/1000
1 1877/100
2 1787/10
3 1778
4 17771
5 177701
6 1777001
7 17770001
8 177700001
9 1777000001
10 17770000001

 2022-02-13, 14:42 #3 hunson   Feb 2020 Germany 628 Posts my bad. That was a typo, sorry. I meant to write: 10^n+777*10^((n-3)/2)+1, for n > 4 (one more than the length of the 'middle' factor) Last fiddled with by hunson on 2022-02-13 at 14:45
2022-02-13, 15:15   #4
Dr Sardonicus

Feb 2017
Nowhere

2×3×997 Posts

Quote:
 Originally Posted by hunson Hi, currently I am interested in writing small programs for prime number generation for fun. My newest project is a program to generate candidates for palindrome prime numbers of the form 10^n+a*10^(n-len(a)/2)+1. Code: 10^n+777*10^(n-3)+1  An explanation or hint in the right direction is very much appreciated.

For the sort of palindromes you want, the formula would be

N = 10^(2*k) + a*10^(k - (len(a) - 1)/2) + 1

where len(a) is odd, and 10^(2*k - 1) > a.

For your example 777, we have

N = 10^(2*k) + 777*10^(k - 1) + 1 with k > 1.

We can write this as

N = 100*(10^(k-1))^2 + 777*10^(k-1) + 1, or

N = 100*x^2 + 777*x + 1, with x = 10^(k-1).

The quadratic in x has discriminant D = 777^2 - 4*100 = 757*797. [This idea can be adapted to any a]

In order that N be divisible by p for some k, it is necessary that
1. D is a quadratic residue (mod p), and
2. if x - r is a factor of the quadratic in x (mod p), then r be expressible as a power of 10 (mod p).
There are a bunch of additional details, but, alas, I am to lazy to work them out.

EDIT: As an exercise, I wrote a clunky Pari-GP script to work out the congruence classes of k for which

10^(2*k) + 777*10^(k - 1) + 1

is divisible by the prime p, for all possible p < 500.

p = 13 k == 2 or 4 (mod 6)
p = 17 k == 5 or 11 (mod 16)
p = 23 k == 9 or 13 (mod 22)
p = 29 k == 4 or 24 (mod 28)
p = 31 k == 4 or 11 (mod 15)
p = 47 k == 7 or 39 (mod 46)
p = 61 k == 19 or 41 (mod 60)
p = 89 k == 3 or 41 (mod 44)
p = 97 k == 46 or 50 (mod 96)
p = 113 k == 48 or 64 (mod 112)
p = 131 k == 56 or 74 (mod 130)
p = 149 k == 62 or 86 (mod 148)
p = 181 k == 55 or 125 (mod 180)
p = 233 k == 91 or 141 (mod 232)
p = 269 k == 62 or 206 (mod 268)
p = 283 k == 48 or 93 (mod 141)
p = 347 k == 22 or 151 (mod 173)
p = 349 k == 6 or 110 (mod 116)
p = 367 k == 18 or 348 (mod 366)
p = 401 k == 49 or 151 (mod 200)
p = 419 k == 129 or 289 (mod 418)
p = 439 k == 1 or 218 (mod 219)
p = 461 k == 189 or 271 (mod 460)
p = 467 k == 109 or 124 (mod 233)
p = 491 k == 69 or 421 (mod 490)
p = 499 k == 96 or 402 (mod 498)

Last fiddled with by Dr Sardonicus on 2022-02-14 at 17:04 Reason: As indicated

 2022-02-13, 21:56 #5 sweety439   "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 72·73 Posts Some palindrome number forms have composite number pattern, e.g. 9444...4449, all numbers of this form is divisible by at least one of 3, 7, 11, or 13. A more complex example is 333...3332333...333 See http://www.worldofnumbers.com/deplat.htm and http://www.worldofnumbers.com/wing.htm I have collected many examples, this post also has examples in other bases. Last fiddled with by sweety439 on 2022-02-13 at 21:58
2022-02-14, 00:05   #6
Batalov

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

26D316 Posts

Quote:
 Originally Posted by sweety439 I have collected many examples, this post also has examples in other bases.
It is relatively easy to repeat other people's results and call them "yours".

2022-02-14, 20:24   #7
hunson

Feb 2020
Germany

628 Posts

Quote:
 Originally Posted by Dr Sardonicus EDIT: As an exercise, I wrote a clunky Pari-GP script to work out the congruence classes of k for which 10^(2*k) + 777*10^(k - 1) + 1 is divisible by the prime p, for all possible p < 500.

Nice to see that the professionals getting something out of these noob questions too :)

 2022-02-20, 16:54 #8 hunson   Feb 2020 Germany 2·52 Posts I tried to understand the math behind Dr Sardonicus's post and came the to "Chinese Remainder Theorem" but that's about it. I fail to see the correlation between the equation 10^(2*k) + 777*10^(k - 1) + 1 and the theorem not to speak of solving the congruence classes. Could someone please explain how to calculate a congruence with p = 13 as an example for 10^(2*k) + 777*10^(k - 1) + 1? hunson
 2022-02-20, 17:46 #9 Dr Sardonicus     Feb 2017 Nowhere 2·3·997 Posts A convenient listing of links to everything you need to know is in this post. Basic Number Theory 8: equiv. relations and Fermat's little theorem, and Basic Number Theory 15: Lagrange's Theorem, cyclic groups and modular arithmetic (especially Theorem 90 therein) are especially pertinent to the present instance.
 2022-02-23, 19:26 #10 hunson   Feb 2020 Germany 2·52 Posts Thanks for the links to the literature. I looked at the chapters you mentioned and decided that I will not peruse this project any further. I am not a mathematician or very skilled in math, I do not understand very much of it. Thanks anyways. hunson

 Similar Threads Thread Thread Starter Forum Replies Last Post drkirkby PrimeNet 7 2021-02-25 10:21 sweety439 sweety439 4 2020-02-15 07:55 baih Factoring 16 2019-09-29 15:48 fetofs Puzzles 4 2006-03-10 15:56 philmoore Factoring 21 2004-11-18 20:00

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

Thu Sep 29 08:38:53 UTC 2022 up 42 days, 6:07, 0 users, load averages: 0.81, 0.88, 0.93