Problems & Puzzles: Puzzles
|
Problems & Puzzles: Puzzles
From Set 27 to Oct 3, 2025, contributions came from Michael Branicky, Oscar Volpatti, Simon Cavegn, *** Michael wrote:
I tested even-length-digit products covering all
2..22
digits (Q1-Q3) and
2..20
digits (Q4), respectively.
I found the following. Q1, Q2:
No instances
Q3:
43
* 47 =
2021 =
20 &
21 (intgers, ascending)
Q4:
5
* 7 =
35 =
3 &
5 (twins, ascending)
834657017
* 834657019 =
696652337696652323 =
696652337 &
696652323 (primes,
non-twins, descending)
6484544055
* 6484544057 =
42049311614204931135 =
4204931161 &
4204931135 (primes,
non-twins, descending)
*** Oscar wrote: I found 4 solutions to Q1.
Questions Q1 and Q2 of Puzzle 1239 are a re-proposal of question Q2 of
Problem 80.
I labelled my findings as solutions for
Problem 80 due to priority, but they are solutions for puzzle 1239 as
well.
...
I was able to find four more solutions to question
Q2 of problem 80.
Search strategy.
We need to find twin primes p and q, whose product is the
concatenation of two consecutive integers a and b.
If integer b has n digits, then equality p*q = a*10^n+b holds.
Substitute p = x-1, q = x+1, b = a+1 (ascending case), then
rearrange, obtaining:
x^2 = a*(10^n+1) + 2,
or, viewed as a congruence relation:
x^2 == 2 mod 10^n+1.
In other words;
2 must be a quadratic residue modulo w(n) = 10^n+1;
x must be a square root of 2 modulo w(n).
If complete factorization of number w(n) is known, we are able to
check if 2 is a quadratic residue modulo each prime factor of w(n),
and eventually to efficiently compute all possible square roots
modulo w(n) by using
Tonelli-Shanks algorithm and chinese remainder theorem; then,
for each square root x found, we can check if x-1 and x+1 are both
prime.
We only need to consider numbers n of the form n = 4*k, because:
2 is non-residue for prime 11, which divides w(n) whenever n =
2*k+1;
2 is non-residue for prime 101, which divides w(n) whenever n =
4*k+2.
Complete factorization of w(n) is currently known for many small
numbers n=4*k; first few exceptions are 332, 356, 392, 400...
After known solution for n=36, found by Israel, there are four more
solutions for n=396.
Note: quadratic residue 2 admits 2^22 = 4194304 distinct square
roots modulo w(396).
Solution 1:
p=
4355463 828116973131 51956101283374338
q=
4355463 828116973131 51956101283374338
a=
2072329 644830185074 89935557410917696
b=
2072329 644830185074 89935557410917696
Solution 2:
p=
94035074 2597534836961 3914978874060061374
q=
94035074 92597534836961 3914978874060061374
a=
42139343 65791996760671 62816622886154229923
b=
42139343 65791996760671 62816622886154229923
Solution 3:
p=
904969194 9033314302969017 05187179717864091713524
q=
904969194 9033314302969017 05187179717864091713524
a=
613334198 7122771002460369 97869881475467335078626
b=
613334198 7122771002460369 97869881475467335078626
Solution 4:
p=
901135182 8422592581863236 01560773341817937869825
q=
901135182 422592581863236 01560773341817937869825
a=
803458865 1362890723758605 61232316681860397280231
b=
803458865 1362890723758605 61232316681860397280231
Near-solution 1 (padding a zero between a and b):
p=
590578052 3542168234920976 56819077973483466158758
q=
590578052 3542168234920976 56819077973483466158758
a=
367449294 1126661003056837 68711204017422039375746
b=
367449294 1126661003056837 68711204017422039375746
Near-solution 2 (padding two zeros between a and b):
p=
5355911014 879114789874572697 95233821524863517808079423
q=
5355911014 879114789874572697 95233821524863517808079423
a=
7027126416 793624533410074279 03824757699262845432636928
b=
7027126416 793624533410074279 03824757699262845432636928 Accordingly I reported the same in Problem 80.
Q2. I found no
solutions involving
numbers with
400 digits or less.
I found several "small" solutions to
questions Q3 and Q4.
I'm sending the first three examples for each of the two possible orders.
Q3.
p*q = a*10^n+b
p and q consecutive primes;
a and b consecutive integers, in ascending or descending order.
n=2, ascending:
p=43
q=47 a=20 b=21
n=70, ascending:
p=
q= a= b=
n=72, ascending:
p= q= a= b= n=16, descending:
p=4803478892324963
q=4803478892324969 a=2307340946901148 b=2307340946901147
n=49, descending:
p=
q= a= b=
n=69, descending:
p=
q=
a= b=
Q4.
a*b = p*10^n+q
a and b consecutive odd integers;
p and q consecutive primes, in ascending or descending order.
n=30, descending:
a=
b= p= q=
n=40, descending:
a= b= p= q=
n=42, descending:
a= b= p= q=
n=43, ascending:
a=
b= p= q=
n=50, ascending:
a= b= p= q=
n=90, ascending:
a= b= p= q= *** Simon wrote:
Q1:
The file Puzzle1239_Findings.txt (24 Kb) contains the found
numbers that satisfy n*(n+2) = concat(x,y) where y=x+1. I marked the
findings with "None prime", "Solo prime", "Twin prime". Both primes are available to be sent by me (CR) to anyone interested in them, in request, "May be to show the search progress and hint on how to continue more efficiently than brute force?" ***
|
|||
|
|||
|
|||
