mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2022-02-13, 10:14   #1
hunson
 
Feb 2020
Germany

2·52 Posts
Default 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
hunson is offline   Reply With Quote
Old 2022-02-13, 12:43   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

32·52·7 Posts
Default

Quote:
Originally Posted by hunson View Post
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
R. Gerbicz is offline   Reply With Quote
Old 2022-02-13, 14:42   #3
hunson
 
Feb 2020
Germany

2×52 Posts
Default

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
hunson is offline   Reply With Quote
Old 2022-02-13, 15:15   #4
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

10111010101102 Posts
Default

Quote:
Originally Posted by hunson View Post
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.
<snip>
Code:
10^n+777*10^(n-3)+1
<snip>
<snip>
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
Dr Sardonicus is offline   Reply With Quote
Old 2022-02-13, 21:56   #5
sweety439
 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

72×73 Posts
Default

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
sweety439 is offline   Reply With Quote
Old 2022-02-14, 00:05   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

993710 Posts
Default

Quote:
Originally Posted by sweety439 View Post
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".
Batalov is offline   Reply With Quote
Old 2022-02-14, 20:24   #7
hunson
 
Feb 2020
Germany

2×52 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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.
hunson is offline   Reply With Quote
Old 2022-02-20, 16:54   #8
hunson
 
Feb 2020
Germany

2×52 Posts
Default

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
hunson is offline   Reply With Quote
Old 2022-02-20, 17:46   #9
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

10111010101102 Posts
Default

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.
Dr Sardonicus is offline   Reply With Quote
Old 2022-02-23, 19:26   #10
hunson
 
Feb 2020
Germany

2·52 Posts
Default

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

Thread Tools


Similar Threads
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

All times are UTC. The time now is 09:54.


Mon Sep 26 09:54:07 UTC 2022 up 39 days, 7:22, 0 users, load averages: 1.33, 1.52, 1.47

Powered by vBulletin® Version 3.8.11
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.

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