Problems & Puzzles: Puzzles

Puzzle 474. Two last puzzles for this 2008 JM Bergot sent the following two nice puzzles: 1. Prime 673, 673=1(mod6)=1(mod7)=1(mod3). Q1. Find larger primes free of digits "0" & "1" having the same residue for all their digits. Q2. Is there a largest one? 2. There are four consecutive primes such that: 5471=3(mod4) 5477=5(mod8) 5479=7(mod16) 5483=11(mod32) Q3. Find a larger sequence of consecutive of primes with the same property pointed out above.

---

Contributions came from Farideh Firoozbakht, Jim Howell, Qu Shun Liang, Jim Van Delden & Edwin W. Clark.

Farideh wrote:

Q1: Smallest n-digit such prime for n=3, 4, ..., 17 are:

223,2269,22699,223273,2222263,22222327,222222433,2222224489,
22222222669,222222223273,2222222222323,22222222222327,
222222222222337,2222222222222773 & 22222222222223629.

Q2: All such primes with different digits are (seeA152852) :
2, 3, 5, 7, 379, 673, 2437, 23689, 24697, 47629, 62497, 68329, 84673 & 348769.

Q3:

1287544267 = 3 (mod 2^2)
1287544277 = 5 (mod 2^3)
1287544327 = 7 (mod 2^4)
1287544331 = 11 (mod 2^5)
1287544333 = 13 (mod 2^6)
1287544337 = 17 (mod 2^7)
1287544339 = 19 (mod 2^8)
1287544343 = 23 (mod 2^9)

***

Jim Howell wrote:

(Q1) Here are a few other primes with the same property as 673.

636363636363636363636363673 (with "63" appearing 12 times).
and
63...63673 with "63" appearing 53 times.
and
63...63673 with "63" appearing 134 times. (Currently only a probable prime.)

Each of these is 1 (mod 6), 1 (mod 7), and 1 (mod 3).

(Q2) Since there are probably an infinite number of primes like these, there is probably not a largest prime with the stated property.

Later he added:

You asked about Question 1 with more distinct digits.

I tested all primes of 9 digits or less, and found the following:

The "mod value" for the vast majority of these primes is 1.

Here are all of the three-digit primes satisfying the conditions of Question 1:

223 = 1 (mod each digit)
379 = 1 (mod each digit)
433 = 1 (mod each digit)
673 = 1 (mod each digit)
677 = 5 (mod each digit)
787 = 3 (mod each digit)

The smallest prime with 4 distinct digits (and satisfying Question 1):

2437 = 1 (mod each digit)

The smallest prime with 5 distinct digits:

23689 = 1 (mod each digit)

The next prime (after 787) where the "mod value" is not 1:

35597 = 2 (mod each digit)

The smallest prime with 6 distinct digits:

348769 = 1 (mod each digit)

The first few primes (8 digits) with 7 distinct digits:

23684977 = 1 (mod each digit)
24687937 = 1 (mod each digit)
26489737 = 1 (mod each digit)
26837497 = 1 (mod each digit)

The largest 9-digit prime with 7 distinct digits is:

998672473 = 1 (mod each digit)

The largest 9-digit prime with the "mod value" not equal to 1:

999996989 = 5 (mod each digit), but only 3 distinct digits

For Question 1, a prime with 8 distinct digits (containing each of the digits 2 thru 9 at least once) is impossible, assuming the residue must be less than each digit.

Suppose such a prime P exists. Since P contains the digit 2, the residue must be 0 or 1. If 0, then P is not prime. Therefore P = 1(mod 2).

Therefore P = 1(mod 2) = 1(mod 3) = ... = 1 (mod 9).

In order to have P = 1(mod 5), P must end in "1". But the digit 1 is not allowed.

------------------

If the residue is not required to be less than the digit, so that we are just working with congruences, then the following (with 8 distinct digits) will work:

23456837893 = 13(mod 2) = 13(mod 3) = 13(mod 4) = ... = 13(mod 9)

However, if this is allowed, then ANY prime (not containing 0 or 1) will work for Question 1, since one could write (for example):

257 = 257(mod 2) = 257(mod 5) = 257(mod 7)

23456789 = prime = 23456789(mod 2) = 23456789(mod 3) = ... = 23456789(mod 9)

-----------------

Just for fun, here is a 100-digit (probable) prime, with 7 distinct digits (where 222...222 represents 88 occurrences of the digit 2):

2346789222...22264649 = 1(mod 2) = 1(mod 3) = 1(mod 4) = 1 (mod 6) = 1 (mod 7) = 1 (mod 8) = 1(mod 9).
 

***

Qu Shun Liang wrote:

Q2:
I notice that 337=1(mod3)=1(mod7). Is 337 allowed?( here digits 3 use twice ).
If we allowed digits use many times, I think there will not a largest one.
Otherwise, obviously, there will be a largest solution.
Q3:
I found a 8 consecutive primes:
1287544267=3(mod 4)
1287544277=5(mod 8)
1287544327=7(mod 16)
1287544331=11(mod 32)
1287544333=13(mod 64)
1287544337=17(mod 128)
1287544339=19(mod 256)
1287544343=23(mod 512)

