All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Infinite Illation Decision (Posted on 2015-12-31) Difficulty: 3 of 5
Each of X and Y is a positive integer, such that:
  • X and Y are relatively prime, and:
  • Each of (X2 – 5)/Y and (y2 – 5)/X is a positive integer.
Does there exist an infinite numbers of pairs (X,Y) satisfying the given conditions?
Give reasons for your answer.

No Solution Yet Submitted by K Sengupta    
Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts It seems... | Comment 1 of 3
It looks as if there's an infinite supply, with each lower value being the upper value from the preceding pair. Each upper value is approximately (3+sqrt(5))/2 times the lower value. That factor is phi + 1 where phi is the golden ratio.

4  11
11  29
29  76
76  199
199  521
521  1364
1364  3571


3571  9349
9349  24476
24476  64079
64079  167761
167761  439204
439204  1149851
1149851  3010349
3010349  7881196
7881196  20633239
20633239  54018521
54018521  141422324
141422324  370248451
370248451  969323029
969323029  2537720636
2537720636  6643838879
6643838879  17393796001

from

DefDbl A-Z
Dim crlf$


Private Sub Form_Load()
 Form1.Visible = True
 
 Text1.Text = ""
 crlf = Chr$(13) + Chr$(10)
 
 For tot = 6 To 5000
  For x = 3 To tot / 2
   DoEvents
   y = tot - x
   If gcd(x, y) = 1 Then
     If (x * x - 5) Mod y = 0 Then
     If (y * y - 5) Mod x = 0 Then
       Text1.Text = Text1.Text & x & "  " & y & crlf
       ysave = y
     End If
     End If
   End If
  Next
 Next
 Text1.Text = Text1.Text & crlf & crlf
 
 x = ysave
 rat = 1.5 + Sqr(5) / 2
 Do
   y = Int(x * rat) - 1
   did = 0
   Do
     DoEvents
     y = y + 1
     If gcd(x, y) = 1 Then
       q = Int((x * x - 5) / y)
       r = (x * x - 5) - y * q
       If r = 0 Then
       q = Int((y * y - 5) / x)
       r = (y * y - 5) - x * q
       If r = 0 Then
         Text1.Text = Text1.Text & x & "  " & y & crlf
         did = 1
       End If
       End If
     End If
   Loop Until did
   x = y
 Loop Until y > 10000000000#

 Text1.Text = Text1.Text & crlf & " done"
  
End Sub

Function gcd(a, b)
  x = a: y = b
  Do
   q = Int(x / y)
   z = x - q * y
   x = y: y = z
  Loop Until z = 0
  gcd = x
End Function

I had first noticed the fact that the new low value was the old high value. After that, and placing the second part of the program, I noticed the ratio, after having first put in a guess of twice the low value and going up by 1 from there, as it's faster to start with the more accurate multiple.

To continue further without worrying about limits of precision, continuation is in UBASIC:


   10           x = 3571
   20           rat = 1.5 + Sqr(5) / 2
   30           repeat
   40             y = Int(x * rat) - 1
   50             did = 0
   60             repeat
   80               y = y + 1
   90               If gcd(x, y) = 1 Then
  100                 q = Int((x * x - 5) / y)
  110                 r = (x * x - 5) - y * q
  120                 If r = 0 Then
  130                 q = Int((y * y - 5) / x)
  140                 r = (y * y - 5) - x * q
  150                 If r = 0 Then
  160                  :print  x ; "  " ; y       
  180                  :did = 1
  190                 :End If
  200                 :End If
  210               :End If
  220             Until did
  230             x = y
  240           Until y > 1000000000000000000000000


 3571    9349 
 9349    24476 
 24476    64079 
 64079    167761 
 167761    439204 
 439204    1149851 
 1149851    3010349 
 3010349    7881196 
 7881196    20633239 
 20633239    54018521 
 54018521    141422324 
 141422324    370248451 
 370248451    969323029 
 969323029    2537720636 
 2537720636    6643838879 
 6643838879    17393796001 
 17393796001    45537549124 
 45537549124    119218851371 
 119218851371    312119004989 
 312119004989    817138163596 
 817138163596    2139295485799 
 2139295485799    5600748293801 
 5600748293801    14662949395604 
 14662949395604    38388099893011 
 38388099893011    100501350283429 
 100501350283429    263115950957276 
 263115950957276    688846502588399 
 688846502588399    1803423556807921 
 1803423556807921    4721424167835364 
 4721424167835364    12360848946698171 
 12360848946698171    32361122672259149 
 32361122672259149    84722519070079276 
 84722519070079276    221806434537978679 
 221806434537978679    580696784543856761 
 580696784543856761    1520283919093591604 
 1520283919093591604    3980154972736918051 
 3980154972736918051    10420180999117162549 
 10420180999117162549    27280388024614569596 
 27280388024614569596    71420983074726546239 
 71420983074726546239    186982561199565069121 
 186982561199565069121    489526700523968661124 
 489526700523968661124    1281597540372340914251 
 1281597540372340914251    3355265920593054081629 
 3355265920593054081629    8784200221406821330636 
 8784200221406821330636    22997334743627409910279 
 22997334743627409910279    60207804009475408400201 
 60207804009475408400201    157626077284798815290324 
 157626077284798815290324    412670427844921037470771 
 412670427844921037470771    1080385206249964297121989 


  Posted by Charlie on 2015-12-31 10:18:36
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information