![]() |
![]() |
#1 |
Feb 2020
Germany
2·52 Posts |
![]()
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 [...] 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 |
![]() |
![]() |
![]() |
#2 | |
"Robert Gerbicz"
Oct 2005
Hungary
112×13 Posts |
![]() Quote:
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 |
|
![]() |
![]() |
![]() |
#3 |
Feb 2020
Germany
2×52 Posts |
![]() ![]() Last fiddled with by hunson on 2022-02-13 at 14:45 |
![]() |
![]() |
![]() |
#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^(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
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 |
|
![]() |
![]() |
![]() |
#5 |
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
67718 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 |
![]() |
![]() |
![]() |
#6 | |
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2·3·13·127 Posts |
![]() Quote:
|
|
![]() |
![]() |
![]() |
#7 | |
Feb 2020
Germany
3216 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. |
|
![]() |
![]() |
![]() |
#8 |
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 |
![]() |
![]() |
![]() |
#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. |
![]() |
![]() |
![]() |
#10 |
Feb 2020
Germany
5010 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 | |
![]() |
||||
Thread | Thread Starter | Forum | Replies | Last Post |
PRP tests on known composite numbers | drkirkby | PrimeNet | 7 | 2021-02-25 10:21 |
Always composite numbers? | sweety439 | sweety439 | 4 | 2020-02-15 07:55 |
Condition on composite numbers easily factored | baih | Factoring | 16 | 2019-09-29 15:48 |
Palindrome numbers | fetofs | Puzzles | 4 | 2006-03-10 15:56 |
Factoring highly composite Mersenne numbers | philmoore | Factoring | 21 | 2004-11-18 20:00 |