***

Jan van Delden wrote:

Q2: No apparent reason why there should be 'a largest one'.

Q1: Primes of consisting of only 7's and 9's, having residu 1 (mod 7 and mod 9).
Suppose we have k 9's, where the positions of the 9's have index a[i], with i in [1..k] and l 7's.

Modulo 9 we have: sum(7,i=1..l)=7*l=1 mod 9, so l=4 mod 9. A condition on the total number of 7's.
Modulo 7 we have that 10 mod 7=3 and 9 mod 7=2, so 2*sum(3^a[i],i=1..k)=1 mod 7.

A small table:

a[i]	2*3^a[i] mod 7
0	2
1	6
2	4
3	5
4	8
5	3

If a[i] is larger we can reduce it mod 6, since 3^6=1 mod 7. (The order of 3 mod 7 is 6,or here phi(7)=6).
For possible combinations (below) the consequence is that we can add a multiple of 6 to each allready found index.

Some combinations of a[i] which make the sum equal to 1 mod 7 are:
Sum 8 : (0,1),(3,5) but also (0,0,0,0) gives for instance (0,6,12,18)
Sum 15 : (0,3,4),(1,2,3),(2,4,5)
Sum 22: (0,1,3,5,7),(0,1,2,4,6),(0,2,3,4,5), etc.

Giving conditions of the possible placement of the 9's.

Some solutions:

Pattern 9’s	First Prime	Digits
(0,1)	Not possible (*)
(3,5)	{7}[28*9]979777	258
(0,3,4)	{7}[27*9+2]99779	250
(1,2,3)	7779997	7
(2,4,5)	{7}[21*9+1]997977	196
(0,1,3,5,7)	797979799	9
(0,1,2,4,6)	{7}[4*9+2]9797999	45
(0,2,3,4,5)	{7}[3*9+3]999979	36
(0,6,12,18)	{7}[19*9+7]9777779777779777779	197
(0,60,120,180)	{7}[14*9+7]9{7}[59]9{7}[59]9{7}[59]9	314
(0,600,1200,1800)	{7}[14*9+7]9{7}[599]9{7}[599] 9{7}[599]9	1934

(*) If the pattern is (0,1) the number of 7's should be odd, otherwise 11 is a divisor, but then 19 is a divisor!

Take n= {7}[(2*k+1)*9+4]99 100={7}[18k+13]99.
{7}[13] mod 19 = 3 and 100 mod 19=5 together with 99 mod 19=4 gives for k=0: n mod 19=(3*5+4) mod 19=0 mod 19.
Finally {7}[18] mod 19=0 mod 19. q.e.d.

This procedure can be repeated with other digits as well. The steps are of course the easiest when the digits are 2,3,5 or 9.

Primes of consisting of l 2's and k 9's, having residu 1 obligatory.

Mod 2: Our number should be odd, hence 1 mod 2.
Mod 9: 2*l = 1 mod 9, gives l = 5 mod 9.

For instance the form {2}[5]{9}[k]=22223*10^k-1, solutions:
k=11,39,74,126,129,201,387,724,1829,2768, (no more <=5000).

Primes of consisting of l 5's and k 9's, residu 4 obligatory.

Mod 5: Our number should end in a 9, hence our number is 4 mod 5.
Mod 9: 5*l=4 mod 9, gives l=8 mod 9.

For instance the form {5}[8]{9}[k]=55555556*10^k-1 solutions:
k=5,749,867,1629, (no more <=5000).

***

Edwin W. Clark wrote:

Here are some results on Puzzle 474 which probably many of your regular puzzle solvers will have noticed:

