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

Home > Numbers
Amicable pair generator (Posted on 2016-07-08) Difficulty: 4 of 5
Find a value of n for which the following are each prime:
a=3*2n-1
b=3*2n-1-1
c=9*22n-1-1

The numbers 2n*a*b and 2n*c will be an amicable pair.

Show this always works.

Can this formula be generalized?

No Solution Yet Submitted by Jer    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts Computer exploration Comment 1 of 1

    5   open "amicprgn.txt" for output as #2
   10   for N=1 to 1000
   20     A=3*2^N-1
   30     B=3*2^(N-1)-1
   40     C=9*2^(2*N-1)-1
   50     if prmdiv(A)=A and prmdiv(B)=B and prmdiv(C)=C then
   60       :print N,A;B;C,A*B*2^N;C*2^N
   61       :print #2,N,A;B;C,A*B*2^N;C*2^N
   65    '  :else print N;
   70   next
   80   close #2
   
finds only   

 n   a   b     c       pair
 1   5   2    17      20  34 
 2  11   5    71     220  284 
 4  47  23  1151   17296  18416 
 7 383 191 73727 9363584  9437056 

A check on the amicability of the 8 found numbers finds the sum of the proper divisors of each of those 8 as being:

     22 20
    284 220
  18416 17296
9437056 9363584

indicating the first pair is not amicable but the remaining pairs are.

The testing program (for amicability) was:

Dim crlf$, fct(20, 1), f, divisor, totdiv


Private Sub Form_Load()
 Form1.Visible = True
 
 
 Text1.Text = ""
 crlf = Chr$(13) + Chr$(10)
 
 Text1.Text = Text1.Text & sumProperDivisors(20) & Str(sumProperDivisors(34)) & crlf
 Text1.Text = Text1.Text & sumProperDivisors(220) & Str(sumProperDivisors(284)) & crlf
 Text1.Text = Text1.Text & sumProperDivisors(17296) & Str(sumProperDivisors(18416)) & crlf
 Text1.Text = Text1.Text & sumProperDivisors(9363584) & Str(sumProperDivisors(9437056)) & crlf
 
 
 Text1.Text = Text1.Text & crlf & " done"
  
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

Function sumProperDivisors(n)
  f = factor(n)
  totdiv = 0
  divisor = 1
  sumD 1
  For i = 1 To f
    pf = pf * (fct(i, 1) + 1)
  Next
  sumProperDivisors = totdiv - n
End Function

Sub sumD(wh)
 
  For i = 0 To fct(wh, 1)
    dvsave = divisor
    divisor = divisor * fct(wh, 0) ^ i
    If wh = f Then
      totdiv = totdiv + divisor
    Else
      sumD wh + 1
    End If
    divisor = dvsave
  Next i
 
End Sub


From Wikipedia:

The first ten amicable pairs are: (220, 284), (1184, 1210), (2620, 2924), (5020, 5564), (6232, 6368), (10744, 10856), (12285, 14595), (17296, 18416), (63020, 76084), and (66928, 66992).(sequence A259180 in OEIS).

So n=1 does not produce two amicable numbers. And the other three seem to be the only other cases that satisfy the criteria.

This is confirmed by the referenced Wikipedia article, which does add the rule n > 1:

Thabit ibn Qurra theorem[edit]
The Thabit ibn Qurra theorem is a method for discovering amicable numbers invented in the ninth century by the Arab mathematician Thabit ibn Qurra.[4]

It states that if

p = 3 * 2^(n - 1) - 1,
q = 3 * 2^(n - 1},
r = 9 * 2^(2n - 1) - 1,

where n > 1 is an integer and p, q, and r are prime numbers, then 2^n*p*q and 2^n*r are a pair of amicable numbers. This formula gives the pairs (220, 284) for n=2, (17296, 18416) for n=4, and (9363584, 9437056) for n=7, but no other such pairs are known. Numbers of the form 3 * 2^(n - 1) are known as Thabit numbers. In order for Ibn Qurra's formula to produce an amicable pair, two consecutive Thabit numbers must be prime; this severely restricts the possible values of n.

To establish the theorem, Thâbit ibn Qurra proved nine lemmas divided into two groups. The first three lemmas deal with the determination of the aliquot parts of a natural integer. The second group of lemmas deals more specifically with the formation of perfect, abundant and deficient numbers.[5]

  Posted by Charlie on 2016-07-08 15:33:47
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