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, ... 

 

***

Records   |  Conjectures  |  Problems  |  Puzzles