 mersenneforum.org Pattern in composite palindrome numbers
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read 2022-02-13, 10:14 #1 hunson   Feb 2020 Germany 1100102 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

32×52×7 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 2×52 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

175616 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.
Your code does not match your formula,and your formula isn't quite right.

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

19·523 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

1100102 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 :)
Thanks for your input, I will try to understand your explanation.   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 10111010101102 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  Thread Tools Show Printable Version Email this Page 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 10:01.

Mon Sep 26 10:01:17 UTC 2022 up 39 days, 7:29, 0 users, load averages: 1.36, 1.32, 1.38

Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