20220213, 10:14  #1 
Feb 2020
Germany
2·5^{2} 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^(nlen(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^(n3)+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 [...] I further tested other factors than 777 and found similar periodic patterns (e.g. 10^n+8787878*10^(n7)+1 with pattern 4,8,4,8, prime factor 7, indices are congruent {3,5} % 6 and 10^n+642939246*10^(n9)+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 
20220213, 12:43  #2  
"Robert Gerbicz"
Oct 2005
Hungary
11^{2}×13 Posts 
Quote:
Code:
(13:38) gp > f(n)=10^n+777*10^(n3)+1 %3 = (n)>10^n+777*10^(n3)+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 

20220213, 14:42  #3 
Feb 2020
Germany
2×5^{2} Posts 
my bad. That was a typo, sorry. I meant to write: 10^n+777*10^((n3)/2)+1, for n > 4 (one more than the length of the 'middle' factor)
Last fiddled with by hunson on 20220213 at 14:45 
20220213, 15:15  #4  
Feb 2017
Nowhere
23×257 Posts 
Quote:
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^(k1))^2 + 777*10^(k1) + 1, or N = 100*x^2 + 777*x + 1, with x = 10^(k1). 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
EDIT: As an exercise, I wrote a clunky PariGP 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 20220214 at 17:04 Reason: As indicated 

20220213, 21:56  #5 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
6771_{8} 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 20220213 at 21:58 
20220214, 00:05  #6  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2·3·13·127 Posts 
Quote:


20220214, 20:24  #7  
Feb 2020
Germany
32_{16} Posts 
Quote:
Nice to see that the professionals getting something out of these noob questions too :) Thanks for your input, I will try to understand your explanation. 

20220220, 16:54  #8 
Feb 2020
Germany
2·5^{2} 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 
20220220, 17:46  #9 
Feb 2017
Nowhere
23×257 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. 
20220223, 19:26  #10 
Feb 2020
Germany
50_{10} 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 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
PRP tests on known composite numbers  drkirkby  PrimeNet  7  20210225 10:21 
Always composite numbers?  sweety439  sweety439  4  20200215 07:55 
Condition on composite numbers easily factored  baih  Factoring  16  20190929 15:48 
Palindrome numbers  fetofs  Puzzles  4  20060310 15:56 
Factoring highly composite Mersenne numbers  philmoore  Factoring  21  20041118 20:00 