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

Home > Just Math
Totient Trial (Posted on 2016-10-24) Difficulty: 3 of 5
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?

No Solution Yet Submitted by K Sengupta    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution computer solution Comment 2 of 2 |
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
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 (2)
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