It is observed that Φ(1)=1 and, Φ(2)=1, where Φ(x) denotes
Euler's totient function.
So for x=1, it is trivially observed that each of Φ(x) and Φ(x+1) is a perfect square.
(A) What is the next positive integer value of x such that each of Φ(x) and Φ(x+1) is a perfect square?
(B) What is the value of x with 2000 ≤ x ≤ 2100 such that each of Φ(x) and Φ(x+1) is a perfect square?
Totients were checked for numbers through 100,000. All eligible pairs within that range are shown.
To answer the questions:
(A) 125 is the next such x
(B) 2047 falls in the range asked for
x x+1 totient function values
1 2 1 1
125 126 100 36
504 505 144 400
512 513 256 324
513 514 324 256
629 630 576 144
679 680 576 256
1358 1359 576 900
1728 1729 576 1296
1970 1971 784 1296
2047 2048 1936 1024
2834 2835 1296 1296
3458 3459 1296 2304
4400 4401 1600 2916
4577 4578 4356 1296
4616 4617 2304 2916
4913 4914 4624 1296
5403 5404 3600 2304
6817 6818 6400 2916
8729 8730 7056 2304
16523 16524 14400 5184
23085 23086 11664 9216
24564 24565 7744 18496
25220 25221 9216 14400
37829 37830 32400 9216
44010 44011 11664 40000
44825 44826 32400 14400
45032 45033 20736 28224
50736 50737 14400 50176
52428 52429 16384 46656
55419 55420 28224 20736
58311 58312 32400 28224
61336 61337 25600 60516
67207 67208 57600 32400
68250 68251 14400 67600
78624 78625 20736 57600
84874 84875 42436 57600
89784 89785 28224 71824
98280 98281 20736 94864
DefDbl A-Z
Dim crlf$
Dim fct(20, 1)
Private Sub Form_Load()
Text1.Text = ""
crlf$ = Chr(13) + Chr(10)
Form1.Visible = True
DoEvents
For d = 1 To 100000
DoEvents
f = factor(d)
relprime = d
For i = 1 To f
relprime = relprime * (1 - 1 / fct(i, 0))
Next
sq = relprime
sr = Int(Sqr(sq) + 0.5)
If sr * sr = sq Then
If d = dsave + 1 And dsave > 0 Then
Text1.Text = Text1.Text & d - 1 & Str(d) & " "
Text1.Text = Text1.Text & sqsave & Str(sq) & crlf
End If
srsave = sr
sqsave = sq
dsave = d
End If
Next d
Text1.Text = Text1.Text & " done" & crlf
End Sub
Function factor(num)
diffCt = 0: good = 1
n = Abs(num): If n > 0 Then limit = Sqr(n) Else limit = 0
If limit <> Int(limit) Then limit = Int(limit + 1)
dv = 2: GoSub DivideIt
dv = 3: GoSub DivideIt
dv = 5: GoSub DivideIt
dv = 7
Do Until dv > limit
GoSub DivideIt: dv = dv + 4 '11
GoSub DivideIt: dv = dv + 2 '13
GoSub DivideIt: dv = dv + 4 '17
GoSub DivideIt: dv = dv + 2 '19
GoSub DivideIt: dv = dv + 4 '23
GoSub DivideIt: dv = dv + 6 '29
GoSub DivideIt: dv = dv + 2 '31
GoSub DivideIt: dv = dv + 6 '37
If INKEY$ = Chr$(27) Then s$ = Chr$(27): Exit Function
Loop
If n > 1 Then diffCt = diffCt + 1: fct(diffCt, 0) = n: fct(diffCt, 1) = 1
factor = diffCt
Exit Function
DivideIt:
cnt = 0
Do
q = Int(n / dv)
If q * dv = n And n > 0 Then
n = q: cnt = cnt + 1: If n > 0 Then limit = Sqr(n) Else limit = 0
If limit <> Int(limit) Then limit = Int(limit + 1)
Else
Exit Do
End If
Loop
If cnt > 0 Then
diffCt = diffCt + 1
fct(diffCt, 0) = dv
fct(diffCt, 1) = cnt
End If
Return
End Function
|
|
Posted by Charlie
on 2016-10-24 19:16:26 |
computer solution
