Problems & Puzzles:
Puzzles
Puzzle
557.-
H(m, a)
Emmanuel Vantieghem sent the following
nice puzzle:
Consider the function H(m,a), defined for all
natural numbers m, a by the rule to intertwine the digits of m by a.
For instance,
H(123,8) = 18283
H(468025,12) = 4126128120122125
H(402,402) = 440204022
. . .
Examples of primes m by
Emmanuel:
m = 13, H(m,j) is prime for j = 0, 1 (but
not for j = 2)
m = 1069, H(m,j) is prime for j = 0, 1, 2 (but not for j = 3)
m = 1979, H(m,j) is prime for j = 0, 1, 2, 3 (but not for j =
4)
m = 3049, is prime for j = 0, 1, 2, 3, 4 (but not for j =
5).
One more was found by C.
Rivera:
2381963 is a prime m &
gives primes for H(m,j), j=0 to 5, fails for j=6
Q1.Find a prime number m such
that H(m,0), H(m,1), H(m,2), ... , H(m,k) are all prime for k as big as
possible.
Q2. Another question is : Can H(m,m) be
prime ? Prove your answer.
Contributions came from Jan van Delden, Seiji Tomita, J-C Colin, J. K.
Andersen, Farideh Firoozbakht.
***
Jan van Delden wrote:
Q1:
The first sequences with H(a,j) prime, j=0..b, H(a,j+1)
composite:
a=1194307993 with b=6
a=1046197333 with b=7
Assume a has k digits and b has l digits and
a=a[k-1]...a[0].
H(a,b)=sum(a[i].10^(i.(l+1)),i=0..k-1)+10b.sum(10^(i.(l+1)),i=0..k-2)
rewrite to H(a,b)=T(a)+T(b) with
T(a)=sum(a[i].(10^(l+1))^i,i=0..k-1) and T(b)=10b.sum((10^(l+1))^i,i=0..k-2).
H(a,b) mod 3=(a+b.(k-1)) mod 3 (count powers of 10) With fixed a and
thus fixed T(a) mod 3, only two residue classes of b mod 3 are allowed.
So we should
have (k-1)=0 mod 3, or k=1 mod 3, to allow for b>1.
If b<10, l=1: T(b)=10b.(100^(k-1)-1)/99 with the small
divisors 2,3,5,7,13,37,. (and divisors of b).
so T(b)=0 mod q for all primes <10 and H(a,b) mod q=T(a) mod q. There
are q-1 free residues for each of these q to choose from.
If 10<=b<100, l=2 and we have: T(b)=10b.(1000^(k-1)-1)/999
T(b)=0 mod 11 iff k=odd. [T(b)=1 mod 11 iff k even (disallowed, because
there are no free residues left for T(a), remark: b=10 already uses the
11 residues,
so T(11)=0 mod 11 doesn't help].
We also have 13|T(b) for each k=1 mod 6 [the order of 10
mod 13=6].
So k=1 mod 6 suffices for b<17 (the b<10 are also divisors of T(b),
since 10^(3k)-1|10^(6k)-1) and 2,5 are divisors of 10).
We have 17|T(b) if k=1 mod 48 [the order of 10 mod
17=16]. Also we have for these k: 19|T(b).
So k=1 mod 48 suffices for b<23.
We have 23|T(b) if k=1 mod 528,
So k=1 mod 528 suffices for b<29.
Our k rapidly increases with solutions with increasing b.
One would need a clever sieve to reduce the number of "isprime"-checks.
Q2:
Split T(a) and T(b):
T(a)=sum(a[i].10^i.(10^((i.l)-1),i=0..k-1)+sum(a[i].10^i,i=0..k-1)
T(b)=10b.sum(10^i.(10^(i.l)-1),i=0..k-2)+10b.sum(10^i,i=0..k-2).
The second term of T(a) equals a, the second term of T(b)
equals 10b.(10^(k-1)-1)/9.
The sum of these is: (9(a-b)+b.(10^k-1))/9.
The other two terms are 0 mod 10^l-1. They are (at least) 0 mod
(10^l-1)/9.
And we see that H(a,b) = 0 mod (10^l-1)/9 if (sufficient,
not necessary):
- 9(a-b)=0 mod (10^l-1)/9 and
- l|k.
We have a=b, hence k=l so (10^k-1)/9, is a divisor of
H(a,a).
***
Seiji Tomita wrote:
Q2.
H(m,m) is always composite for all m > 1.
For example,let m=a1a2a3a4a5(5 digits).
H(m,m)=a1*10^(4+4*5)+a2*10^(3+3*5)+a3*10^(2+2*5)+a4*10^(1+1*5)+a5
+m*(10+10^7+10^13+10^19).
Coefficient of a1=a1*10^(4+4*5)+a1*10^4*(10+10^7+10^13+10^19).
=a1*10^4*(10+10^7+10^13+10^19+10^20).
Here,we take a prime p such that 10^5=1 mod p.
In this case(m=5 digits),p=41,271.
Then 10+10^7+10^13+10^19+10^20=(10^5-1)/9=0 mod p.
So,coefficient of a1=0 mod p.
Similarly, other coefficient of a2,a3,a4,a5=0 mod p.
Consequently,H(m,m) is composite.
In the same way,it is obvious that m=a1a2a3...an(n digits) is divisible by
p such that (10^n-1)/9=0 mod p.
Hence, H(m,m) is always composite for all m > 1.
By the way,(10^n-1)/9 is defined as repunit.
Numerical examples.
H(23459,23459)=2234593234594234595234599=0 mod 41.
(10^5-1)/9= (41)*(271)
H(1234577,1234577)=1123457721234577312345774123457751234577712345777=0
mod 239.
(10^7-1)/9= (239)*(4649)
H(1234567890123456817,1234567890123456817)=0 mod
1111111111111111111.
(10^19-1)/9= (1111111111111111111)=R(19).
***
J-C Colin wrote:
m, minimal prime such as H(m,i) prime for i = 0 to k
k m
0 11
1 13
2 1069
3 1979
4 3049
5 2381963
7 1046197333
and such as H(m,i) prime for i = 1 to k
k m
1 13
2 1021
3 1979
4 3049
5 5701
6 2335667
7 1041293663
8 2459868287
***
J. K. Andersen wrote:
Q1.
H(m,j) for j = 0, 1, 2 can only give three primes if the number of digits
in m is 1 modulo 3. Otherwise 3 will divide one of the three numbers.
m = 1046197333 is the smallest prime for k=6, and also for k=7.
m = 1194307993 is the smallest which only works to k=6.
m = 5769213841 is the smallest for k=8.
There is no prime below 10^12 for k=9.
Q2.
If m has n digits then it seems H(m,m) is divisible by the repunit
(10^n-1)/9.
***
Farideh wrote:
Answer to Q1 :
1046197333 is the smallest number m such that H(m, k)
for k = 0, 1, ... , 6 is prime.
Also 1046197333 is the smallest number m such that H(m, k)
for k = 0, 1, ... , 7 is prime.
***
Emmanuel Vantieghem wrote:
Because the numbers H(m,k) form an arithmetic
progression when k runs from 0 to 9, I first searched for the
natural numbers m such that H(m,k) is prime for k = 0, 1,
9.
Here is what I found :
H(13,k) is prime for 0 <= k <
2 (and not for k = 2)
H(1069,k) 0 <= k < 3
( k = 3)
H(1979,k) 0 <= k <
4 ( k = 4)
H(3049,k) 0 <= k <
5 ( k = 5)
H(1043809,k) 0 <= k <
6 ( k = 6)
H(4585547,k) 0 <= k <
7 ( k = 7)
Then I used the fact that, when a, a+d, a+2d, ... ,
a+(k-1)d are all primes, then the common difference d must be
divisible by every prime divisor p <= k (unless a = k which is never
the case in our situation). In our case, a = H(m,0) and d is of the
form 1010
10 where the number of ones is one less than the number of
digits in m, To be divisible by 3 and 7 m must have 4, 7, 10,
13,
digits. So, I could skip a lot of possible values for m. The
results then continue as follows :
H(1046197333,k) is prime for 0 <= k <
8 (and not for k = 8)
H(3379142501,k) 0
<= k < 9 ( k = 9)
H(7691546233,k) 0
<= k < 10 ( k = 10).
I did not find further results
for m below 10^10. The next candidate must be bigger than 10^12.
If we require m to be prime, the list looks the same
for k < 5 and further :
H(2381963,k) is prime for 0 <=
k < 6 (and not for k = 6)
H(1046197333,k) 0
<= k < 8 ( k = 8)
H(5769213841,k) 0
<= k < 9 ( k = 10).
For bigger k, we must start the computations
from 10^12 and this will take much more time
About the primality of H(m,m) : this happens only
if m is 2, 3, 5 or 7. For m >= 11 we can prove H(m,m) to be
divisible by the repunit R_n of n ones, where n is the
number of digits of m. For instance, H(13,13) = 1133 = 11x103,
Proof:
Assume m has n digits. Thus, m can be written
in the form
a(n-1)10^(n-1)+a(n-2)10^(n-2)+ ... +a(1)10+a(0) with 0 <= a(i) <
10.
Hence, it is easy to see that H(m,m) =
a(n-1)10^(n+1)(n-1)+a(n-2)10^(n+1)(n-2)+ ...
+a(1)10^(n+1)+a(0)+ 10m(10^(n+1)(n-2)+10^(n+1)(n-3)+ ...
+10^(n+1)+1.
Considering this equality modulo (10^n 1) and
using the fact that 10^(n+1) is congruent to 10 mod (10^n 1),
leads to H(m,m) === m+10m(10^(n-2)+10^(n-3)+ ... 10+1) (mod (10^n
1)) === m + m(10^(n-1)+10^(n-2)+ ... +10+1 1) (mod (10^n 1))
=== m R_n (mod (10^n 1)).
Since R_n = (10^n 1) /9, we have H(m,m) === 0
(mod R_n), QED.
***
|
