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

Home > Just Math
Three Product Tease (Posted on 2014-06-12) Difficulty: 3 of 5
Define P(n) as the sum of all the positive integers that are less than n and relatively prime to n.

Find all possible positive integer values of n such that P(n) = 3n, and prove that there are no others.

No Solution Yet Submitted by K Sengupta    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution numbers without proof of completeness | Comment 1 of 2
DefDbl A-Z
Dim crlf$

Function mform$(x, t$)
  a$ = Format$(x, t$)
  If Len(a$) < Len(t$) Then a$ = Space$(Len(t$) - Len(a$)) & a$
  mform$ = a$
End Function

Private Sub Form_Load()
 ChDir "C:\Program Files (x86)\DevStudio\VB\projects\flooble"
 Text1.Text = ""
 crlf$ = Chr(13) + Chr(10)
 Form1.Visible = True
 DoEvents
 For n = 1 To 1000000
   p = phi(n)
   If p = 3 * n Then
     Text1.Text = Text1.Text & mform(n, "#####0") & mform(p, "#####0")
      Text1.Text = Text1.Text & "      "
     For i = 1 To n
      If gcd(i, n) = 1 Then Text1.Text = Text1.Text & mform(i, "#####0")
     Next
     Text1.Text = Text1.Text & crlf
   End If
   DoEvents
 Next
End Sub

Function gcd(a, b)
  x = a: y = b
  Do
   z = x Mod y
   x = y: y = z
  Loop Until z = 0
  gcd = x
End Function

Function phi(n)
 tot = 0
 For i = 1 To n
  If gcd(i, n) = 1 Then tot = tot + i
 Next
 phi = tot
End Function

finds

     n	   p                     coprimes of n
     7    21           1     2     3     4     5     6
     9    27           1     2     4     5     7     8
    14    42           1     3     5     9    11    13
    18    54           1     5     7    11    13    17
    
After that the p's get larger and larger relative to 3n, but a proof that there are no others eludes me. I would think it would involve two cases: (i) the largest prime factor of n is no more than some given prime, such as 7; (ii) there is a prime factor larger than that prime.  Either way we'd have to set a maximum limit on n.


  Posted by Charlie on 2014-06-12 11:37:50
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 (9)
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