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

 Three Product Tease (Posted on 2014-06-12)
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.)
 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

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

 Search: Search body:
Forums (0)