Part 1:
Looking among primes of the form p=22...29...99
where there are i 2's followed by j 9's. I found many values of i,j giving primes. When i is = 5 mod 9 such a prime p satisfies p mod 9 = 1 and p mod 2 = 1. For i from 5 to 1805 and j from 1 to 20 the values of i,j giving such primes (using Maple's "isprime" function) are:

i j
59 3
284 3
1634 3
23 6
203 6
455 6
464 7
257 8
5 11
842 15
131 18
473 20


If one allows in addition a string of 9's at the beginning,looking at numbers of the form 99...922...299..9, one finds even more primes satisfying p mod 2 = 1 and p mod 9 = 1. But I don't know how to prove there are infinitely many.

I think it may not be possible to have a prime p with all digits except 0 and 1 that have the same residue modulo each digit in p. Since p is prime it must have least significant digit d = 3 or 7 or 9.
Now
p mod 5 = d mod 5 and
p mod 2 = d mod 2.

But
3 mod 2 = 1 and 3 mod 5 = 3 so d is not 3
7 mod 2 = 1 and 7 mod 5 = 2 so d is not 7
9 mod 2 = 1 and 9 mod 5 = 4 so d is not 9

I also searched among random strings of the digits 2,3,4,6,7,8,9 and found easily, for example, the following 100 digit prime p congruent to 1 modulo each digit in p:

4297773684226746264829766489898287894393887348842798928973998774398883983439427843784869984623668673

Part 2:

Here's an example with 7 consecutive primes satisfying the condition:

502103027 = 3 mod 2^2
502103029 = 5 mod 2^3
502103047 = 7 mod 2^4
502103051 = 11 mod 2^5
502103053 = 13 mod 2^6
502103057 = 17 mod 2^7
502103059 = 19 mod 2^8

***

J. K. Anderse wrote:

Q1.
I assume the prime must have more than one digit and each digit must
be larger than the shared residue. The first such primes are:
223, 337, 379, 433, 673, 677, 787, 2269, 2437, 2833, 3433, 3889, 4933,
4969, 6229, 6637, 6679, 6763, 6949, 7477, 8233, 8737, 8929, 9433, 9649,
22699, 23227, 23293, 23623, 23689, 23773, 23833, 24229, 24697, ....

The smallest prime with each possible value mod the digits is:
mod 1: 223
mod 2: 35597
mod 3: 787
mod 4: 597559
mod 5: 677
mod 7: 8989999

mod 0 is impossible when the number has to be a multi-digit prime with
digits above 1.
mod 6 is impossible because:
If the number only contains the digit 7 then it's divisible by 7.
If it contains the digit 8 then it has to be 6 (mod 8) but then it's even.
If it contains the digit 9 then it has to be 6 (mod 9) but then it's
divisible by 3.
mod 8 is impossible because the only digit would have to be 9 and then
the number is divisible by 3.

A prime containing both the digit 2 and 5 cannot have this property.
The digit 2 means it has to be 1 (mod 2). Then it also has to be 1 (mod 5)
which means it either ends in 1 or 6. But the ending digit 1 is disallowed
and the ending 6 would make it even.
The most possible distinct digits is 2, 3, 4, 6, 7, 8, 9.
The smallest prime with these digits and the given property is 23684977.

Q2.
It seems very unlikely there is a largest such prime but I cannot prove it.
The largest already known prime or prp I could locate is at
http://www.primenumbers.net/prptop/prptop.php:
10^43435-66663 = 9(43430)33337, found by Milton L. Brown in 2008.
The prp is 1 modulo each of its digits 3, 7, 9.

I computed a larger solution with PrimeForm/GW which also proved primality:
326339726294*10^49988-1 = 3263397262939(49988), a 50000-digit prime.
The digits are 2, 3, 6, 7, 9, and the prime is 1 modulo each of those digits.

Q3.
I assume the property is nth term = nth odd prime (mod 2^(n+1)). The infinite
sequence of all odd primes satisfies this so I assume that is disallowed.

The first sequence of length 5:
62971=3 (mod 4)
62981=5 (mod 8)
62983=7 (mod 16)
62987=11 (mod 32)
62989=13 (mod 64)

The first of length 6:
1925359=3 (mod 4)
1925381=5 (mod 8)
1925383=7 (mod 16)
1925387=11 (mod 32)
1925389=13 (mod 64)
1925393=17 (mod 128)

The first of length 7:
502103027=3 (mod 4)
502103029=5 (mod 8)
502103047=7 (mod 16)
502103051=11 (mod 32)
502103053=13 (mod 64)
502103057=17 (mod 128)
502103059=19 (mod 256)

The first of length 8:
1287544267=3 (mod 4)
1287544277=5 (mod 8)
1287544327=7 (mod 16)
1287544331=11 (mod 32)
1287544333=13 (mod 64)
1287544337=17 (mod 128)
1287544339=19 (mod 256)
1287544343=23 (mod 512)

The first of length 9:
876749583247=3 (mod 4)
876749583293=5 (mod 8)
876749583319=7 (mod 16)
876749583371=11 (mod 32)
876749583373=13 (mod 64)
876749583377=17 (mod 128)
876749583379=19 (mod 256)
876749583383=23 (mod 512)
876749583389=29 (mod 1024)

A sequence of length 15 but I don't know whether it's the first:
6331030051177054863191=3 (mod 4)
6331030051177054863253=5 (mod 8)
6331030051177054863271=7 (mod 16)
6331030051177054863371=11 (mod 32)
6331030051177054863373=13 (mod 64)
6331030051177054863377=17 (mod 128)
6331030051177054863379=19 (mod 256)
6331030051177054863383=23 (mod 512)
6331030051177054863389=29 (mod 1024)
6331030051177054863391=31 (mod 2048)
6331030051177054863397=37 (mod 4096)
6331030051177054863401=41 (mod 8192)
6331030051177054863403=43 (mod 16384)
6331030051177054863407=47 (mod 32768)
6331030051177054863413=53 (mod 65536)

***