Problems & Puzzles: Puzzles

Puzzle 818. A follow up to Puzzle 814 Jim Howell sent this follow-up to Puzzle 814. "In puzzle 814, one could also ask for "s" and "p" such that p&s = prime  and s&p = square.  (The opposite of what is now asked for.)"   I told him that the real challenge was to find  a square s and two primes p & q such that p&s and q&s are primes and s&p and s&q are squares.   In a little preliminary search I made in my PC I found the following:   a) for s=9, I found not two but fifteen solutions for the following primes less than 10^7: 61, 409, 35089, 1718929, 2756161, 2987449, 3528241, 3760489, 5394289, 5511529, 6963409, 7160449, 7871449, 8465929, 8863249 b) for s=81, I found just two solutions for the following primes less than 10^7: 1801, 9161641 Q Can you find more trio of values s, p and q ?

---

Contributions came from Seiji Tomita, Jan van Delden and Emmanuel Vantieghem

***

Seiji wrote:

Search condition: s<10^4, p<10^9
If s=0 mod 3, then p=1 mod 3.

[s: p, q,...]
[9: 61, 409, 35089, 1718929, 2756161, 2987449, 3528241, 3760489, 5394289, 5511529, 6963409,
 7160449, 7871449, 8465929, 8863249, 9420841, 112420681, 125407729, 129611401, 155236489,
 188564449, 195083881, 201221929, 230789929, 242707321, 246168649, 265410049, 294695281,
 298166329, 308197441, 316303441, 317847841, 337163641, 343348921, 360369001, 369659209,
 403374841, 408418009, 415403089, 458146009, 460869289, 465538681, 497087209, 532983769,
 536889649, 576383881, 584997409, 586172281, 592831249, 626945689, 657582529, 664659481,
 692205601, 709934521, 715453489, 733203649, 758081089, 775870129, 777452161, 827351689,
 848776081, 852349081, 888910249, 892888369, 927531769, 940688209, 952656169, 958243681,
 959441209, 996600289]
[81: 1801, 9161641, 116166481, 123002041, 203911369, 211890529, 460580569, 612491041,
 756536761, 875527321]
[441: 1483561, 107177281, 170938849, 351621649, 386168161, 410085769, 457922929,
497789209, 550947049, 561579001, 654614041, 721073641, 737024689, 869961289, 960369601]
[729: 126424321, 263052961, 382613521, 457770889, 884874889]
[1089: 411975001, 457900441, 808635721]
[1521: 7442881, 218824129, 282960409, 544453081, 578991529, 914528281]
[2601: 44641, 165772969]
[3249: 146846521, 658787761]
[3969: 126001, 932715961]
[7569: 117947209, 712218721]
 

***

Jan wrote:

If a solution exists we must have  s mod 30 in {9,21}  and p,sp,ps mod 30 in {1,19}.

In order of increasing number of digits of s we have {1,1,2,10,28,92,288,912,2882,9118} possible values for s.
For all these values of s there are at least 3 prime values p. For every admissible s the number of solutions is probably infinite.
In order for sp to be square, the first digits must match the digits of s, this seems to enforce a lowerbound on (the number of digits of) p.
 

With n, the number of digits of s and d the number of digits of p, a table where the smallest solution p has d<n (n<=10):

n                     s                 p  d
8       24235929     2459449  7

8       59120721     3451009  7
8       69505569     7760281  7

9     168194961     2073241  7

10 1417296609 658134241  9
10 1477556721     5053681  7
10 2562283161 638262241  9
10 3360404961 648903169  9
10 4455162009     7067209  7

 

Maximum(d)=m, the number of digits of the smallest solution p belonging to all s with n digits, increases with n.
  n                  s                                      p   m

  1                  9                                    61   2
  2                81                                1801   4
  3              729                      126424321   9
  4            8649                  19337259121 11

  5          59049              1231921038529 13

  6        927369          131773765632961 15

  7      6487209          113809391969521 15

  8    43046721      14824343543735281 17

  9  127983969      10478541901238569 17

10 3924897201 1007289727517693761 19
So it’s just a matter of waiting for the solutions to appear..

 

The solutions for s=81, with s<10^10 are:
1801, 9161641, 116166481, 123002041, 203911369, 211890529, 460580569, 612491041, 756536761, 875527321

There are 96 solution with s<10^12, 932 solutions with s<10^14 and 4492 solutions with s<10^16 etc.

***

Emmanuel wrote:

First of all, as in puzzle 814, we must have  s  divisible by  9  and  p, q congruent  1 mod 3.

Furthermore,  s  must be odd and not divisible by  5.  This gives the first admissible values for  s :

9, 81, 441, 729, 1089, 1521, 2601, 3249, 3969, 4761, 6561, 7569, 8649, 9801, ...

The  p, q  are given in the following table (where  "... ?"  means that there can be more solutions) :

  s           p, q, ...

   9        61, 409, 35089, 1718929, 2756161, 2987449, 3528241, 3760489, 5394289, 5511529, and many others

  81        1801, 9161641, 116166481, 123002041, 203911369, 211890529, 460580569, 612491041, 756536761, 875527321, ... ?

 441        1483561, 107177281, 170938849, 351621649, 386168161, 410085769, 457922929, 497789209, ... ?

 729        126424321, 263052961, 382613521, 457770889, 884874889, ... ?

1089        411975001, 457900441, 808635721, ... ?

1521        7442881, 218824129, 544453081, 578991529, 914528281, ... ?

2601        44641, 165772969, ... ?

3249        146846521, 658787761, ... ?

3969        126001, 932715961, ... ?

4761        477490561,16720369801, ... ?

6561        943133641, ... ?

7569        117947209, 712218721, ... ?

 

I also used the fact that  p  must be a quadratic residue modulo  10^w, where  w  is the number of digits of  p.

The first such  p  are : 61, 241, 409, 601, 769, 1009, 1129, 1201, 1249, 1321, 1489, 1609, 1801, 2089, 2161, 2281, 2521, 2689, 3001, 3049, ... 

 

***